[Model] UndirectedTwoCommodityIntegralFlow

[isPANN]

---

name: Problem
about: Propose a new problem type
title: "[Model] UndirectedTwoCommodityIntegralFlow"
labels: model
assignees: ''

Motivation

UNDIRECTED TWO-COMMODITY INTEGRAL FLOW (P115) from Garey & Johnson, A2 ND39. An NP-complete problem that extends the directed two-commodity integral flow to undirected graphs, where flow on each edge can go in either direction but each commodity must choose a single direction per edge. Notable for remaining NP-complete with unit capacities, yet becoming polynomial when all capacities are even (a rare parity-dependent complexity dichotomy).

Associated reduction rules:

• As source: None in current set.
• As target: R60: DIRECTED TWO-COMMODITY INTEGRAL FLOW -> UNDIRECTED TWO-COMMODITY INTEGRAL FLOW

Definition

Name: UndirectedTwoCommodityIntegralFlow
Canonical name: UNDIRECTED TWO-COMMODITY INTEGRAL FLOW
Reference: Garey & Johnson, Computers and Intractability, A2 ND39

Mathematical definition:

INSTANCE: Graph G = (V,E), specified vertices s_1, s_2, t_1, and t_2, a capacity c(e) ∈ Z^+ for each e ∈ E, requirements R_1,R_2 ∈ Z^+.
QUESTION: Are there two flow functions f_1,f_2: {(u,v),(v,u): {u,v} ∈ E} → Z_0^+ such that
(1) for all {u,v} ∈ E and i ∈ {1,2}, either f_i((u,v)) = 0 or f_i((v,u)) = 0,
(2) for each {u,v} ∈ E,
max{f_1((u,v)),f_1((v,u))} + max{f_2((u,v)),f_2((v,u))} ≤ c({u,v}),
(3) for each v ∈ V − {s_1,s_2,t_1,t_2} and i ∈ {1,2}, flow f_i is conserved at v, and
(4) for i ∈ {1,2}, the net flow into t_i under flow f_i is at least R_i?

Variables

• Count: 4|E| (for each edge {u,v} and each commodity i in {1,2}: variables f_i((u,v)) and f_i((v,u))).
• Per-variable domain: {0, 1, ..., c(e)} for each directed version of edge e. Subject to antisymmetry: for each commodity i, at most one of f_i((u,v)), f_i((v,u)) is nonzero.
• Meaning: Each variable represents the integer flow of a specific commodity in a specific direction along an edge. The joint capacity constraint limits the total flow (from both commodities) on each edge. A valid configuration satisfies antisymmetry, joint capacity, conservation for each commodity, and both requirements.

Schema (data type)

Type name: UndirectedTwoCommodityIntegralFlow
Variants: None (single variant; problem is always on an undirected graph with SimpleGraph).

Field	Type	Description
graph	SimpleGraph	Undirected graph G = (V, E) using the codebase's standard SimpleGraph type (petgraph-based). Vertex count and edge list are derived from the graph.
capacities	Vec<u64>	Capacity c(e) for each edge (indexed by edge index in the graph)
source_1	usize	Source vertex s_1 for commodity 1
sink_1	usize	Sink vertex t_1 for commodity 1
source_2	usize	Source vertex s_2 for commodity 2
sink_2	usize	Sink vertex t_2 for commodity 2
requirement_1	u64	Flow requirement R_1 for commodity 1
requirement_2	u64	Flow requirement R_2 for commodity 2

Size fields (for overhead expressions): num_vertices (from graph.node_count()), num_edges (from graph.edge_count())

Notes:

• This is a satisfaction (decision) problem: Metric = bool, implementing SatisfactionProblem.
• The graph is stored as SimpleGraph (not generic over graph type) since the problem is defined on general undirected graphs without special structure constraints.
• NP-complete even with unit capacities (c(e) = 1 for all e).
• Polynomial when all capacities are even.
• The fractional (non-integral) version is solvable in polynomial time.
• Antisymmetry constraint: each commodity can only send flow in one direction per edge.

Complexity

• Best known exact algorithm: The problem is NP-complete (Even, Itai, and Shamir, 1976). No sub-exponential exact algorithm is known. A brute-force approach enumerates flow assignments: for each edge and each commodity, choose a direction and flow amount. With unit capacities, the search space is O(5^|E|) (each edge can carry: nothing, commodity 1 left, commodity 1 right, commodity 2 left, commodity 2 right). For general capacities, the complexity is O(∏_e (c(e)+1)^4) before pruning by conservation constraints.
• Complexity string: "5^num_edges" (unit-capacity brute-force upper bound; no better exact algorithm known).
• NP-completeness: Proved by Even, Itai, and Shamir (1976) via reduction from DIRECTED TWO-COMMODITY INTEGRAL FLOW. Remains NP-complete with unit capacities.
• Polynomial cases:
  • All capacities even: polynomial (Even, Itai, and Shamir, 1976).
  • Non-integral flows allowed: polynomial (solvable by LP or specialized algorithms).
