Conforti-Cornuéjols conjecture on the MFMC property

Definitions and mathematical statement

A finite clutter $\mathcal C$ is a family of nonempty subsets of a finite ground set $V$, none containing another. Its incidence matrix $A$ has rows indexed by $V$ and columns by the members of $\mathcal C$. For each $w\in\mathbb Z_{\ge0}^V$, consider the dual pair \[ \min\{w^Tx:A^Tx\ge\mathbf1,\ x\ge0\},\qquad \max\{\mathbf1^Ty:Ay\le w,\ y\ge0\}. \] The max-flow min-cut (MFMC) property says that both programs have integral optimal solutions for every such $w$.

Deleting an element removes all clutter members containing it. Contracting an element removes it from every member and retains only inclusion-minimal resulting sets. Repeated operations produce minors. The packing property requires $\tau(\mathcal D)=\nu(\mathcal D)$ in every minor $\mathcal D$ with no empty member. Here $\tau$ is the least size of a set meeting every member, and $\nu$ is the largest number of pairwise disjoint members; both are zero for an empty family.

The Conforti--Cornuéjols conjecture asserts that the packing property implies MFMC. The reverse implication is part of the standard equivalent formulation. Unit-weight packing equality in every nontrivial minor must therefore force integral optimal certificates for arbitrary nonnegative integral weights on the original clutter, not merely unweighted equality there.

Short English statement

Does matching-cover equality in every clutter minor force the full integral max-flow min-cut property for every integral weight vector?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3000019 (AMR-029-0019), AMR Open Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Egres Open - List of open problems, Open-problem page: Conforti-Cornuéjols conjecture on the MFMC property. Original source indexed by AMR-029-0019. https://oldlemon.cs.elte.hu/egres/open/List_of_open_problems.
• S3 EGRES Open, Conforti-Cornuéjols conjecture on the MFMC property. Individual source page and explanatory remarks. https://lemon.cs.elte.hu/egres/open/Conforti-Cornu%C3%A9jols_conjecture_on_the_MFMC_property.