[Model] PathConstrainedNetworkFlow

[isPANN]

---

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

Motivation

PATH CONSTRAINED NETWORK FLOW (P110) from Garey & Johnson, ND34. A variant of network flow where flow must be routed along a given collection of specified s-t paths (rather than being decomposed freely). This constraint makes the problem NP-complete even when all arc capacities equal 1. The non-integral version is equivalent to linear programming, but the integrality gap question (whether the best integral flow matches the best rational flow) is itself NP-complete.

Associated reduction rules:

• As source: None found in the current rule set.
• As target: R55: 3SAT -> PATH CONSTRAINED NETWORK FLOW

Definition

Name: PathConstrainedNetworkFlow

Canonical name: PATH CONSTRAINED NETWORK FLOW (also: Integer Multicommodity Flow on Prescribed Paths, Unsplittable Flow on Paths)
Reference: Garey & Johnson, Computers and Intractability, ND34

Mathematical definition:

INSTANCE: Directed graph G = (V,A), specified vertices s and t, a capacity c(a) ∈ Z^+ for each a ∈ A, a collection P of directed paths in G, and a requirement R ∈ Z^+.
QUESTION: Is there a function g: P -> Z_0^+ such that if f: A -> Z_0^+ is the flow function defined by f(a) = Sum_{p in P(a)} g(p), where P(a) is the set of all paths in P containing the arc a, then f is such that
(1) f(a) <= c(a) for all a ∈ A,
(2) for each v ∈ V - {s,t}, flow is conserved at v, and
(3) the net flow into t is at least R?

Variables

• Count: |P| integer variables (one per path in the collection P), representing the amount of flow sent along each path.
• Per-variable domain: {0, 1, ..., M_p} where M_p = min_{a in p} c(a) is the bottleneck capacity of path p -- the maximum flow that can be sent along path p without violating any arc capacity on that path alone.
• Meaning: The variable assignment encodes the flow decomposition. g(p) is the amount of flow sent along path p. A satisfying assignment has total flow (sum over all paths of g(p)) into t at least R, while respecting all arc capacity constraints.

Dims

[M_1+1, M_2+1, ..., M_{|P|}+1] where M_i = min_{a in p_i} c(a) is the bottleneck capacity of the i-th path. For the common all-capacities-1 case: [2; num_paths] (binary variables).

Schema (data type)

Type name: PathConstrainedNetworkFlow
Variants: None (directed graph with integer types)

Field	Type	Description
num_vertices	usize	Number of vertices
arcs	Vec<(usize, usize)>	Directed arcs (u, v) in A
source	usize	Index of source vertex s
sink	usize	Index of sink vertex t
capacities	Vec<u64>	Capacity c(a) for each arc
paths	Vec<Vec<usize>>	Collection P of directed s-t paths (each path is a sequence of arc indices)
requirement	u64	Flow requirement R

Notes:

• This is a satisfaction (decision) problem: Metric = bool, implementing SatisfactionProblem.
• Each path in P is a directed path from s to t in G.
• The flow on each arc is the sum of flows on all paths using that arc.
• Flow conservation is automatically satisfied when flow is decomposed into s-t paths.
• The key constraint is integrality of the path flows g(p).

Size Fields

Getter name	Meaning
num_vertices	Number of vertices
num_arcs	Number of arcs
num_paths	Number of prescribed paths
max_capacity	Maximum arc capacity max_a c(a)
requirement	Flow requirement R

Complexity

