Strong orientation of a connected graph for a crossing family

Ahmad Abdi; Mahsa Dalirrooyfard; Meike Neuwohner

Strong orientation of a connected graph for a crossing family

T0 review · 0 major / 6 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Every connected graph admits a strong orientation for any crossing family whose cuts have size at least two.

desk verdict Strong, clean proof of the main disjoint dijoins conjecture; the only terse spots are two standard reductions that a referee should ask to have expanded. read the letter →

arxiv 2411.13202 v1 pith:Y6TBLBLR submitted 2024-11-20 math.CO

Ahmad Abdi , Mahsa Dalirrooyfard , Meike Neuwohner This is my paper · ORCID

classification math.CO MSC 05C2090C27

keywords crossingfamilystrongorientationdijoinEdmonds-GilesconjectureWoodall'ssubmodularflowtotaldualintegrality0-1weights

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper proves that every connected graph $G=(V,E)$ carries a strong orientation for any crossing family $\mathcal{C}$ over $V$ whose cuts all have size at least two: one can direct the edges so that every set in $\mathcal{C}$ receives at least one outgoing and one incoming arc. This is Theorem 1, and it is the missing step that confirms the main conjecture of [3] on disjoint dijoins. As Theorem 2, the paper derives that in any weighted digraph with 0/1 weights, minimum dicut weight at least two, and weakly bridge-connected weight-1 arcs, there are two disjoint dijoins lying inside the weight-1 arcs. If correct, this pins down the counterexample of [9] to the Edmonds-Giles conjecture: the nonzero-weight arcs in a minimal counterexample with minimum dicut weight two must be disconnected.

What carries the argument

The load-bearing objects are crossing families and the crossing-submodular functions $f_i(U)=|\delta^+_D(U)|-1$ defined on $\mathcal{C}$ and on the complementary family $\{V\setminus U: U\in\mathcal{C}\}$. The orientation problem is encoded as the system $y(\delta^+(U))-y(\delta^-(U))\le f_i(U)$ for all $i=1,2$ and all $U$ in the respective family. This system is the intersection of two submodular flow systems and is therefore box-TDI by a standard theorem quoted as Theorem 4 in the paper; the generalized set-covering form of the inequalities is what permits rounding an integral solution to a 0/1 solution, and the transshipment theorem quoted as Theorem 3 supplies the integral solution once a vertex potential $x'$ with $x'(V)=0$ is exhibited.

What would settle it

A single connected graph $G$ with a crossing family $\mathcal{C}$ satisfying $|\delta_G(U)| \ge 2$ for all $U\in\mathcal{C}$ but admitting no strong orientation would refute Theorem 1; equivalently, a weighted digraph with 0/1 weights, minimum dicut weight 2, and weakly bridge-connected weight-1 arcs that has no two disjoint dijoins inside those arcs would refute Theorem 2.

Watch

Extended reading notes

Core claim

Theorem 1 states that a connected graph admits a strong orientation for a crossing family provided every cut in the family has at least two edges. The proof works by orienting the graph arbitrarily and asking whether some subset of arcs can be flipped so that each member of the family ends up with both an outgoing and an incoming arc. This is modelled as a 0/1 feasibility problem over a system of generalized set-covering inequalities, which is shown to be integral through the intersection of two submodular-flow systems. An integral solution is obtained from a feasible vertex-potential vector via a transshipment, and a rounding argument turns it into a 0/1 solution, i.e., an actual re-orientation. Theorem 2 then follows by an induction whose base case is exactly the tree case of Theorem 1, converting the strong orientation into two disjoint dijoins contained in the weight-1 arcs.

Load-bearing premise

The induction proving Theorem 2 rests on two reduction steps—contracting a cycle in the weight-1 arcs and deleting a vertex with no incident weight-1 arc—that the paper asserts are 'readily checked' but does not prove in detail; the entire dijoin result depends on both steps preserving the minimum dicut weight and the dijoin property.

Editorial extensions

If this is right

Theorem 2 verifies the main conjecture of [3] on disjoint dijoins for weakly bridge-connected weight-1 arcs.
In every minimal counterexample to the Edmonds-Giles conjecture with minimum dicut weight 2, the nonzero-weight arcs must be disconnected; the weakly bridge-connected case is now settled.
The result extends the earlier theorem of [12] from subgraphs whose components are all 2-edge-connected to the weakly bridge-connected case.
The proof shows that Theorem 1 is exactly the $\tau=2$ case of a proposed strengthening-set partition conjecture, a conjecture that would imply Woodall's conjecture.
The Appendix A example shows that the natural extension to two weakly connected components does not preserve integrality of the corresponding linear system, so that case requires new machinery.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