• References:
  • S. Even, A. Itai, A. Shamir (1976). "On the complexity of timetable and multicommodity flow problems". SIAM J. Comput. 5, pp. 691-703.

Extra Remark

Full book text:

INSTANCE: Graph G = (V,E), specified vertices s_1, s_2, t_1, and t_2, a capacity c(e) ∈ Z^+ for each e ∈ E, requirements R_1,R_2 ∈ Z^+.
QUESTION: Are there two flow functions f_1,f_2: {(u,v),(v,u): {u,v} ∈ E} → Z_0^+ such that
(1) for all {u,v} ∈ E and i ∈ {1,2}, either f_i((u,v)) = 0 or f_i((v,u)) = 0,
(2) for each {u,v} ∈ E,
max{f_1((u,v)),f_1((v,u))} + max{f_2((u,v)),f_2((v,u))} ≤ c({u,v}),
(3) for each v ∈ V − {s_1, s_2, t_1, t_2} and i ∈ {1,2}, flow f_i is conserved at v, and
(4) for i ∈ {1,2}, the net flow into t_i under flow f_i is at least R_i?
Reference: [Even, Itai, and Shamir, 1976]. Transformation from DIRECTED TWO-COMMODITY INTEGRAL FLOW.
Comment: Remains NP-complete even if c(e) = 1 for all e ∈ E. Solvable in polynomial time if c(e) is even for all e ∈ E. Corresponding problem with non-integral flows allowed can be solved in polynomial time.

Note: The original book text uses "v ∈ V − {s,t}" in condition (3), which appears to be shorthand. The correct exclusion set for this problem is {s_1, s_2, t_1, t_2} (all four terminal vertices), as shown in the definition above.

How to solve

• It can be solved by (existing) bruteforce. The variable domains are finite ({0, ..., c(e)} per directed edge per commodity), so exhaustive enumeration is possible, though exponential.
• It can be solved by reducing to integer programming.
• Other: Formulate as an ILP: for each edge {u,v} and commodity i, introduce integer variables f_i_uv, f_i_vu >= 0 with binary direction indicators. Constraints: antisymmetry (at most one direction per commodity per edge), joint capacity, conservation, and requirements. Standard ILP solvers can handle moderate instances.

Example Instance

Instance 1 (YES):
Graph with 6 vertices {0=s_1, 1=s_2, 2, 3, 4=t_1, 5=t_2} and 8 edges (all capacity 1):

• e_0 = {0,2}, e_1 = {0,3}, e_2 = {1,2}, e_3 = {1,3}
• e_4 = {2,4}, e_5 = {2,5}, e_6 = {3,4}, e_7 = {3,5}

Requirements: R_1 = 1, R_2 = 1.

Solution:

• Commodity 1: flow on e_0 (0->2) = 1, flow on e_4 (2->4) = 1. Path: s_1 -> 2 -> t_1.
• Commodity 2: flow on e_3 (1->3) = 1, flow on e_7 (3->5) = 1. Path: s_2 -> 3 -> t_2.
• Joint capacity: e_0: 1+0=1<=1, e_3: 0+1=1<=1, e_4: 1+0=1<=1, e_7: 0+1=1<=1. Others: 0<=1.
• Conservation: vertex 2: commodity 1 in=1, out=1; commodity 2: 0. vertex 3: commodity 1: 0; commodity 2 in=1, out=1.
• Requirements met: R_1=1, R_2=1. Answer: YES.

Instance 2 (NO):
Graph with 4 vertices {0=s_1, 1=s_2, 2, 3} where t_1=3, t_2=3, and 3 edges (all capacity 1):

• e_0 = {0,2}, e_1 = {1,2}, e_2 = {2,3}

Requirements: R_1 = 1, R_2 = 1.

• Both commodities need to route 1 unit to vertex 3. Both must use edge e_2={2,3}. Joint capacity on e_2: max flow from commodity 1 + max flow from commodity 2 <= 1. But both need >= 1 unit through this edge. f_1 + f_2 >= 2 > 1 = c(e_2). Answer: NO.

Instance 3 (YES, even capacities -- polynomial case):
Same graph as Instance 2 but c(e_2) = 2.

• Commodity 1: e_0 (0->2)=1, e_2 (2->3)=1. Commodity 2: e_1 (1->2)=1, e_2 (2->3)=1.
• Joint capacity on e_2: 1+1=2<=2. Answer: YES (and solvable in polynomial time since c(e_2) is even).

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem not yet in the reduction graph
Non-trivial	✅ Pass	Distinct feasibility constraints (multicommodity flow with antisymmetry + joint capacity) from all 24 existing problems
Correctness	⚠️ Warn	Reference verified, but complexity bound is a rough brute-force estimate rather than a best-known exact algorithm
Well-written	⚠️ Warn	Minor notation inconsistency in book text; brute-force solver unchecked without explanation

