open access publication

Article, 2024

Arc-disjoint out- and in-branchings in compositions of digraphs

European Journal of Combinatorics, ISSN 0195-6698, Volume 120, 10.1016/j.ejc.2024.103981

Contributors

Bang-Jensen J. 0000-0001-5783-7125 [1] Wang Y. [1] [2]

Affiliations

  1. [1] University of Southern Denmark
  2. [NORA names: SDU University of Southern Denmark; University; Denmark; Europe, EU; Nordic; OECD];
  3. [2] Shandong University
  4. [NORA names: China; Asia, East]

Abstract

An out-branching B (in-branching B) in a digraph D is a connected spanning subdigraph of D in which every vertex except the vertex u, called the root, has in-degree (out-degree) one. A good(u,v)-pair in D is a pair of branchings B,B which have no arc in common. Thomassen proved that it is NP-complete to decide if a digraph has any good pair. A digraph is semicomplete if it has no pair of non-adjacent vertices. A semicomplete composition is any digraph D which is obtained from a semicomplete digraph S by substituting an arbitrary digraph H for each vertex x of S. Recently the authors of this paper gave a complete classification of semicomplete digraphs which have a good (u,v)-pair, where u,v are prescribed vertices. They also gave a polynomial algorithm which for a given semicomplete digraph D and vertices u,v of D, either produces a good (u,v)-pair in D or a certificate that D has no such pair. In this paper we show how to use the result for semicomplete digraphs to completely solve the problem of characterizing semicomplete compositions which have a good (u,v)-pair for given vertices u,v. Our solution implies that the problem of deciding the existence of a good (u,v)-pair and finding such a pair when it exists is polynomially solvable for all semicomplete compositions. We also completely solve the problem of deciding the existence of a good (u,v)-pair and finding one when it exists for digraphs that are compositions of transitive digraphs. Combining these two results we obtain a polynomial algorithm for deciding whether a given quasi-transitive digraph D has a good (u,v)-pair for given vertices u,v of D. This proves a conjecture of Bang-Jensen and Gutin from 1998.

Funders

  • Danmarks Frie Forskningsfond
  • China Scholarship Council

Data Provider: Elsevier