A likely algorithmic reading of the proof is that the strong orientation can be found in polynomial time: the underlying system is box-TDI, so a 0/1 solution can be obtained by linear programming, though the paper does not discuss complexity.
One could test whether the crossing condition is necessary by building a non-crossing set family with all cuts of size at least two on a connected graph and checking whether a strong orientation always exists; a counterexample would show that crossing is the essential hypothesis.
Written out in full, the two 'readily checked' reduction lemmas in the induction might yield an explicit construction of the two dijoins from the orientation, turning Theorem 2 into a constructive packing statement.
The equivalence in Section 6 suggests that the same orientation theorem likely applies to other problems that can be phrased as finding 0/1 points in submodular-flow systems with set-covering inequalities.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

You should read this one before it gets too deeply into the pipeline. The paper proves the main conjecture of Chudnovsky, Edwards, Kim, Scott and Seymour on disjoint dijoins: every weighted digraph with 0/1 weights, all dicuts weight at least 2, and weight-1 arcs weakly bridge-connected, admits two disjoint dijoins in the weight-1 arcs. That alone is a substantive result. But the real engine is Theorem 1, a clean strong-orientation statement for crossing families: if every set in the family has edge cut size at least 2, there is an orientation where each set has both an outgoing and an incoming arc. That theorem is new and is proved through an intersection of two crossing-submodular systems, invoking box-TDI and an integral transshipment argument. The proof of Theorem 1 is compact and sound: the 0/1 rounding step, the integrality step, and the transshipment step all check out. I tried to find a gap and did not. The paper is honest about what the method does not do, with a whole section on why the two-component case fails and an explicit fractional example in the appendix.

The only soft spot is Section 4, where the two induction reductions are described as 'readily checked' and not written out fully. They are load-bearing for Theorem 2. I went through them: contracting a cycle works because each dicut of the contracted digraph lifts to a dicut that contains either all or none of the cycle, and if it splits the cycle then each of the two half-cycles contributes an outgoing arc; deleting a vertex with no weight-1 incident arcs works because any new dicut in the reduced digraph can be lifted to one in the original with no larger weight. Both are correct as stated, but a referee should ask for them to be expanded, since the paper's main result depends on them.

Who gets value: anyone working on dijoins, dicuts, or strong orientations, and people who like seeing box-TDI used as a hammer. The citation pattern is appropriate — the paper does not oversell its novelty, and the self-citation [1] is only tangential. I would send this to a strong referee rather than desk-reject, and I expect it to land in a good combinatorics journal after the reductions in Section 4 are written out properly.

Referee Report

0 major / 6 minor

Summary. The paper proves two theorems in combinatorial optimization. Theorem 1 states that for a connected graph G=(V,E) and a crossing family C over V with |δ_G(U)| ≥ 2 for all U in C, there is an orientation of G in which every set in C has both an outgoing and an incoming arc. The proof reduces the problem to finding a 0-1 solution of a system of submodular-flow inequalities, obtains an integral solution via the box-TDI theorem for intersections of two crossing-submodular systems, and then rounds it to a 0-1 solution. Theorem 2 states that in a weighted digraph with 0/1 weights, minimum dicut weight at least 2, and weight-1 arcs forming a weakly bridge-connected subdigraph, there exist two disjoint dijoins contained in the weight-1 arcs. This is derived from Theorem 1 by induction, with two reduction steps (cycle contraction and deletion of a vertex not incident to weight-1 arcs) and a base case in which the weight-1 arcs form a spanning tree. The paper also includes a discussion of the difficulties in extending the approach to two weakly connected components and an appendix with a fractional example showing that a certain polytope is not integral.

Significance. If the results are correct, Theorem 1 resolves a conjecture of Chudnovsky, Edwards, Kim, Scott, and Seymour on disjoint dijoins, and Theorem 2 provides a unified proof of previously known planar and caterpillar cases as well as an extension to weakly bridge-connected weight-1 subdigraphs. The proof of Theorem 1 is clean and elegant: it formulates the orientation problem as a submodular-flow feasibility problem, uses the box-TDI property of the intersection of two crossing-submodular systems to obtain an integral transshipment, and then rounds it to a 0-1 solution. The paper is self-contained modulo standard theorems from combinatorial optimization, has no fitted parameters, and includes an explicit counterexample in the appendix, which is a sign of careful work. The main limitation, as the authors themselves state, is that the induction in Theorem 2 relies on two reductions that are asserted as 'readily checked' rather than proved in full; these reductions are routine and correct, but a skeptical reader would want them written out.

