[Model] UndirectedFlowLowerBounds

[isPANN]

---

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

Motivation

UNDIRECTED FLOW WITH LOWER BOUNDS (P113) from Garey & Johnson, A2 ND37. A fundamental NP-complete problem notable for being strongly NP-complete even when non-integral flows are allowed. This stands in sharp contrast to directed flow with lower bounds, which is polynomial-time solvable. The problem demonstrates that the combination of undirected edges and lower bounds creates inherent computational hardness.

Associated reduction rules:

• As source: Potential: UndirectedFlowLowerBounds → IntegerLinearProgramming (natural ILP formulation via binary direction indicators).
• As target: R58: SATISFIABILITY -> UNDIRECTED FLOW WITH LOWER BOUNDS

Definition

Name: UndirectedFlowLowerBounds

Canonical name: UNDIRECTED FLOW WITH LOWER BOUNDS
Reference: Garey & Johnson, Computers and Intractability, A2 ND37

Mathematical definition:

INSTANCE: Graph G = (V,E), specified vertices s and t, capacity c(e) ∈ Z^+ and lower bound l(e) ∈ Z_0^+ for each e ∈ E, requirement R ∈ Z^+.
QUESTION: Is there a flow function f: {(u,v),(v,u): {u,v} ∈ E} → Z_0^+ such that
(1) for all {u,v} ∈ E, either f((u,v)) = 0 or f((v,u)) = 0,
(2) for each e = {u,v} ∈ E, l(e) ≤ max{f((u,v)),f((v,u))} ≤ c(e),
(3) for each v ∈ V − {s,t}, flow is conserved at v, and
(4) the net flow into t is at least R?

Variables

• Count: 2|E| (two variables per undirected edge: one for each direction (u,v) and (v,u)).
• Per-variable domain: {0, 1, ..., c(e)} for each direction of edge e.
• Meaning: For each undirected edge {u,v}, exactly one of f((u,v)) and f((v,u)) is nonzero (antisymmetry constraint). The nonzero value must lie between the lower bound l(e) and the capacity c(e). A valid configuration satisfies flow conservation at all non-terminal vertices and achieves net flow into t of at least R.

Schema (data type)

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

Field	Type	Description
num_vertices	usize	Number of vertices
edges	Vec<(usize, usize)>	Undirected edges {u, v}
capacities	Vec<u64>	Upper bound c(e) for each edge
lower_bounds	Vec<u64>	Lower bound l(e) for each edge
source	usize	Source vertex s
sink	usize	Sink vertex t
requirement	u64	Flow requirement R (must be ≥ 1 per the definition, since R ∈ Z^+)

Notes:

• This is a satisfaction (decision) problem: Metric = bool, implementing SatisfactionProblem.
• Flow on undirected edges is antisymmetric: for each edge, flow goes in only one direction.
• The lower bound constraint means every edge must carry at least l(e) units of flow (if l(e) > 0).
• Strongly NP-complete even with non-integral flows allowed.
• The directed version (with lower and upper bounds) is polynomial-time solvable.

Complexity

• Best known exact algorithm: The problem is strongly NP-complete (Itai, 1978). No sub-exponential exact algorithm is known. Brute-force approach: enumerate all 2^|E| possible flow direction assignments for the edges; for each assignment, checking feasibility (whether valid flow values exist satisfying bounds and conservation) reduces to a polynomial-time directed flow problem. This gives a worst-case bound of 2^num_edges (suppressing polynomial factors).
• Complexity string: 2^num_edges
• NP-completeness: Proved by Itai (1978) via reduction from SATISFIABILITY. Strongly NP-complete even with non-integral flows.
• Contrast with directed case: For directed graphs, flow with lower and upper bounds can be solved in polynomial time using standard max-flow techniques (Ford and Fulkerson, 1962).
• References:
  • A. Itai (1978). "Two commodity flow". Journal of the ACM 25(4), pp. 596-611. (Also as Technion technical report, 1977.)
  • L. R. Ford and D. R. Fulkerson (1962). "Flows in Networks". Princeton University Press.

Extra Remark

Full book text:

