Woodall's Conjecture

Woodall’s Dicut--Dijoin Conjecture

Definitions and mathematical statement

Shared notation.

Unless a section says otherwise, ${\mathbb{N}}=\{1,2,\ldots\}$, ${\mathbb{Z}}$ is the ring of integers, ${\mathbb{Q}},{\mathbb{R}},{\mathbb{C}}$ are the rational, real, and complex fields, $[N]=\{1,\ldots,\lfloor N\rfloor\}$, and $\log$ is the natural logarithm. For real functions of a parameter tending to infinity, $f\ll g$ and $f=O(g)$ mean $|f|\leq Cg$ eventually for some fixed $C$; $f\gg g$ reverses this comparison; $f=o(g)$ means $f/g\to0$; $f\sim g$ means $f/g\to1$; and $f\asymp g$ means both order bounds. A subscript on $O$ or $\ll$ specifies allowed constant dependence. The expression $n^{o(1)}$ in an upper bound means growth smaller than $n^\epsilon$ for each fixed $\epsilon>0$. Local definitions govern any exception, finite-field convention, or use of the same symbol for another object. An asymptotic claim is not automatically an effective algorithm.

For a vertex set $S$ in a finite digraph, a nonempty directed cut is $\delta^+(S)$ when $\delta^-(S)=\varnothing$. A dijoin is a set of arcs meeting every nonempty directed cut. For a digraph having such a cut, let $\tau$ be its minimum size. The conjecture asks for $\tau$ pairwise arc-disjoint dijoins. No arc weights are imposed. [S1] [S2]

Statement recorded in the supplied source.

Is the minimum dicut size equal to the maximum number of disjoint dijoins in a directed graph? [S1]

Scope and interpretation.

The archive’s informal background describes dijoins imprecisely. The cut-hitting definition above is the one in its cited mathematical sources; it is not a prescribed-pair path problem. [S1]

Residual task reported by the archive.

The embedded review $2026-08-17$ records: Close the constant-factor gap and prove or disprove the exact min--max relation. [S1]

Short English statement

Can the arcs of a digraph always contain as many pairwise disjoint directed-cut hitting sets as the size of its smallest directed cut?

Research attempt

Status and scope.

This attempt leaves Woodall's exact packing conjecture unresolved. Write $\mathcal D$ for the nonempty directed cuts, assume $\mathcal D\ne\varnothing$, and put $\tau=\min_{C\in\mathcal D}|C|$. Internal arcs of strongly connected components will be irrelevant; parallel arcs are kept as distinct arcs. The 2025 paper of Cornuéjols, Liu and Ravi proves a polynomial-time packing of at least $\lfloor\tau/6\rfloor$ dijoins. That theorem is an external benchmark, not derived by the elementary method below. Its weighted predecessor and the present unweighted conjecture must not be conflated. https://doi.org/10.1007/s00493-025-00159-x

The upper bound and the coloring formulation.

If $J_1,\ldots,J_k$ are disjoint dijoins, each meets a minimum cut $C$. Their intersections with $C$ are disjoint nonempty sets, so $k\leq|C|=\tau$. Conversely, color each arc with one of $k$ colors and require that every cut in $\mathcal D$ contain every color. Each color class is then a dijoin, and the classes are disjoint. A packing also gives such a coloring: color the arcs of $J_i$ with color $i$ and give any unused arcs arbitrary colors. Adding arcs never destroys the property of being a dijoin. Thus the target is exactly a polychromatic coloring of the directed-cut family with $\tau$ colors.

This formulation gives a precise finite certificate. Use variables $x_{a,i}\in\{0,1\}$ with $\sum_{i=1}^{\tau}x_{a,i}=1$ for every arc, and impose $\sum_{a\in C}x_{a,i}\geq1$ for every $C\in\mathcal D$ and every color $i$. There may be exponentially many cuts; writing these constraints is not a polynomial algorithm or a proof of feasibility.

Strong-component contraction.

