A Min-Max Relation on Dicuts and Dijoins in Weighted Chordal Digraphs
Gérard Cornuéjols, Siyue Liu, R. Ravi · 2025
Read A Min-Max Relation on Dicuts and Dijoins in Weighted Chordal Digraphs by Gérard Cornuéjols, Siyue Liu, R. Ravi (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-10918.txt.
Introduction
In a directed network, a dicut is a set of arcs all crossing one way between two camps, and a dijoin is a set of arcs meeting every dicut. Gérard Cornuéjols, Siyue Liu, and Ravi study an old guess linking the two: that the lightest dicut weighs the same as the largest packing of dijoins. The guess was disproved in general, and its unweighted form is still open after decades.
For one family of networks, those whose underlying undirected graph is chordal, the three prove the guess true. Chordal graphs are built from overlapping cliques in a tree-like way. They also give a fast method, running in strongly polynomial time, that builds the matching packing. The result settles the question for a broad and useful graph family.
Catalog record
| CREATOR | Gérard Cornuéjols, Siyue Liu, R. Ravi |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 25 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-10918
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A Min-Max Relation on Dicuts and Dijoins in Weighted Chordal Digraphs Gérard Cornuéjols, Siyue Liu, R. Ravi Abstract In a digraph, a dicut is a cut where all the arcs cross in one direction. A dijoin is a subset of arcs that intersects every dicut. Edmonds and Giles conjectured that in a weighted digraph, the minimum weight of a dicut is equal to the maximum size of a packing of dijoins. This has been disproved. However, the unweighted version conjectured by Woodall remains open. We prove that the Edmonds-Giles conjecture is true if the underlying undirected graph is chordal. We also give a strongly polynomial-time algorithm to construct such a packing. 1 Introduction In a digraph D=(V,A) , for a proper node subset U\subsetneqq V,U\neq\emptyset , denote by \delta^{+}(U) and \delta^{-}(U) the arcs leaving and entering U , respectively. Let \delta(U):=\delta^{+}(U)\cup\delta^{-}(U) . A dicut is a set of arcs of the form \delta^{+}(U) such that \delta^{-}(U)=\emptyset . A dijoin is a set of arcs that intersects every dicut at least once. If D is a weighted digraph with arc weights w:A\rightarrow\mathbb{Z}_{+} , we say that (D,w) can pack k dijoins if there exist k dijoins J_{1},...,J_{k} such that no arc e is contained in more than w(e) of J_{1},...,J_{k} . In this case, J_{1},...,J_{k} is a packing of dijoins in (D,w) . Assume that the minimum weight of a dicut is \tau . Clearly, \tau is an upper bound on the maximum number of dijoins in a packing. Edmonds and Giles [ 9 ] conjectured that the other direction also holds true: Conjecture 1 (Edmonds-Giles) In a weighted digraph, the minimum weight of a dicut is equal to the maximum size of a packing of dijoins. Schrijver [ 17 ] disproved the above conjecture by providing a counterexample (see Figure 1 ). However, the unweighted version of the Edmonds-Giles conjecture, proposed by Woodall [ 21 ] , is still open. Woodall’s conjecture asserts that the minimum size of a dicut equals the maximum number of disjoint dijoins. There has been great interest in understanding when the Edmonds-Giles conjecture is true (e.g., [ 12 , 20 , 2 , 1 , 19 , 5 , 16 ] ), which could be an important stepping stone towards resolving Woodall’s conjecture. Despite many efforts, it is still not known whether there exists a packing of 2 dijoins in a weighted digraph when \tau is large enough [ 19 ] , in contrast to the existence of a packing of \left\lfloor\frac{\tau}{6}\right\rfloor dijoins in unweighted digraphs [ 7 ] . Abdi et al. [ 3 ] recently showed that the Edmonds-Giles conjecture is true when \tau=2 and the digraph induced by the arcs of weight w(e)\geq 1 is (weakly) connected, settling a conjecture of Chudnovsky et al. [ 5 ] . Abdi et al. [ 2 ] proved the Edmonds-Giles conjecture to be true when some parameter characterizing the “discrepancy" of a digraph takes several special values. Among the special cases where the Edmonds-Giles conjecture was proved to be true, probably the most well-known one is source-sink connected digraphs, where there is a directed path going from every source to every sink. This result was proved independently by Schrijver [ 18 ] , and Feofiloff and Younger [ 10 ] . Lee and Wakabayashi [ 13 ] proved that the conjecture also holds true for digraphs whose underlying graphs are series-parallel. Figure 1: Left: Schrijver’s counterexample to the Edmonds-Giles conjecture. The solid arcs have weight 1 and the dashed arcs have weight 0 . The minimum weight of a dicut equals 2 . Among all minimal dicuts, six have weight 2 such as D_{1}\supseteq\{1,1^{\prime}\} and D_{2}\supseteq\{1,1^{\prime\prime}\} , and four have weight 3 such as D_{3}\supseteq\{1,2,3\} and D_{4}\supseteq\{1^{\prime},2^{\prime\prime},3\} . One can verify that the solid arcs do not contain 2 disjoint dijoins. Right: a generalization of Schrijver’s example due to Younger. It extends to an infinite family with a ring of length 4k+2 and 2k+1 solid paths for k\in\mathbb{Z}_{\geq 1} . Younger extended Schrijver’s counterexample to an infinite family [ 20 ] (see Figure 1 ). Cornuéjols and Guenin gave two more counterexamples [ 6 ] . Williams [ 20 ] constructed more infinite classes, but defined a notion of minimality that reduces these counterexamples to the earlier known classes. We observe that all of the known counterexamples to the Edmonds-Giles conjecture have a large chordless cycle (actually of length at least 6 ). This motivates us to prove the following result. A graph is chordal if there is no chordless cycle of length more than 3 . Theorem 1.1 The Edmonds-Giles conjecture is true for digraphs whose underlying undirected graph is chordal. This result only depends on the underlying undirected graph, regardless of its orientation. Our proof constructs a packing of \tau dijoins in strongly polynomial time. Chordal graphs are perfect [ 11 ] , and in fact they are closely associated with the birth of perfect graph theory [ berge1960 ] . In the literature, chordal graphs are also referred to as triangulated graphs , or rigid-circuit graphs . Dirac [ 8 ] observed the following striking property of chordal graphs. In a graph, a vertex is called simplicial if its neighbors form a clique. Lemma 1 ( [ 8 ] ) Every chordal graph has a simplicial vertex. Moreover, after removing a simplicial vertex, the resulting graph remains chordal. We will use this result in our proof of Theorem 1.1 . Lemma 1 implies that one can recursively remove simplicial vertices. This process is called a perfect elimination scheme . Rose [ 15 ] showed that a graph is chordal if and only if it has a perfect elimination scheme. Rose, Lueker and Tarjan [ 14 ] showed how to find a perfect elimination scheme efficiently and how to recognize chordal graphs in linear time. Chordal graphs have other elegant characterizations. For example, Buneman [ 4 ] showed that a graph is chordal if and only if it is the intersection graph of a family of subtrees of a tree. 2 Proof of Theorem 1.1 Let D=(V,A) be a digraph whose underlying undirected graph is chordal and let w:A\rightarrow\mathbb{Z}_{\geq 0} be a weight function. Suppose the minimum weight of a dicut is \tau . Note that, if D contains a directed cycle C , the arcs in C do not belong to any dicut. Therefore no minimal dijoin of D contains an arc of C . Furthermore, after contracting all the arcs of C , the underlying graph remains chordal. It follows that we can assume w.l.o.g. that D has no directed cycle. 2.1 Removing a simplicial vertex By Lemma 1 , there exists a simplicial vertex v , and after removing v the underlying graph remains chordal. Let us begin with some observations. First, the neighbor set of v , denoted by N(v) , induces an acyclic tournament , that is, there is a total ordering v_{1},...,v_{k} of the nodes in N(v) such that v_{i}v_{j}\in A if and only if 1\leq i<j\leq k . This is because N(v) is a clique and there is no directed cycle. Moreover, observe that if vv_{i}\in A , then we must have vv_{j}\in A for every