INSTANCE: Graph G = (V,E), specified vertices s and t, capacity c(e) ∈ Z^+ and lower bound l(e) ∈ Z_0^+ for each e ∈ E, requirement R ∈ Z^+.
QUESTION: Is there a flow function f: {(u,v),(v,u): {u,v} ∈ E} → Z_0^+ such that
(1) for all {u,v} ∈ E, either f((u,v)) = 0 or f((v,u)) = 0,
(2) for each e = {u,v} ∈ E, l(e) ≤ max{f((u,v)),f((v,u))} ≤ c(e),
(3) for each v ∈ V − {s,t}, flow is conserved at v, and
(4) the net flow into t is at least R?
Reference: [Itai, 1978]. Transformation from SATISFIABILITY.
Comment: Problem is NP-complete in the strong sense, even if non-integral flows are allowed. Corresponding problem for directed graphs can be solved in polynomial time, even if we ask that the total flow be R or less rather than R or more [Ford and Fulkerson, 1962] (see also [Lawler, 1976a]). The analogous DIRECTED M-COMMODITY FLOW WITH LOWER BOUNDS problem is polynomially equivalent to LINEAR PROGRAMMING for all M ≥ 2 if non-integral flows are allowed [Itai, 1978].

How to solve

• It can be solved by (existing) bruteforce.
• It can be solved by reducing to integer programming.
• Other: Formulate as an ILP: for each edge {u,v}, introduce variables f_uv, f_vu >= 0 with f_uv * f_vu = 0 (or use binary direction indicators), enforce lower and upper bounds, flow conservation, and requirement R. The bilinear constraint f_uv * f_vu = 0 can be linearized using big-M or binary variables.

Example Instance

Instance 1 (YES):
Graph with 6 vertices {0=s, 1, 2, 3, 4, 5=t} and 7 edges:

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

Requirement R = 3.

Solution:

• e_0: flow s->1, f=2. e_1: flow s->2, f=1. e_2: flow 1->3, f=1. e_3: flow 2->3, f=1. e_4: flow 1->4, f=1. e_5: flow 3->t, f=2. e_6: flow 4->t, f=1.
• Lower bounds: e_0: 2>=1, e_1: 1>=1, e_4: 1>=1, e_6: 1>=1. All satisfied.
• Conservation: vertex 1: in=2, out=1+1=2. vertex 2: in=1, out=1. vertex 3: in=1+1=2, out=2. vertex 4: in=1, out=1.
• Net flow into t: 2+1 = 3 >= 3. Answer: YES.

Instance 2 (NO):
Graph with 4 vertices {0=s, 1, 2, 3=t} and 4 edges:

• e_0 = {0,1}: l=2, c=2
• e_1 = {0,2}: l=2, c=2
• e_2 = {1,3}: l=1, c=1
• e_3 = {2,3}: l=1, c=1

Requirement R = 2.

Why infeasible: The lower bound on e_0 forces at least 2 units of flow into vertex 1. However, the only edge out of vertex 1 toward t is e_2, which has capacity 1. Flow conservation at vertex 1 requires outflow = inflow = 2, but at most 1 unit can leave via e_2. No reverse flow on e_0 helps (antisymmetry: if flow goes s→1, no flow goes 1→s on the same edge). The same bottleneck applies to vertex 2 via e_1 and e_3. Answer: NO.

References

• [Itai, 1978]: [Itai1978] Alon Itai (1978). "Two commodity flow". Journal of the ACM 25(4), pp. 596-611. (Also as Technion technical report, 1977.)
• [Ford and Fulkerson, 1962]: [Ford1962] L. R. Ford and D. R. Fulkerson (1962). "Flows in Networks". Princeton University Press, Princeton, NJ.
• [Lawler, 1976a]: [Lawler1976a] Eugene L. Lawler (1976). "Combinatorial Optimization: Networks and Matroids". Holt, Rinehart and Winston, New York.

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	⚠️ Warn	Novel problem, but no planned reduction rules as source; only one target rule cited
Non-trivial	✅ Pass	Distinct feasibility constraints (undirected antisymmetric flow + lower bounds) from all existing problems
Correctness	⚠️ Warn	References verified but some claims need clarification; complexity bound not specific enough for implementation
Well-written	❌ Fail	Inconsistent naming, missing concrete complexity expression, flawed Example Instance 2

Overall: 1 passed, 2 warnings, 1 failed

---

Usefulness

The problem UndirectedFlowLowerBounds does not currently exist in the codebase — this is a novel addition. The problem is a classic entry from Garey & Johnson (A2 ND37) and is notable for the contrast between undirected (NP-complete) and directed (polynomial) flow with lower bounds.

However, the issue lists no reduction rules where this problem is the source, and only one target rule (SAT -> UndirectedFlowLowerBounds). Without outgoing reductions, this problem would be a leaf node in the reduction graph with limited utility for the project's core purpose of enabling problem transformations. A planned reduction from this problem to another (e.g., to ILP) would strengthen the motivation.