If $\delta^-(S)=\varnothing$, no strongly connected component can meet both $S$ and its complement. Indeed, a path from a vertex outside $S$ to a vertex inside the same component must contain an arc entering $S$. Therefore $S$ is a union of whole components. Contract the components, remove internal arcs, and preserve each intercomponent arc individually. The contracted digraph is acyclic and its nonempty directed cuts are in bijection with those of the original graph as arc sets. In particular their minimum size is unchanged. Any coloring of the contracted arcs meeting all its cuts lifts to the original graph; internal arcs can be assigned freely. It is consequently sufficient to solve the problem for acyclic directed multigraphs. The reduction does not turn a dijoin into a directed path or require prescribed source-to-sink pairs.

An exact class: a tree of parallel bundles.

Suppose the underlying simple graph of the contracted digraph is a tree. For each tree edge $e$, let its $m_e\geq1$ parallel arcs all point in the same direction. Deleting that tree edge gives two components; take $S$ to be the component containing its tail. The corresponding directed cut consists of precisely that bundle, so $\tau\leq\min_e m_e$. Every nonempty directed cut consists of one or more whole bundles, and hence has size at least $\min_e m_e$. Thus \[ \tau=\min_e m_e. \] Color every bundle with all $\tau$ colors, placing at least one arc of each color in it; this is possible since $m_e\geq\tau$. Every nonempty directed cut contains a bundle and therefore all colors. This proves the conjecture for the entire class, with arbitrary tree orientation and arbitrary positive bundle sizes. The same argument works componentwise for a forest having at least one bundle. It also lifts through any strong-component expansion described above.

A probabilistic bound and its exact loss.

Let $M=|\mathcal D|$. Color the arcs independently and uniformly with $k\geq2$ colors. For a particular cut $C$ and color $i$, the probability that $C$ misses $i$ is $(1-1/k)^{|C|}\leq\exp(-\tau/k)$. There are $Mk$ bad events, so a coloring and hence $k$ disjoint dijoins exist whenever \[ Mk\exp(-\tau/k)<1. \] No independence between different bad events is needed for this union bound. The criterion may yield a packing when $\tau$ is large relative to $k\log(Mk)$, but it does not reach $k=\tau$: its displayed upper bound then becomes $M\tau/e$. This failure does not imply a packing fails to exist. For a single bundle of $\tau$ parallel arcs, assigning each arc a different color is an explicit optimum even though random coloring has a coupon-collection obstruction. A sharp argument must coordinate colors rather than pay separately for every missing color on every cut. The cited $\lfloor\tau/6\rfloor$ theorem achieves a much stronger guarantee than this size-dependent union bound.

Verification and residual task.

The exact companion check enumerates all labeled oriented graphs on at most four vertices, lists their nonempty directed cuts, and searches for a $\tau$-coloring satisfying the cut constraints whenever such cuts exist. This tests the reformulation on every graph in that finite range. It is not a verification for arbitrary multigraphs, and the tree-of-bundles theorem instead has the uniform proof given above. For an arbitrary acyclic digraph, directed cuts can overlap across many routes and need not contain an entire independently colorable bundle. A global coloring construction that survives all those overlaps is the missing step. Status: unresolved.

Sources

• S1 ULAM.AI, UnsolvedMath, supplied problems.json, record 1445 (GRAPH-058), statement and background. The embedded literature-review date is 2026-08-17; that is the archive’s review date, not a fresh certification. Dataset landing page: https://huggingface.co/datasets/ulamai/UnsolvedMath.

• S2 G. Cornuéjols, S. Liu and R. Ravi, Approximately Packing Dijoins via Nowhere-Zero Flows, Combinatorica 45 $2025$, Article 32,

  \nolinkurl{doi:10.1007/s00493-025-00159-x.}

  https://doi.org/10.1007/s00493-025-00159-x. Bibliographic information from the supplied record.

• S3 J. Pascal Gollin et al., Disjoint dijoins for classes of dicuts in finite and infinite digraphs, 2022. https://doi.org/10.5070/C62359180. Bibliographic information from the supplied record.