minor comments (6)

[Section 4, Steps 1 and 2] The two claims introduced by 'It can be readily checked' are load-bearing for the induction in Theorem 2 and should be expanded into brief proofs. In Step 1, please explain why any dicut of D contains either all or none of the contracted cycle (otherwise an arc of the cycle would enter the dicut), and why the lifted dicuts in D/C have the same outgoing weight. In Step 2, please spell out the case distinction for a dicut U of D' based on whether U contains an out-neighbor of v0; if it does not, U is already a dicut of D, and if it does, then all in-neighbors of v0 must lie in U and U∪{v0} is a dicut of D with the same outgoing weight.
[Section 3, Step 3] In the displayed derivation of x'(U) ≤ f_i(U), the inequality |δ(U)| ≥ 2 is used for U in C2 as well as for U in C1. This is true because U = V\W for some W in C and |δ(U)| = |δ(W)| ≥ 2, but it is not stated explicitly; please add a short sentence to make the step fully transparent.
[Section 4, Step 3] The term 'cycle' in 'Suppose A1 contains a cycle C' and in 'A1 contains no cycle' should be clarified to mean a cycle in the underlying undirected graph. If 'cycle' meant a directed cycle, the claim that the underlying graph is a tree would be false, since a digraph with no directed cycle can still have an undirected cycle (e.g., a directed acyclic orientation of a triangle).
[Appendix A] There are several typographical errors in the list of tight constraints: some closing parentheses are missing, for example 'x⋆({2, 3, 4, 9, 10} = f1(...)' and 'x⋆({0, 1, 2, 3, 4, 7, 8, 9, 10} = f1(...)', and 'Schriver' should be 'Schrijver'.
[Section 5] The phrase 'at most two weakly bridge-connected components' appears to be a typo for 'at most two weakly connected components', based on the subsequent sentence that mentions a spanning forest with two weakly connected components. Please correct this.
[Section 3, final note] The sentence 'surprisingly, this system is TDI [1]' cites the authors' own paper [1] as a side remark. This is fine, but it is not needed for the main proof and could be omitted to avoid any appearance of relying on an unpublished result.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the proof is self-contained modulo standard external theorems, and the only self-citation is a non-load-bearing remark.

full rationale

The derivation of Theorem 1 is not circular. The proof constructs a feasible solution x' for the system x(V) = 0, x(U) ≤ f_i(U), which is a special case of the intersection of two crossing-submodular base systems; Theorem 4, an external box-TDI result from Schrijver and Frank, guarantees an integral solution. Then Theorem 3, an external transshipment theorem, provides an integral transshipment y, and the thresholding argument converts it to a 0-1 solution. Each step is justified by an explicit inequality in the paper, and no target result is assumed. The only self-citation, reference [1], appears in the closing remark 'surprisingly, this system is TDI [1]' and is not used in the proof of either theorem; moreover, the integrality needed in the proof is already supplied by Theorem 4. The two reductions in Section 4 are asserted as 'readily checked' rather than fully expanded, but they are standard contraction and deletion arguments, not circular ones: they reduce the theorem to smaller instances of the same theorem, which is legitimate induction. Appendix A honestly exhibits a fractional polytope for a two-component extension, showing that the authors do not hide a failure behind an assumption. No fitted parameters, empirical predictions, or imported uniqueness claims occur. Therefore the paper receives a circularity score of 0.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The paper introduces no fitted constants and no new postulated objects. The central claim rests on standard theorems in combinatorial optimization and on two induction reductions that are stated without full proof. The authors are transparent that the method cannot handle two weakly connected components, and the appendix provides a fractional polytope example to justify that limitation.

assumptions (5)

standard math Theorem 3: the b-transshipment existence condition and integrality (Schrijver, Corollary 11.2f).
Used in Section 3, Step 3, to pass from an integral x to an integral flow y in a weakly connected digraph.
standard math Theorem 4: the intersection of two crossing-submodular base systems is box-TDI (Schrijver, Frank).
Used in Section 3, Step 3, to obtain an integral solution x to the system x(V)=0 and x(U) ≤ f_i(U) for two crossing families.
standard math The functions U → |δ^+_D(U)| - 1 and U → |δ^-_D(U)| - 1 are crossing-submodular.
Needed to apply Theorem 4; this is a standard property of directed cut functions.
domain assumption Contracting any vertex set preserves the minimum dicut weight, and the cycle-uncontracting partition preserves dijoin status.
Used in Section 4, Step 1, of the proof of Theorem 2. The authors state it as readily checked; it is standard but not fully expanded.
domain assumption Deleting a vertex not incident to weight-1 arcs and replacing it with zero-weight arcs from in-neighbors to out-neighbors preserves the property that a dijoin of the reduced digraph is a dijoin of the original.
Used in Section 4, Step 2, of the proof of Theorem 2. The proof sketch says it can be readily checked.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Strong orientation of a connected graph for a crossing family." pith.science (2026). https://pith.science/paper/Y6TBLBLR

