3 papers
math.CO2026
A Min-Max Relation on Dicuts and Dijoins in Weighted Chordal Digraphs
Gérard Cornuéjols, Siyue Liu, R. Ravi
In a digraph, a dicut is a cut where all the arcs cross in one direction. A dijoin is a subset of arcs that intersects every dicut. Edmonds and Giles conjectured that in a weighted…
math.CO2025
Approximately Packing Dijoins via Nowhere-Zero Flows
Gérard Cornuéjols, Siyue Liu, R. Ravi
In a digraph, a dicut is a cut where all the arcs cross in one direction. A dijoin is a subset of arcs that intersects each dicut. Woodall conjectured in 1976 that in every digraph…
cs.DS2025
Minimum Cost Nowhere-zero Flows and Cut-balanced Orientations
Karthekeyan Chandrasekaran, Siyue Liu, R. Ravi
Flows and colorings are disparate concepts in graph algorithms -- the former is tractable while the latter is intractable. Tutte introduced the concept of nowhere-zero flows to uni…