The brute-force solver checkbox is unchecked, and the ILP formulation described involves a bilinear constraint (f_uv * f_vu = 0) that requires careful linearization — this is noted but not fully spelled out.

Non-trivial

Pass. This problem has genuinely distinct feasibility constraints from all 24 existing problems in the codebase. The combination of undirected edge antisymmetry (flow in only one direction per edge), mandatory lower bounds on flow, flow conservation, and a flow requirement threshold is not captured by any existing model. It is not a variant or renaming of an existing problem.

Correctness

References verified:

• Itai (1978), "Two-commodity flow", JACM 25(4), pp. 596-611 — Confirmed to exist. This paper does prove that finding feasible flow in an undirected graph with lower and upper bounds is NP-complete, even for a single commodity. The citation year in the issue oscillates between 1977 and 1978; the JACM publication is 1978 (the 1977 date refers to the Technion technical report).
• Ford and Fulkerson (1962), "Flows in Networks" — A well-known classic. The claim that directed flow with lower and upper bounds is polynomial-time solvable is correct.
• Garey & Johnson (1979) — Already in the project bibliography. The problem is listed under A2 as a network design problem.

Concerns:

• The issue states the problem is "strongly NP-complete even if non-integral flows are allowed" — this matches the G&J comment text verbatim. However, the issue does not provide a concrete worst-case complexity expression suitable for declare_variants!. The brute-force bound O((2C)^|E|) is pseudo-polynomial (depends on capacity magnitudes), not a pure combinatorial bound. Since this is a satisfaction problem, the complexity section needs a concrete exponential expression in terms of the problem's structural parameters (e.g., number of edges).

Well-written

Fail. Several issues need to be addressed:

4a. Inconsistent naming:

• The issue title says UndirectedFlowWithLowerBounds but the Name field in the Definition section says UndirectedFlowLowerBounds. These must match. Per project naming conventions (no optimization prefix for non-optimization problems), a consistent name should be chosen.

4b. Missing concrete complexity expression:

• The Complexity section describes the search space as O((2C)^|E|) but does not provide a concrete expression suitable for the declare_variants! macro. Since this is a strongly NP-complete problem, there should be a bound in terms of structural parameters only (not capacity values). At minimum, note that no sub-exponential exact algorithm is known and provide a brute-force bound like 2^(num_edges * log2(max_capacity)) or similar.

4c. Example Instance 2 is flawed:

• The issue author initially constructs a 4-vertex "NO" instance, then realizes mid-explanation that it is actually a YES instance ("this seems feasible... Actually this IS feasible"). The author then revises the instance with different parameters. This self-correction within the issue body is confusing and suggests the example was not carefully verified. A clean, correct NO instance should be provided.

4d. Symbol consistency:

• The Variables section says "2|E| variables" but the Schema section does not have a field that directly represents the flow variables — instead it stores edges, capacities, and lower bounds. The mapping from schema fields to the variable space should be made explicit.
• The requirement field uses u64 type, but the mathematical definition specifies R ∈ Z^+ (positive integers). Using u64 means R=0 is representable but not valid per the definition — this should be noted or the type should be clarified.

4e. How to Solve — incomplete ILP formulation:

• The ILP formulation mentions "bilinear constraint f_uv * f_vu = 0 can be linearized using big-M or binary variables" but does not spell out the linearization. Since this is the primary proposed solver path, a complete formulation would be more useful.

Recommendations

• Settle on a single consistent name (suggest UndirectedFlowLowerBounds to match the Definition section, and update the title).
• Provide a clean, verified NO instance for Example 2 — remove the mid-stream self-correction.
• Add a concrete complexity expression for declare_variants!, even if it is just a brute-force bound.
• Consider adding at least one outgoing reduction rule to make this problem more useful in the reduction graph (e.g., UndirectedFlowLowerBounds -> ILP is natural given the ILP solver path).
• Spell out the ILP linearization for the antisymmetry constraint to make the solver section implementable.

[GiggleLiu]

Fix-issue changelog

• Fixed inconsistent naming: YAML title UndirectedFlowWithLowerBounds → UndirectedFlowLowerBounds to match Definition Name field
• Added concrete complexity string 2^num_edges (brute-force over edge direction assignments)
• Standardized Itai citation year to 1978 (JACM publication), noting 1977 Technion tech report
• Replaced flawed Example Instance 2 (had mid-stream self-correction) with clean 4-vertex bottleneck NO instance
• Added potential outgoing rule (→ ILP) to Associated reduction rules
• Annotated requirement field with R ≥ 1 constraint per mathematical definition

Applied by /fix-issue.