• Best known exact algorithm: NP-complete, so no polynomial-time algorithm is known. Brute-force: enumerate all non-negative integer assignments to |P| paths such that arc capacities are satisfied and total flow >= R. This is bounded by O((max_capacity + 1)^num_paths).
• Concrete bound for declare_variants!: "(max_capacity + 1)^num_paths"
• Special cases: With non-integral flows allowed, equivalent to linear programming (polynomial). With all c(a) = 1, still NP-complete.
• NP-completeness: NP-complete by transformation from 3SAT. Private communication from Prömel to Garey & Johnson (1979), cited as [Promel, 1978] in G&J ND34. Published proof: Büsing & Stiller (2011).
• Related problems: The integrality gap problem (does the best rational flow exceed the best integral flow?) is also NP-complete.
• References:
  • H.J. Prömel (1978). Private communication to Garey & Johnson. Transformation from 3SAT.
  • C. Büsing, S. Stiller (2011). "Line planning, path constrained network flow and inapproximability." Networks, 57(1):106-113.
  • C. Barnhart, C.A. Hane, P.H. Vance (2000). "Using branch-and-price-and-cut to solve origin-destination integer multicommodity flow problems." Operations Research, 48(2):318-326.

Extra Remark

Full book text:

INSTANCE: Directed graph G = (V,A), specified vertices s and t, a capacity c(a) ∈ Z^+ for each a ∈ A, a collection P of directed paths in G, and a requirement R ∈ Z^+.
QUESTION: Is there a function g: P -> Z_0^+ such that if f: A -> Z_0^+ is the flow function defined by f(a) = Sum_{p in P(a)} g(p), where P(a) is the set of all paths in P containing the arc a, then f is such that
(1) f(a) <= c(a) for all a ∈ A,
(2) for each v ∈ V - {s,t}, flow is conserved at v, and
(3) the net flow into t is at least R?
Reference: [Promel, 1978]. Transformation from 3SAT.
Comment: Remains NP-complete even if all c(a) = 1. The corresponding problem with non-integral flows is equivalent to LINEAR PROGRAMMING, but the question of whether the best rational flow fails to exceed the best integral flow is NP-complete.

How to solve

• It can be solved by (existing) bruteforce -- enumerate all integer flow assignments on paths and verify capacity and requirement constraints.
• It can be solved by reducing to integer programming -- ILP with variables g(p) for each path, capacity constraints on arcs, and flow requirement.
• Other: LP relaxation (non-integral) is equivalent to linear programming and solvable in polynomial time.

Example Instance

Instance 1 (YES -- feasible integral flow exists):
Directed graph with 8 vertices {s=0, 1, 2, 3, 4, 5, 6, t=7} and 10 arcs:

• Arcs (with capacities):
  • (0,1) c=2, (0,2) c=1, (1,3) c=1, (1,4) c=1, (2,4) c=1
  • (3,5) c=1, (4,5) c=1, (4,6) c=1, (5,7) c=2, (6,7) c=1
• Paths in P:
  • p_1: 0 → 1 → 3 → 5 → 7
  • p_2: 0 → 1 → 4 → 5 → 7
  • p_3: 0 → 1 → 4 → 6 → 7
  • p_4: 0 → 2 → 4 → 5 → 7
  • p_5: 0 → 2 → 4 → 6 → 7
• R = 3

Arc-sharing conflicts:

• p_1, p_2, p_3 share (0,1) with c=2 → at most 2 can carry flow
• p_2, p_3 share (1,4) with c=1 → at most one of p_2, p_3
• p_4, p_5 share (0,2) with c=1 → at most one of p_4, p_5
• p_2, p_4 share (4,5) with c=1 → at most one of p_2, p_4
• p_3, p_5 share (4,6) with c=1 → at most one of p_3, p_5

Optimal solution 1: g(p_1)=1, g(p_2)=1, g(p_3)=0, g(p_4)=0, g(p_5)=1.

• Arc flows: f(0,1)=2≤2, f(0,2)=1≤1, f(1,3)=1≤1, f(1,4)=1≤1, f(2,4)=1≤1, f(3,5)=1≤1, f(4,5)=1≤1, f(4,6)=1≤1, f(5,7)=2≤2, f(6,7)=1≤1. All satisfied.
• Net flow into t: 1 + 1 + 0 + 0 + 1 = 3 = R.

Optimal solution 2: g(p_1)=1, g(p_2)=0, g(p_3)=1, g(p_4)=1, g(p_5)=0.

• Net flow: 1 + 0 + 1 + 1 = 3 = R.

