Delphi.science

Cut Conditions, Integrality, and Obstructions for Directed Multiflows

Source: arxiv.org/abs/2611.12330

Srinwanti Debgupta, Martin Skutella, Philipp Warode

arXivarxiv/2611.12330Nov 9, 2026math.COscore 0

In contrast to the max-flow/min-cut theorem for single-commodity flows, the cut condition is necessary but not sufficient for the existence of directed multiflows, even with only two commodities. Poremba and Shepherd (IPCO 2023) conjecture that the cut condition is sufficient for all capacities and demands on a directed two-commodity topology if and only if it contains neither of two specific topologies as a relevant minor. We prove this conjecture. As a consequence, the fractional and integral flow-cut gaps of every directed two-commodity topology coincide and are either 1 or 2. We then…

JSONText

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2611.12330
curl -X POST /api/v1/records/arxiv/2611.12330/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.12330/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'