2023/02/16 by Joergen Bang-Jensen, Yun Wang, Bang-Jensen, Joergen +1
Computer Science · #Advanced Graph Theory Research #semigroups and automata theory #Complexity and Algorithms in Graphs
paper · pdf · doi:10.48550/arxiv.2302.08283
An out-branching B+u (in-branching B-u) 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 \bf good (u,v)-pair in D is a pair of branchings B+u,B-v which have no arc in common. Thomassen proved that is NP-complete to decide if a digraph has any good pair. A digraph is \bf semicomplete if it has no pair of non adjacent vertices. A \bf semicomplete composition is any digraph D which is obtained from a semicomplete digraph S by substituting an arbitrary digraph Hx 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 of D. 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 such pair. In this paper we show how to use the result for semicomplete digraphs to completely solve the problem of deciding whether a given semicomplete composition D, has a good (u,v)-pair for given vertices u,v of D. Our solution implies that the problem is polynomially solvable for all semicomplete compositions. In particular our result implies that there is 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 confirms a conjecture of Bang-Jensen and Gutin from 1998.