Arc-disjoint in- and out-branchings rooted at the same vertex in compositions of digraphs
Pith reviewed 2026-05-25 20:01 UTC · model grok-4.3
The pith
Every strong digraph composition with each part of size at least two has arc-disjoint in- and out-branchings rooted at any vertex.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
Every strong digraph composition Q = T[H1, …, Ht] in which ni ≥ 2 for each i possesses a good pair at every vertex. The lower bound ni ≥ 2 is tight. When T is semicomplete the compositions that admit a good pair at a given root are characterized by a set of forbidden configurations on the parts and the arcs of T; the characterization extends the 1995 result of Bang-Jensen and Huang for quasi-transitive digraphs and implies a polynomial-time algorithm.
What carries the argument
The composition Q = T[H1, …, Ht] in which the vertex sets of the Hi become the parts of Q and all possible arcs run from every vertex in Hi to every vertex in Hj whenever ui uj is an arc of T; a good pair is a pair of arc-disjoint branchings, one in-branching and one out-branching, sharing the same root.
If this is right
- Strong compositions with parts of size at least two always contain good pairs rooted at every vertex.
- The size-two condition on the parts is necessary; there exist strong compositions with a part of size one that have no good pair at certain vertices.
- When the base digraph is semicomplete, membership in the class of compositions possessing a good pair at a given vertex is decidable in polynomial time.
- The characterization for semicomplete base digraphs directly generalizes the earlier characterization known for quasi-transitive digraphs.
Where Pith is reading between the lines
- The existence result may extend to other hierarchical products of digraphs that preserve strong connectivity and complete bipartite links between modules.
- Polynomial-time recognition for the semicomplete case suggests that similar structural characterizations could be sought for other base classes such as tournaments or transitive digraphs.
- Good pairs supply two arc-disjoint spanning arborescences; the result therefore guarantees a form of arc-resilient reachability inside modular directed networks.
Load-bearing premise
The whole composition Q must be strong and the arcs between distinct parts must form complete bipartite digraphs in both directions whenever the corresponding base arc exists.
What would settle it
A concrete strong composition with some ni = 1 that lacks a good pair at some vertex, or an explicit strong composition with all ni ≥ 2 that lacks a good pair at some vertex.
read the original abstract
A digraph $D=(V, A)$ has a good pair at a vertex $r$ if $D$ has a pair of arc-disjoint in- and out-branchings rooted at $r$. Let $T$ be a digraph with $t$ vertices $u_1,\dots , u_t$ and let $H_1,\dots H_t$ be digraphs such that $H_i$ has vertices $u_{i,j_i},\ 1\le j_i\le n_i.$ Then the composition $Q=T[H_1,\dots , H_t]$ is a digraph with vertex set $\{u_{i,j_i}\mid 1\le i\le t, 1\le j_i\le n_i\}$ and arc set $$A(Q)=\cup^t_{i=1}A(H_i)\cup \{u_{ij_i}u_{pq_p}\mid u_iu_p\in A(T), 1\le j_i\le n_i, 1\le q_p\le n_p\}.$$ When $T$ is arbitrary, we obtain the following result: every strong digraph composition $Q$ in which $n_i\ge 2$ for every $1\leq i\leq t$, has a good pair at every vertex of $Q.$ The condition of $n_i\ge 2$ in this result cannot be relaxed. When $T$ is semicomplete, we characterize semicomplete compositions with a good pair, which generalizes the corresponding characterization by Bang-Jensen and Huang (J. Graph Theory, 1995) for quasi-transitive digraphs. As a result, we can decide in polynomial time whether a given semicomplete composition has a good pair rooted at a given vertex.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper investigates the existence of arc-disjoint in- and out-branchings rooted at the same vertex (a 'good pair') in digraph compositions Q = T[H_1, ..., H_t]. For arbitrary base digraph T it claims that every strong such Q with each n_i >= 2 admits a good pair at every vertex; the n_i >= 2 condition is stated to be tight. For semicomplete T the paper gives a characterization of compositions admitting a good pair and shows this can be decided in polynomial time. The results are positioned as generalizations of earlier work on quasi-transitive digraphs.
Significance. A correct version of the arbitrary-T result would modestly extend the literature on branchings in composed digraphs and supply a new algorithmic handle for the semicomplete case. The polynomial-time decision procedure would be a concrete practical contribution if the underlying characterization is accurate.
major comments (1)
- [Abstract / Main theorem for arbitrary T] Abstract (and the corresponding theorem for arbitrary T): the claim that every strong composition Q with n_i >= 2 for all i has a good pair at every vertex is false when t=1. In this case Q coincides with H_1, so the statement asserts that every strong digraph on at least two vertices has a good pair at every vertex. The directed 3-cycle C_3 is a counter-example: it is strong with n_1=3>=2, yet at root r=1 the unique out-branching uses arcs 1->2 and 2->3 while any in-branching uses 3->1 and 2->3, so the two branchings necessarily share the arc 2->3.
Simulated Author's Rebuttal
We thank the referee for identifying an important oversight in the statement of our main result for arbitrary base digraphs T. We agree that the claim as written is incorrect when t=1 and will revise the manuscript to correct this. The remainder of the paper, including the semicomplete case and the polynomial-time algorithm, is unaffected.
read point-by-point responses
-
Referee: [Abstract / Main theorem for arbitrary T] Abstract (and the corresponding theorem for arbitrary T): the claim that every strong composition Q with n_i >= 2 for all i has a good pair at every vertex is false when t=1. In this case Q coincides with H_1, so the statement asserts that every strong digraph on at least two vertices has a good pair at every vertex. The directed 3-cycle C_3 is a counter-example: it is strong with n_1=3>=2, yet at root r=1 the unique out-branching uses arcs 1->2 and 2->3 while any in-branching uses 3->1 and 2->3, so the two branchings necessarily share the arc 2->3.
Authors: We agree that the statement is false for t=1, as the C_3 counter-example correctly demonstrates. The intended result applies to compositions where the base digraph T has at least two vertices (i.e., t >= 2). When t=1 the composition is simply an arbitrary strong digraph H_1, which need not admit a good pair. We will revise the abstract, the theorem statement, the introduction, and all related text to explicitly require t >= 2. The tightness of the n_i >= 2 condition (shown via examples with t >= 2) remains valid and will be retained. This is a statement error only; the proof for t >= 2 is unaffected. revision: yes
Circularity Check
No circularity; existence proof uses independent graph-theoretic arguments on compositions
full rationale
The paper establishes existence of good pairs via direct constructions and reductions to known results on branchings in strong digraphs and compositions, without any self-referential definitions, fitted parameters renamed as predictions, or load-bearing self-citations. The main theorem for arbitrary T and the characterization for semicomplete T rest on standard digraph decomposition arguments that cite external prior work (e.g., Bang-Jensen and Huang) whose validity is independent of the present claims. No equation or step reduces the target existence statement to an input by construction.
Axiom & Free-Parameter Ledger
axioms (1)
- standard math Standard definitions and basic properties of digraphs, in-/out-branchings, strong connectivity, and the composition operation Q = T[H1,...,Ht].
Reference graph
Works this paper leans on
-
[1]
Bang-Jensen, Edge-disjoint in- and out-branchings i n tournaments and related path problems, J
J. Bang-Jensen, Edge-disjoint in- and out-branchings i n tournaments and related path problems, J. Combin. Theory Ser. B, 51(1), 1 991, 1–23
-
[2]
Bang-Jensen, Locally semicomplete digraphs and gene ralizations, in Classes of Directed Graphs (J
J. Bang-Jensen, Locally semicomplete digraphs and gene ralizations, in Classes of Directed Graphs (J. Bang-Jensen and G. Gutin, eds.), Springer, 2018
work page 2018
-
[3]
J. Bang-Jensen and G. Gutin, Paths and cycles in extended and de- composable digraphs. Discrete Math. 164 (1997) 5–19
work page 1997
-
[4]
J. Bang-Jensen and G. Gutin, Digraphs: Theory, Algorith ms and Ap- plications, 2nd Edition, Springer, London, 2009
work page 2009
-
[5]
J. Bang-Jensen and G. Gutin, Basic terminology, notatio n and results, in Classes of Directed Graphs (J. Bang-Jensen and G. Gutin, eds.), Springer, 2018
work page 2018
-
[6]
J. Bang-Jensen, G. Gutin and A. Yeo, Arc-disjoint strong spanning subgraphs of semicomplete compositions, arXiv:1903.1222 5v1 [cs.DM]
-
[7]
J. Bang-Jensen and J. Huang, Quasi-transitive digraphs , J. Graph The- ory, 20(2), 1995, 141–161
work page 1995
-
[8]
J. Bang-Jensen and J. Huang, Decomposing locally semico mplete di- graphs into strong spanning subgraphs, J. Combin. Theory Se r. B, 102, 2012, 701–714
work page 2012
-
[9]
J. Bang-Jensen and J. Huang, Arc-disjoint in- and out-br anchings rooted at the same vertex in locally semicomplete digraphs, J. Graph Theory, 77, 2014, 278–298
work page 2014
-
[10]
J. Bang-Jensen and A. Yeo, The minimum spanning strong s ubdigraph problem is fixed parameter tractable. Discrete Appl. Math., 156:2924– 2929, 2008
work page 2008
-
[11]
Edmonds, Edge-disjoint branchings, in Combinatorial Algorithms (B
J. Edmonds, Edge-disjoint branchings, in Combinatorial Algorithms (B. Rustin ed.), Academic Press, 1973, 91–96
work page 1973
-
[12]
H. Galeana-S´ anchez and C. Hern´ andez-Cruz, Quasi-transitive digraphs and their extensions, in Classes of Directed Graphs (J. Bang-Jensen and G. Gutin, eds.), Springer, 2018
work page 2018
-
[13]
Gutin, Polynomial algorithms for finding Hamiltonia n paths and cycles in quasi-transitive digraphs
G. Gutin, Polynomial algorithms for finding Hamiltonia n paths and cycles in quasi-transitive digraphs. Australasian J. Comb in. 10, 1994, 231–236
work page 1994
- [14]
-
[15]
Hammack, Digraphs Products, in Classes of Directed Graphs (J
R.H. Hammack, Digraphs Products, in Classes of Directed Graphs (J. Bang-Jensen and G. Gutin, eds.), Springer, 2018. 7
work page 2018
-
[16]
Y. Sun, G. Gutin, J. Ai, Arc-disjoint strong spanning su bgraphs in compositions and products of digraphs, Discrete Math. 342( 8), 2019, 2297–2305. 8
work page 2019
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.