Overall: 2 passed, 0 failed, 2 warnings

---

Usefulness

Pass. UndirectedTwoCommodityIntegralFlow does not exist in the codebase (checked via pred show). The problem is a classic NP-complete flow problem from Garey & Johnson (A2 ND39) with an interesting parity-dependent complexity dichotomy (NP-complete with unit capacities, polynomial with even capacities). This makes it a valuable addition.

One concern: the only associated reduction rule listed is R60 (Directed Two-Commodity Integral Flow → Undirected), and the directed variant also does not exist yet. This means the problem would initially be an orphan node in the reduction graph. This is acceptable but worth noting — the directed variant should ideally be added first or simultaneously.

Non-trivial

Pass. This problem involves multicommodity integral flow with antisymmetry constraints, joint capacity sharing between commodities, and flow conservation — a fundamentally different structure from all existing problems in the codebase. The nearest existing problems are graph-based (MIS, MaxCut, etc.) or algebraic (ILP, QUBO), none of which model multicommodity flow semantics.

Correctness

Warn. The reference is verified and accurate:

• Paper exists: S. Even, A. Itai, A. Shamir (1976). "On the Complexity of Timetable and Multicommodity Flow Problems." SIAM J. Comput. 5(4), pp. 691–703. DOI: 10.1137/0205048.
• NP-completeness claim: Confirmed — the paper proves NP-completeness for both directed and undirected two-commodity integral flow.
• Unit capacities: Confirmed — remains NP-complete with c(e) = 1 for all e.
• Even capacities polynomial: Confirmed — polynomial-time solvable when all capacities are even.
• Fractional version polynomial: Confirmed.

Warning on complexity bound: The issue states the best known exact algorithm as "brute-force: O(5^|E|)." This is not a best-known exact algorithm from the literature — it is a rough upper bound on naive enumeration. For the declare_variants! macro, a more precise bound should be cited. If no sub-exponential exact algorithm is known, the brute-force bound should at least be stated precisely (e.g., accounting for flow conservation constraints that reduce the search space).

Well-written

Warn. The issue is generally well-structured and follows the template, but has minor issues:

1. Notation inconsistency in Extra Remark: The "Full book text" section has condition (3) referencing "v ∈ V − {s,t}" but the problem has four terminal vertices s_1, s_2, t_1, t_2 (not just s and t). The issue's own definition section correctly uses {s_1, s_2, t_1, t_2}. This appears to be a direct transcription of the book text, which may have a typo or use shorthand — but it should be flagged for clarity.

2. Brute-force solver unchecked: The "How to solve" section leaves brute-force unchecked without explanation. Given that the variables section describes a finite domain {0, ..., c(e)} for each variable, brute-force enumeration is technically possible (though exponential). It should either be checked, or an explanation should be given for why it was unchecked.

3. Six "⚠️ Unverified" markers: The issue acknowledges these are AI-generated sections. While transparent, implementers should verify these before implementation.

4. Examples are good: Three well-constructed instances (YES, NO, and polynomial-case YES) with step-by-step verification. Instance 2 (NO) provides a clear bottleneck argument.

5. Schema is reasonable for a satisfaction problem with Metric = bool.

Recommendations

• Consider adding this problem simultaneously with DirectedTwoCommodityIntegralFlow so the R60 reduction can be implemented, avoiding an orphan node.
• For the complexity bound, investigate whether there exists a better exact algorithm than naive brute-force (e.g., ILP-based approaches or fixed-parameter tractability results parameterized by treewidth).
• Fix the "v ∈ V − {s,t}" in the book text transcription to "v ∈ V − {s_1, s_2, t_1, t_2}" for consistency, or add a note that the book text is quoted verbatim.
• Check or explain the brute-force solver option.

[isPANN]

Changelog (2026-03-13):

• Schema: Use SimpleGraph instead of raw edge list — Replaced num_vertices: usize + edges: Vec<(usize, usize)> with a single graph: SimpleGraph field, consistent with how other graph problems in the codebase store their input (e.g., MaximumIndependentSet). Vertex count and edge list are derived from the graph via node_count() / edge_count().
• Kept 5^num_edges complexity string as-is (unit-capacity brute-force bound).

[isPANN]

Changelog (fix-issue-batch)

• Added Size fields line: num_vertices (from graph.node_count()), num_edges (from graph.edge_count())
• Removed redundant note about num_vertices/num_edges (now covered by Size fields line)
• Kept complexity string "5^num_edges" as-is (brute-force bound, no better exact algorithm known)