Mixed-graph pseudo-dicut orientation conjecture

About 3 years old · traced to

Let M=(V,E∪A)M=(V,E\cup A) be a mixed graph, where AA is the set of directed arcs and EE the set of undirected edges. For U⊂VU\subset V, a pseudo dicut is the edge set δE(U)\delta_E(U) such that no directed arc enters UU. An orientation E+E^+ of EE replaces every undirected edge by a directed edge. For an oriented cut, write δE++(U)\delta_{E^+}^+(U) and δE+−(U)\delta_{E^+}^-(U) for its outgoing and incoming edges.

Mixed-graph orientation conjecture. There is a constant k>2k>2 such that for every mixed graph M=(V,E∪A)M=(V,E\cup A), there is an orientation E+E^+ such that

∣δE++(U)∣,∣δE+−(U)∣≥⌊1k∣δE(U)∣⌋|\delta_{E^+}^+(U)|,|\delta_{E^+}^-(U)|\geq \left\lfloor\frac{1}{k}|\delta_E(U)|\right\rfloor

for every pseudo dicut δE(U)\delta_E(U).

This is proposed as an analogue of nowhere-zero flow methods for mixed graphs. The source notes that the counterexample to Edmonds–Giles implies k>2k>2, and gives no resolution.

References

Primary source

Gérard Cornuéjols, Siyue Liu and R. Ravi, “Approximately Packing Dijoins via Nowhere-Zero Flows”, arXiv:2311.04337 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.