Mixed-graph pseudo-dicut orientation threshold conjecture

Let M=(V,EA)M=(V,E\cup A) be a mixed graph, with directed arcs AA and undirected edges EE. For UVU\subset V, a pseudo dicut is δE(U)\delta_E(U) when no directed arc enters UU. Its minimum pseudo dicut size is the smallest cardinality of a pseudo dicut.

Mixed-graph threshold orientation conjecture. There is a constant k>2k>2 such that every mixed graph with minimum pseudo dicut size at least kk has an orientation E+E^+ satisfying

δE++(U),δE+(U)1|\delta_{E^+}^+(U)|,|\delta_{E^+}^-(U)|\geq 1

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

This is presented as a weaker question than the preceding mixed-graph orientation conjecture; the source 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.