Suboptimal solution: g(p_1)=1, g(p_2)=1, g(p_3)=0, g(p_4)=0, g(p_5)=0.

• Net flow: 2 < 3 (does not meet requirement, but is feasible at R=2).

32 total configs (binary since all bottleneck capacities are 1), 14 capacity-feasible, 8 with flow≥2, 2 with flow=3.

• Answer: YES

Instance 2 (NO -- no feasible integral flow achieving R):
Same graph and paths as Instance 1, but R = 4.

• Maximum achievable integral flow is 3 (see Instance 1), so no assignment can reach R = 4.
• The two solutions achieving flow=3 are the maximum: the arc-sharing conflicts between paths prevent activating more than 3 simultaneously.
• Answer: NO

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem not yet in the reduction graph
Non-trivial	✅ Pass	Distinct feasibility constraints from all existing problems
Correctness	❌ Fail	Primary reference "Promel, 1978" cannot be verified
Well-written	⚠️ Warn	Several notation and completeness issues

Overall: 2 passed, 1 failed, 1 warning

---

Usefulness

Pass. PathConstrainedNetworkFlow does not exist in the current codebase (confirmed via pred show). The problem is a satisfaction (decision) problem on directed graphs with prescribed path routing, which is structurally distinct from all 24 existing problems. The issue mentions an associated reduction rule (3SAT -> PathConstrainedNetworkFlow), which would connect this problem to the existing reduction graph. The motivation references Garey & Johnson ND34, a recognized NP-complete problem from a standard reference.

Non-trivial

Pass. This problem is genuinely distinct from all existing problems. It involves:

• A directed graph with arc capacities (no existing problem uses directed arcs with capacities)
• A fixed collection of prescribed s-t paths (unique input structure)
• Integer flow assignment to paths with capacity constraints

This is not a variant or renaming of any existing problem. The closest problems in the codebase (ILP, MaxCut, network-related) have fundamentally different feasibility constraints and input structures.

Correctness

Fail. The primary NP-completeness reference cannot be verified.

Reference 1: "H.J. Promel (1978). Transformation from 3SAT."

• Hans Jurgen Promel (properly spelled Promel) is a real mathematician at TU Darmstadt, known for work in combinatorics and Ramsey theory.
• However, Promel received his Diploma in Mathematics from Universitat Bielefeld in 1979, making a 1978 publication highly unlikely.
• DBLP shows no publications by Promel from 1978 or earlier. His earliest indexed publications are from the 1980s.
• The OWU NP-complete problems database (npcomplete.owu.edu) tags ND34 with "No G&J reference", suggesting the original G&J book may not cite a specific reference for this problem's NP-completeness proof.
• The issue header says "Garey & Johnson, A2 ND34" — the "A2" prefix is non-standard for G&J appendix numbering (the standard format is just "ND34"). This suggests the reference may have been transcribed incorrectly or from a secondary source.

Verdict: The "Promel, 1978" citation appears to be fabricated or severely misattributed. The NP-completeness of integer multicommodity flow on prescribed paths is well-established in the literature, but the specific citation given cannot be verified.

Reference 2: Barnhart, Hane, Vance (2000). "Using branch-and-price-and-cut to solve origin-destination integer multicommodity flow problems." Operations Research, 48(2):318-326.

• Verified. This paper exists with the correct authors, title, journal, volume, and page numbers. It addresses origin-destination integer multicommodity flow problems, which is related but focuses on solution methods rather than the NP-completeness proof itself.

Recommendation: Replace the "Promel, 1978" reference with a verifiable NP-completeness source. The NP-hardness of integer multicommodity flow is well-known — e.g., Even, Itai, and Shamir (1976) showed edge-disjoint paths is NP-complete, and the integer unsplittable flow problem on paths is known to be NP-hard (equivalent to bin packing/knapsack in special cases). A proper reference should be found and cited.

Well-written

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

4a. Information Completeness:

• All template sections are present and substantive. Good.

4b. Definition Completeness:

