Arc-disjoint out-branching and in-branching
Status partial high confidence
The general Thomassen conjecture — that some universal $k$ suffices for all digraphs — remains open. Since 2013, the conjecture has been verified for digraphs of independence number at most 2 (where $k=2$ suffices), for semicomplete digraphs (complete classification of which pairs of roots admit a good pair), and for semicomplete compositions; separately, extremal work showed the smallest 2-arc-strong digraph without a good pair has at least 10 vertices.
Cited literature (5)
-
Every digraph with independence number at most 2 and arc-connectivity at least 2 has an arc-disjoint out-branching and in-branching (i.e., $k=2$ suffices for this class), settling Thomassen's conjecture for digraphs of independence number 2.
-
Every 2-arc-strong digraph on at most 9 vertices has a good pair (arc-disjoint out- and in-branching), so any 2-arc-strong counterexample to the conjecture with $k=2$ requires at least 10 vertices.
-
Provides a complete polynomial-time decidable characterisation of which semicomplete digraphs contain a good $(u,v)$-pair for prescribed roots, generalising the 1991 tournament result of Bang-Jensen and confirming a conjecture of Bang-Jensen for semicomplete digraphs.
-
Completely solves (in polynomial time) the good-pair problem for semicomplete compositions, extending the semicomplete-digraph classification to a broader class.
-
Proves that every 3-arc-strong split digraph has a strong arc decomposition (partition of arcs into two strong spanning subdigraphs), which implies good pairs exist in this class; also shows 2-arc-strong is insufficient in general for split digraphs.
Reviewer notes. The Wiley (JGT) and ScienceDirect pages returned HTTP 403 and could not be fetched directly; DOIs 10.1002/jgt.22779 and 10.1002/jgt.23072 are taken from Wiley URL patterns visible in search results and are reported with medium confidence. The DOI for arXiv:2302.08283 (European J. Combinatorics) and arXiv:2012.03742 (Theoretical Computer Science) could not be confirmed and are set to null. The conjecture for general digraphs remains open as of all verified sources. The 2019 paper arXiv:1906.08052 (Gutin, Sun) addresses the same-root variant (u=v) and was not included in since_posted as it is tangential to Thomassen's conjecture. No paper was found that resolves the general conjecture.
Discussion
Thomassen [T] showed that, given a digraph $ D $ and two vertices $ u $ and $ v $ , deciding whether there are an out-branching rooted at $ u $ and an in-branching rooted at $ v $ which are arc-disjoint is NP-complete. In contrast, one can decide in polynomial time whether there are $ k $ arc-disjoint out-branchings with specified roots $ s_1, \dots , s_k $ (some of which may be identical). This is a consequence of Edmonds’ well known branching theorem [E] states that a digraph $ D $ has $ k $ arc-disjoint out-branchings rooted at some fixed vertex $ s $ if and only if there are $ k $ arc-disjoint paths from $ s $ to every other vertex of $ D $ . Bang-Jensen [B] proved this conjecture for tournaments. A similar question can be asked about arc-disjoint strongly connected spanning subdigraphs . Several related problems are mentioned in the survey of Bang-Jensen and Kriesell [BK].
Bibliography
-
[B]J. Bang-Jensen, Edge-disjoint in- and out-branching in tournaments and related path problems. J. Combin. Theory Ser. B 51 (1991), 1-23. -
[BK]J. Bang-Jensen, M. Kriesell, Disjoint sub(di)graphs in digraphs, Electronic Notes in Discrete Mathematics 34 (2009), 179-183. -
[E]J. Edmonds, Edge-disjoint branchings. In Combinatorial Algorithms, B. Rustin, ed., Acad. Press, New York (1973), 91-96. -
★
[T]C. Thomassen, Configurations in Graphs, Annals of The New York Acad. Sci. 555 (1989), 402-412.