@misc{pith2026241113202,
  author       = {Pith},
  title        = {Pith review of: Strong orientation of a connected graph for a crossing family},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/Y6TBLBLR}},
  note         = {Machine review of arXiv:2411.13202}
}

abstract

Given a connected graph $G=(V,E)$ and a crossing family $\mathcal{C}$ over ground set $V$ such that $|\delta_G(U)|\geq 2$ for every $U\in \mathcal{C}$, we prove there exists a strong orientation of $G$ for $\mathcal{C}$, i.e., an orientation of $G$ such that each set in $\mathcal{C}$ has at least one outgoing and at least one incoming arc. This implies the main conjecture in Chudnovsky et al. (Disjoint dijoins. Journal of Combinatorial Theory, Series B, 120:18--35, 2016). In particular, in every minimal counterexample to the Edmonds-Giles conjecture where the minimum weight of a dicut is $2$, the arcs of nonzero weight must be disconnected.

Figures

Figures reproduced from arXiv: 2411.13202 by the authors.

**Figure 2.** Schrijver’s example (left) and an example where (6 [PITH_FULL_IMAGE:figures/full_fig_p010_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

14 extracted references · 13 canonical work pages

[1]

Combinatorica, 2024

Ahmad Abdi, G´ erard Cornu´ ejols, and Giacomo Zambelli.Arc connectivity and submod- ular ﬂows in digraphs. Combinatorica, 2024. doi:10.1007/s00493-024-00108-0

work page doi:10.1007/s00493-024-00108-0 2024
[2]

On packing dijoins in digraphs and weighted digraphs

Ahmad Abdi, G´ erard Cornu´ ejols, and Michael Zlatin. On packing dijoins in digraphs and weighted digraphs. SIAM Journal on Discrete Mathematics , 37(4):2417–2461, 2023. doi:10.1137/22M1506511

work page doi:10.1137/22m1506511 2023
[3]

Disjoint dijoins

Maria Chudnovsky, Katherine Edwards, Ringi Kim, Alex Sc ott, and Paul Sey- mour. Disjoint dijoins. Journal of Combinatorial Theory, Series B , 120:18–35, 2016. doi:10.1016/j.jctb.2016.04.002

work page doi:10.1016/j.jctb.2016.04.002 2016
[4]

On dijoins.Discrete Mathematics, 243(1):213– 216, 2002

G´ erard Cornu´ ejols and Bertrand Guenin. On dijoins.Discrete Mathematics, 243(1):213– 216, 2002. doi:10.1016/S0012-365X(01)00209-6

work page doi:10.1016/s0012-365x(01)00209-6 2002
[5]

G´ erard Cornu´ ejols, Siyue Liu, and R. Ravi. Approximately packing dijoins via nowhere- zero ﬂows. In Jens Vygen and Jaros/suppress law Byrka, editors,Integer Programming and Com- binatorial Optimization . Springer, 2024. doi:10.1007/978-3-031-59835-7_6

work page doi:10.1007/978-3-031-59835-7_6 2024
[6]

A min-max relation for submodular functions on graphs

Jack Edmonds and Rick Giles. A min-max relation for submodular functions on graphs. In P.L. Hammer, E.L. Johnson, B.H. Korte, and G.L. Nemhauser, editors, Studies in Integer Programming, volume 1 of Annals of Discrete Mathematics , pages 185–204. Elsevier, 1977. doi:10.1016/S0167-5060(08)70734-9

work page doi:10.1016/s0167-5060(08)70734-9 1977
[7]

Connections in Combinatorial Optimization

Andr´ as Frank. Connections in Combinatorial Optimization . Oxford Lec- ture Series in Mathematics and Its Applications. Oxford Uni versity Press, 2011. doi:10.1016/j.dam.2011.09.003

work page doi:10.1016/j.dam.2011.09.003 2011
[8]

Observations on Woodall’s conjec ture

Alexander Schrijver. Observations on Woodall’s conjec ture. Accessed online at https://homepages.cwi.nl/~lex/files/woodall.pdf

work page

Show all 14 references

[9]

A counterexample to a conjecture o f Edmonds and Giles

Alexander Schrijver. A counterexample to a conjecture o f Edmonds and Giles. Discrete Mathematics, 32(2):213–214, 1980. doi:10.1016/0012-365X(80)90057-6

1980 doi
[10]

Combinatorial Optimization: Polyhedra and Eﬃciency Volume 1

Alexander Schrijver. Combinatorial Optimization: Polyhedra and Eﬃciency Volume 1. Springer Science & Business Media, 2003

2003
[11]

Combinatorial Optimization: Polyhedra and Eﬃciency Volume 2

Alexander Schrijver. Combinatorial Optimization: Polyhedra and Eﬃciency Volume 2. Springer Science & Business Media, 2003

2003
[12]

Visualizing, ﬁnding a nd packing dijoins

Bruce Shepherd and Adrian Vetta. Visualizing, ﬁnding a nd packing dijoins. In D. Avis, A. Hertz, and O. Marcotte, editors, Graph Theory and Combinatorial Optimization , chap- ter 8, pages 219–254. Springer Verlag. doi:10.1007/0-387-25592-3_8. 8

doi
[13]

Packing directed joins

Aaron Williams. Packing directed joins. Master’s thes is, University of Waterloo, 2004. URL: http://hdl.handle.net/10012/1024

2004
[14]

Douglas R. Woodall. Menger and K¨ onig systems. In Youse f Alavi and Don R. Lick, editors, Theory and Applications of Graphs , pages 620–635. Springer, 1978. doi:10.1007/BFb0070416. A An example where (6) is not integral. Fig. 2b shows a weighted digraph ( D, w) for which (6) ...

1978 doi

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.

[1] [1]

Combinatorica, 2024

Ahmad Abdi, G´ erard Cornu´ ejols, and Giacomo Zambelli.Arc connectivity and submod- ular ﬂows in digraphs. Combinatorica, 2024. doi:10.1007/s00493-024-00108-0

work page doi:10.1007/s00493-024-00108-0 2024

[2] [2]

On packing dijoins in digraphs and weighted digraphs

Ahmad Abdi, G´ erard Cornu´ ejols, and Michael Zlatin. On packing dijoins in digraphs and weighted digraphs. SIAM Journal on Discrete Mathematics , 37(4):2417–2461, 2023. doi:10.1137/22M1506511

work page doi:10.1137/22m1506511 2023

[3] [3]

Disjoint dijoins

Maria Chudnovsky, Katherine Edwards, Ringi Kim, Alex Sc ott, and Paul Sey- mour. Disjoint dijoins. Journal of Combinatorial Theory, Series B , 120:18–35, 2016. doi:10.1016/j.jctb.2016.04.002

work page doi:10.1016/j.jctb.2016.04.002 2016

[4] [4]

On dijoins.Discrete Mathematics, 243(1):213– 216, 2002

G´ erard Cornu´ ejols and Bertrand Guenin. On dijoins.Discrete Mathematics, 243(1):213– 216, 2002. doi:10.1016/S0012-365X(01)00209-6

work page doi:10.1016/s0012-365x(01)00209-6 2002

[5] [5]

G´ erard Cornu´ ejols, Siyue Liu, and R. Ravi. Approximately packing dijoins via nowhere- zero ﬂows. In Jens Vygen and Jaros/suppress law Byrka, editors,Integer Programming and Com- binatorial Optimization . Springer, 2024. doi:10.1007/978-3-031-59835-7_6

work page doi:10.1007/978-3-031-59835-7_6 2024

[6] [6]

A min-max relation for submodular functions on graphs

Jack Edmonds and Rick Giles. A min-max relation for submodular functions on graphs. In P.L. Hammer, E.L. Johnson, B.H. Korte, and G.L. Nemhauser, editors, Studies in Integer Programming, volume 1 of Annals of Discrete Mathematics , pages 185–204. Elsevier, 1977. doi:10.1016/S0167-5060(08)70734-9

work page doi:10.1016/s0167-5060(08)70734-9 1977

[7] [7]

Connections in Combinatorial Optimization

Andr´ as Frank. Connections in Combinatorial Optimization . Oxford Lec- ture Series in Mathematics and Its Applications. Oxford Uni versity Press, 2011. doi:10.1016/j.dam.2011.09.003

work page doi:10.1016/j.dam.2011.09.003 2011

[8] [8]

Observations on Woodall’s conjec ture

Alexander Schrijver. Observations on Woodall’s conjec ture. Accessed online at https://homepages.cwi.nl/~lex/files/woodall.pdf

work page