Mixed-graph pseudo-dicut orientation conjecture

Let M=(V,EA)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 UVU\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,EA)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.

Sources & referencesView supporting material

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.