Mixed-graph pseudo-dicut orientation threshold conjecture
Mixed-graph pseudo-dicut orientation threshold conjecture
Let be a mixed graph, with directed arcs and undirected edges . For , a pseudo dicut is when no directed arc enters . Its minimum pseudo dicut size is the smallest cardinality of a pseudo dicut.
Mixed-graph threshold orientation conjecture. There is a constant such that every mixed graph with minimum pseudo dicut size at least has an orientation satisfying
for every pseudo dicut .
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.