• The mathematical definition is well-formed and directly transcribed from Garey & Johnson.
• Feasibility constraints (capacity, conservation, requirement) are clearly stated.
• However, flow conservation (condition 2) is redundant when flow is decomposed into s-t paths (as noted in the issue's own "Notes" section). The issue should clarify whether this constraint is kept for fidelity to G&J or is actually enforced in the implementation.

4c. Symbol and Notation Consistency:

• The variable domain says "{0, 1, ..., M} where M is bounded by the minimum capacity along the path" — this is correct but M is never formally defined as a single symbol. Each path could have a different upper bound.
• The Schema section uses Vec<i32> for capacities but the definition says c(a) ∈ Z^+ (positive integers). Using i32 allows negative values — consider u32 or document the positive-integer invariant.
• The paths field is described as "sequence of arc indices" — good, but this should be clarified in the definition section too, since the mathematical definition uses paths as sequences of vertices/arcs without specifying the representation.

4d. Example Quality:

• Good: Two examples (YES and NO instances) with the same graph structure, which is illustrative.
• Good: Small enough to verify by hand.
• The examples correctly demonstrate the key constraint (shared arcs between paths limiting total flow).

Missing complexity string: The Complexity section does not provide a concrete worst-case time bound in the format needed for declare_variants! (e.g., "2^num_paths" or similar). It only says "brute-force" without a specific expression. This will need to be filled in before implementation.

Recommendations

• Replace the unverifiable "Promel, 1978" reference with a proper NP-completeness citation.
• Add a concrete complexity string for declare_variants!.
• Clarify the "A2 ND34" notation — standard G&J uses just "ND34".
• Consider using u32 instead of i32 for capacities, or document the positive-integer invariant.
• Define M explicitly in the Variables section, or state that each path variable has a different upper bound.

[isPANN]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem; concrete 3SAT reduction connects to existing KSatisfiability
Non-trivial	✅ Pass	Unique input structure: prescribed s-t paths + integer flow + capacity constraints
Correctness	⚠️ Warn	"Promel, 1978" is a G&J private communication, not a published paper; NP-completeness claim itself is correct
Well-written	❌ Fail	Missing Dims/Size fields sections, no concrete complexity expression, example too small (8 configs, 1 feasible solution)

Overall: 2 passed, 1 warning, 1 failed

---

Usefulness

PathConstrainedNetworkFlow does not exist in the codebase (pred show confirms). The issue mentions R55: 3SAT → PathConstrainedNetworkFlow, and KSatisfiability (3SAT) is already implemented. The motivation is substantive — references G&J ND34, explains the integer vs rational flow distinction, and notes the integrality gap question.

Pass.

Non-trivial

Genuinely distinct from all existing problems:

• Input: Directed graph + prescribed s-t paths + arc capacities + flow requirement (no existing problem has this structure)
• Variables: Integer flow assignment per path (not binary selection, not vertex coloring, not edge selection)
• Constraint: Capacity conflicts arise from shared arcs between paths — unique combinatorial structure

Not a re-skin, variant, or isomorphism. Pass.

Correctness

3a–3c: Reference verification

1. "H.J. Promel (1978). Transformation from 3SAT." — This is almost certainly a private communication cited by Garey & Johnson, not a published paper. Hans Jürgen Proemel (correct spelling: Prömel) was a graduate student at Universität Bielefeld in 1978 (diploma in 1979). His DBLP record shows no publications before the early 1980s. The OWU NP-complete problems database tags ND34 as "No G&J reference," confirming the original G&J book entry uses the private-communication format [Promel, 1978]. The issue's Extra Remark section faithfully reproduces this, but the Complexity section's References list presents it as if it were a published paper — this is misleading but not factually wrong about the NP-completeness itself.

2. Barnhart, Hane, Vance (2000) — Operations Research 48(2):318–326. Verified. Correct authors, title, journal, volume, pages.

3. NP-completeness claim: The NP-completeness of integer flow on prescribed paths is well-established. Büsing & Stiller (2011), "Line planning, path constrained network flow and inapproximability," Networks 57(1):106–113, provide a modern, published proof via reduction from 3SAT. This would be a better citable reference.

3d: Better references found:

• Büsing & Stiller (2011) — published NP-completeness proof for this specific problem
• Martens (2007), "Path-Constrained Network Flows" (PhD dissertation, TU Dortmund) — comprehensive treatment

Warn — the NP-completeness claim is correct, but the citation needs clarification (private communication vs published paper).

Well-written

4a: Required sections

Section	Status
Name	✅ Present
Motivation	✅ Present and substantive
Reference	✅ Present (G&J ND34)
Definition	✅ Well-formed, directly from G&J
Variables	✅ Count, domain, meaning specified
Schema	⚠️ Present but missing variant_params![]
Dims	❌ Missing — no explicit dims specification
Size fields	❌ Missing — no dedicated section with getter names
Complexity	⚠️ No concrete expression for declare_variants! (e.g., "product_path_capacities" or similar)
How to solve	✅ Bruteforce + ILP
Example	❌ Too small (see below)
Expected Outcome	⚠️ Embedded in example, not a dedicated section

4b: Definition completeness — The mathematical definition is well-formed and faithfully transcribed from G&J. Flow conservation (condition 2) is noted as redundant for s-t path decomposition — this is correct and the note is helpful.

4c: Symbol consistency

• Variable domain says "M is bounded by the minimum capacity along the path" but M is not formally defined per-path
• Schema uses i32 for capacities but definition specifies Z^+ (positive integers) — type mismatch (i32 allows negatives)

4d: Example quality

Verified via Python enumeration:

• Instance 1 (R=2): Only 1 feasible solution out of 8 configs — g = (1, 0, 1). Does not meet the ≥2 suboptimal feasible solutions requirement.
• Instance 2 (R=3): Confirmed infeasible — maximum integral flow is 2.
• Search space is 2³ = 8 — well below the 128–10,000 guideline.
• The example correctly demonstrates arc-sharing conflicts (p1∩p2 share arc (3,5), p2∩p3 share arc (0,2)).
• However, it does not demonstrate an integrality gap (LP relaxation also achieves max 2), missing one of the problem's most interesting features mentioned in G&J's comment.

Fail — missing Dims and Size fields sections; example too small with only 1 feasible solution.

Recommendations

• Add Dims section: e.g., dims = [M_1+1, M_2+1, ..., M_|P|+1] where M_i = min capacity along path i. For the binary case (all capacities 1): dims = [2; num_paths].
• Add Size fields section: num_vertices, num_arcs, num_paths.
• Add concrete complexity expression: e.g., "2^num_paths" for the all-capacities-1 case, or a product-based expression for general capacities.
• Replace "Promel, 1978" with proper attribution: "Private communication to Garey & Johnson (1979), ND34. Published proof: Büsing & Stiller (2011), Networks 57(1):106–113."
• Enlarge example: use 5+ paths (32+ configs) with multiple feasible solutions at different flow levels, and ideally demonstrate an integrality gap.
• Add variant_params![] to Schema.
• Consider u32 for capacities or document positive-integer invariant.

[GiggleLiu]

Fix-issue changelog

• Clarified "Promel, 1978" as private communication to Garey & Johnson; added Büsing & Stiller (2011), Networks 57(1):106–113 as published NP-completeness proof
• Fixed "A2 ND34" notation to standard "ND34"
• Changed capacities and requirement types from i32 to u64 (definition requires Z^+)
• Added missing Dims section with per-path bottleneck capacity formula
• Added missing Size Fields section: num_vertices, num_arcs, num_paths, max_capacity, requirement
• Added concrete complexity bound (max_capacity + 1)^num_paths for declare_variants!
• Clarified variable domain: each path p has upper bound M_p = min capacity along p (was undefined single "M")
• Replaced 3-path example (8 configs, 1 feasible) with 8-vertex lattice graph: 5 paths, 32 configs, 2 optimal solutions at flow=3, 6 suboptimal at flow=2, clear NO at R=4

Applied by /fix-issue.