[Model] IntegralFlowWithMultipliers

[isPANN]

---

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

Motivation

INTEGRAL FLOW WITH MULTIPLIERS (P109) from Garey & Johnson, A2 ND33. A generalization of the standard network flow problem where each intermediate vertex v has a multiplier h(v) that scales the incoming flow before comparing it with the outgoing flow. This small change makes the problem NP-complete (the standard case with all h(v) = 1 is polynomial). Arises in lossy network models where flow is gained or lost at intermediate nodes (e.g., water networks with leakage, currency exchange networks).

Associated reduction rules:

• As source: None found in the current rule set.
• As target: R54: PARTITION -> INTEGRAL FLOW WITH MULTIPLIERS

Definition

Name: IntegralFlowWithMultipliers

Canonical name: INTEGRAL FLOW WITH MULTIPLIERS (also: Network Flow with Gains/Losses, Lossy/Gainy Flow)
Reference: Garey & Johnson, Computers and Intractability, A2 ND33

Mathematical definition:

INSTANCE: Directed graph G = (V,A), specified vertices s and t, multiplier h(v) ∈ Z^+ for each v ∈ V - {s,t}, capacity c(a) ∈ Z^+ for each a ∈ A, requirement R ∈ Z^+.
QUESTION: Is there a flow function f: A -> Z_0^+ such that
(1) f(a) <= c(a) for all a ∈ A,
(2) for each v ∈ V - {s,t}, Sum_{(u,v) in A} h(v)*f((u,v)) = Sum_{(v,u) in A} f((v,u)), and
(3) the net flow into t is at least R?

Variables

• Count: |A| integer variables (one per arc), representing the flow on each arc.
• Per-variable domain: {0, 1, ..., c(a)} -- the flow on arc a is a non-negative integer bounded by its capacity.
• Meaning: The variable assignment encodes the flow function. A satisfying assignment is a flow f such that capacity constraints, generalized conservation constraints (with multipliers), and the requirement R on net flow into t are all met.

Dims

[c(a_1)+1, c(a_2)+1, ..., c(a_m)+1] where m = |A|. Each variable (flow on arc a_i) ranges over {0, 1, ..., c(a_i)}.

Schema (data type)

Type name: IntegralFlowWithMultipliers
Variants: None (the directed graph and integer types are fixed)

Field	Type	Description
graph	DirectedGraph	Directed graph G = (V, A)
source	usize	Index of source vertex s
sink	usize	Index of sink vertex t
multipliers	Vec<u64>	Multiplier h(v) for each vertex (length num_vertices; values at source and sink indices are ignored)
capacities	Vec<u64>	Capacity c(a) for each arc
requirement	u64	Flow requirement R

Notes:

• This is a satisfaction (decision) problem: Metric = bool, implementing SatisfactionProblem.
• Multipliers h(v) only apply to intermediate vertices (not s or t).
• The generalized conservation constraint scales incoming flow by h(v): h(v) * (total in-flow) = total out-flow.
• When h(v) = 1 for all v, this is standard max-flow (polynomial).
• The non-integral version can be solved by linear programming.

Size Fields

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

Complexity

• Best known exact algorithm: The problem is NP-complete in general. Brute-force enumeration of integer flow assignments: O((max_capacity + 1)^num_arcs). A pseudo-polynomial dynamic programming approach (similar to the Subset Sum DP) applies when capacities are bounded.
• Concrete bound for declare_variants!: "(max_capacity + 1)^num_arcs"
• Special cases: When all h(v) = 1, solvable in polynomial time via standard max-flow algorithms (e.g., Edmonds-Karp O(|V|·|E|²), push-relabel O(|V|²·|E|)). The rational (non-integral) version is solvable via linear programming regardless of multiplier values.
• NP-completeness: NP-complete by transformation from PARTITION (Sahni, 1974).
• References:
  • S. Sahni (1974). "Computationally related problems." SIAM Journal on Computing, 3:262-279.
  • W.S. Jewell (1962). "Optimal flow through networks with gains." Operations Research, 10(4):476-499.

Extra Remark

Full book text:

INSTANCE: Directed graph G = (V,A), specified vertices s and t, multiplier h(v) ∈ Z^+ for each v ∈ V - {s,t}, capacity c(a) ∈ Z^+ for each a ∈ A, requirement R ∈ Z^+.
QUESTION: Is there a flow function f: A -> Z_0^+ such that
(1) f(a) <= c(a) for all a ∈ A,
(2) for each v ∈ V - {s,t}, Sum_{(u,v) in A} h(v)*f((u,v)) = Sum_{(v,u) in A} f((v,u)), and
(3) the net flow into t is at least R?
Reference: [Sahni, 1974]. Transformation from PARTITION.
Comment: Can be solved in polynomial time by standard network flow techniques if h(v) = 1 for all v ∈ V - {s,t}. Corresponding problem with non-integral flows allowed can be solved by linear programming.

How to solve

• It can be solved by (existing) bruteforce -- enumerate all integer flow assignments on arcs and verify constraints.
• It can be solved by reducing to integer programming -- ILP with capacity, conservation (with multipliers), and flow requirement constraints.
• Other: When all h(v) = 1, standard max-flow algorithms apply (Edmonds-Karp, push-relabel).

Example Instance

Instance 1 (YES -- feasible integral flow exists):
Directed graph with 8 vertices {s, v_1, v_2, v_3, v_4, v_5, v_6, t}:

• Arcs from s: (s, v_1) c=1, (s, v_2) c=1, (s, v_3) c=1, (s, v_4) c=1, (s, v_5) c=1, (s, v_6) c=1
• Arcs to t: (v_1, t) c=2, (v_2, t) c=3, (v_3, t) c=4, (v_4, t) c=5, (v_5, t) c=6, (v_6, t) c=4
• Multipliers: h(v_1)=2, h(v_2)=3, h(v_3)=4, h(v_4)=5, h(v_5)=6, h(v_6)=4
• R = 12

This encodes PARTITION of {2, 3, 4, 5, 6, 4} (sum = 24, target = 12).

Flow: f(s,v_1)=1, f(v_1,t)=2; f(s,v_3)=1, f(v_3,t)=4; f(s,v_5)=1, f(v_5,t)=6.
All other flows = 0.

• Conservation: h(v_1)*1 = 2 = f(v_1,t). h(v_3)*1 = 4 = f(v_3,t). h(v_5)*1 = 6 = f(v_5,t).
• Net flow into t: 2 + 4 + 6 = 12 = R.
• Answer: YES

Instance 2 (NO -- no feasible flow):
Directed graph with 4 vertices {s, v_1, v_2, t} and 5 arcs (diamond structure with internal arc):

• Arcs: (s, v_1) c=2, (s, v_2) c=1, (v_1, t) c=2, (v_2, t) c=5, (v_1, v_2) c=1
• Multipliers: h(v_1)=2, h(v_2)=3
• R = 7

Conservation at v_1: 2 · f(s, v_1) = f(v_1, t) + f(v_1, v_2)
Conservation at v_2: 3 · (f(s, v_2) + f(v_1, v_2)) = f(v_2, t)

Exhaustive case analysis:

• f(s, v_1) = 0: f(v_1, t) = 0, f(v_1, v_2) = 0. Best: f(s, v_2) = 1, f(v_2, t) = 3. Total = 3.
• f(s, v_1) = 1: 2 · 1 = f(v_1, t) + f(v_1, v_2) = 2.
  • (f(v_1, t), f(v_1, v_2)) = (2, 0): f(s, v_2) = 1 → f(v_2, t) = 3. Total = 2 + 3 = 5.
  • (f(v_1, t), f(v_1, v_2)) = (1, 1): f(s, v_2) = 1 → f(v_2, t) = 3 · (1 + 1) = 6 > 5 ✗. f(s, v_2) = 0 → f(v_2, t) = 3 · 1 = 3. Total = 1 + 3 = 4.
• f(s, v_1) = 2: 2 · 2 = 4, but f(v_1, t) ≤ 2 and f(v_1, v_2) ≤ 1, max = 3 < 4 ✗.

Maximum achievable flow = 5 < 7 = R.

• Answer: NO
• Why: The multipliers amplify flow at intermediate vertices, but capacity limits on arcs to t and the internal arc (v_1, v_2) create bottlenecks that prevent enough amplified flow from reaching the sink.

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem not yet in the reduction graph
Non-trivial	✅ Pass	Distinct feasibility constraints (multiplier-scaled conservation) from all existing problems
Correctness	⚠️ Warn	References verified but exact G&J book text could not be independently cross-checked online; conservation constraint formulation has a subtle ambiguity (see below)
Well-written	❌ Fail	Instance 2 is incoherent; multiplier indexing in schema is ambiguous; complexity section lacks a concrete worst-case bound

Overall: 2 passed, 1 warning, 1 failed

---

Usefulness

IntegralFlowWithMultipliers does not exist in the current codebase (confirmed via pred show). The problem is a classic G&J entry (A2 ND33) and connects to the reduction graph via PARTITION → IntegralFlowWithMultipliers. The motivation is clear: lossy/gainy network models with practical applications in water networks and currency exchange. Pass.

Non-trivial

This is genuinely distinct from all 24 existing problems. The closest problems in the codebase are ILP and MaxCut/SpinGlass (graph-based optimization), but none involve directed flow networks with vertex multipliers and capacity constraints. The feasibility constraints (capacity bounds + multiplier-scaled conservation + flow requirement) are structurally different from any existing model. Pass.

Correctness

References verified:

• Sahni (1974), "Computationally Related Problems", SIAM J. Comput. 3:262-279 — Confirmed to exist. The paper does cover network flows with multipliers as one of the computationally related problems shown to be polynomial-time equivalent (all solvable in poly time iff any one is). The paper establishes NP-hardness via connections to partition-type problems. ✅
• Jewell (1962), "Optimal Flow Through Networks with Gains", Operations Research 10(4):476-499 — Confirmed to exist at INFORMS (DOI: 10.1287/opre.10.4.476). The paper studies the continuous (non-integral) version of flow with gains, which is solvable in polynomial time. ✅
• Garey & Johnson, A2 ND33 — The G&J reference is standard and the problem classification is consistent with known sources. Could not independently access the exact book text online to verify the conservation constraint formula character-by-character, but the formulation is consistent with the "Full book text" section provided in the issue. ⚠️

Conservation constraint note: The issue defines h(v) as a vertex multiplier, which matches the G&J formulation (ND33). This is different from the more common "generalized flow" / "flow with gains" formulation in the optimization literature (Jewell, Wayne, etc.), where gain factors are on arcs. The issue's "Canonical name" section lists "Generalized Flow" as an alias, which is technically misleading — the standard generalized flow problem has arc gains and is solvable in polynomial time even for continuous flows. The vertex-multiplier integral version is what makes it NP-complete. Recommend removing "Generalized Flow" from aliases or adding a clarifying note.

Well-written

4a: Information Completeness

Section	Status
Motivation	✅ Present and substantive
Name	✅ Valid (though no Maximum/Minimum prefix needed — satisfaction problem)
Reference	✅ Two literature citations
Definition	✅ Formal definition provided
Variables	✅ Count, domain, meaning all specified
Schema	⚠️ See below
Complexity	❌ See below
How to solve	✅ Brute-force and ILP both checked
Example Instance	❌ See below

4b: Schema Issues

The multipliers field is Vec<i32> with description "Multiplier h(v) for each non-terminal vertex." This is ambiguous: which indices correspond to which vertices? If multipliers has length num_vertices - 2 (excluding s and t), how is the mapping from index to vertex determined? The schema should clarify the indexing convention (e.g., "multipliers[i] corresponds to vertex i for i ∉ {source, sink}, stored in vertex order excluding source and sink" or store multipliers for all vertices with sentinel values for s and t).

4c: Complexity Section — Missing concrete bound

The complexity section says "Brute-force enumeration of integer flow assignments: O(product of (c(a)+1) for all arcs)" but does not provide a concrete worst-case exponential bound usable for declare_variants!. The declare_variants! macro requires a complexity string with concrete numeric values (e.g., "2^num_arcs" or similar). The current description is a product over capacities, which is pseudo-polynomial and depends on input magnitudes, not just the combinatorial structure. A concrete bound like "product_capacity^num_arcs" or a reference to a specific algorithm is needed. Fail.

4d: Example Quality — Instance 2 is incoherent

Instance 1 is good: it clearly encodes a PARTITION instance, shows the flow assignment, verifies conservation constraints, and confirms the answer is YES.

Instance 2 is a mess. The author visibly struggled to construct a NO instance, going through six failed attempts inline:

• "A = {1, 2, 3, 7, 8, 5} ... Actually this is YES"
• "Change to A = {1, 2, 4, 8} ... {1,2,4}=7 works!"
• "For a true NO: A = {1, 2, 6, 9} ... YES again."
• "True NO: A = {1, 1, 3, 6} ... YES."
• "True NO: A = {1, 5, 7, 11} ... YES."
• "For a definitive NO instance: A = {1, 2, 4} ... YES."

The final attempt (A = {3, 5, 7, 11}, sum=26, R=13) is actually correct — no subset sums to 13 — but the presentation is unacceptable. All failed attempts should be removed, and the NO instance should be presented cleanly like Instance 1, with the full graph structure, arc capacities, multipliers, and a brief argument for infeasibility. Fail.

Recommendations

1. Clean up Instance 2: Remove all failed attempts. Present the final NO instance (A = {3, 5, 7, 11}) with the same level of detail as Instance 1 — full graph, arcs, capacities, multipliers, and a clear explanation of why no feasible flow exists.
2. Clarify multiplier indexing in schema: Specify exactly how the multipliers vector maps to vertices. Consider storing multipliers for all vertices (with h(s) = h(t) = 1 as unused sentinels) to simplify indexing.
3. Add a concrete complexity bound: Provide a worst-case bound suitable for declare_variants!. Since there is no known improvement over brute force for the general integral case, something like the product of capacities (pseudo-polynomial) or "C^num_arcs" where C is the max capacity would work, but this needs to be a function of getter method names.
4. Remove or qualify "Generalized Flow" alias: The standard generalized flow problem has arc gains (not vertex multipliers) and a different complexity profile. Listing it as an alias is misleading.
5. Consider i64 or u32 instead of i32 for capacities and multipliers, since the definition requires positive integers (Z^+) — i32 allows negative values which would need runtime validation.

[isPANN]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem not yet in the reduction graph; concrete reduction from PARTITION
Non-trivial	✅ Pass	Distinct feasibility constraints (multiplier-scaled conservation) from all 86 existing problems
Correctness	❌ Fail	Instance 2 (NO) is actually YES; "Generalized Flow" alias is misleading
Well-written	❌ Fail	Missing Dims and Size fields sections; Instance 2 incoherent; complexity lacks concrete bound

Overall: 2 passed, 0 warnings, 2 failed

---

Usefulness

IntegralFlowWithMultipliers does not exist in the current codebase (confirmed via pred show). The problem is a classic G&J entry (A2 ND33) and connects to the reduction graph via PARTITION → IntegralFlowWithMultipliers. The closest existing problem is DirectedTwoCommodityIntegralFlow, which models two-commodity flow without multipliers — structurally different. Pass.

Non-trivial

The vertex-multiplier conservation constraint (h(v) * Σ_in = Σ_out) is genuinely different from all 86 existing problems. DirectedTwoCommodityIntegralFlow has standard conservation (no multipliers) with two commodities. No existing problem can model this as a variant. Pass.

Correctness

References:

• Sahni (1974), "Computationally Related Problems", SIAM J. Comput. 3:262-279 — ✅ Confirmed. Paper establishes NP-completeness of integral flow with multipliers via reduction from Subset Sum (G&J standardizes the source as PARTITION, which is equivalent).
• Jewell (1962), "Optimal Flow Through Networks with Gains", Operations Research 10(4):476-499 — ✅ Confirmed. Covers the continuous (non-integral) version with arc gains.
• G&J ND33 — ✅ Consistent with project catalog (P109 in issue Garey & Johnson Extraction: 342 Problems + 335 Reductions Catalog #183).

Issues found:

1. Instance 2 is WRONG (critical). The problem asks for net flow into t at least R (≥ R), not exactly R. The "NO" instance uses A = {3, 5, 7, 11} with sum=26, R=13. While no subset sums to exactly 13, subsets summing to ≥ 13 exist (e.g., {7,11}=18, {3,5,7}=15, {3,5,11}=19, etc.). Python brute-force verification found 8 satisfying flow assignments. The instance is actually YES.

2. "Generalized Flow" alias is misleading. Standard generalized flow in the operations research literature (Jewell, Wayne) places gain factors on arcs, not vertices. The G&J formulation uses vertex multipliers. While the two are equivalent via node-splitting, listing "Generalized Flow" as an alias without qualification conflates the NP-hard integral vertex-multiplier version with the polynomial-time continuous arc-gain version.

3. Pseudo-polynomial algorithm exists. The issue claims "No known exact exponential-time improvement over exhaustive search." This is too pessimistic — since NP-completeness comes from PARTITION/Subset Sum (which admits pseudo-polynomial DP), a similar approach works here when capacities are bounded.

Fail — Instance 2 incorrectness is critical.

Well-written

4a: Required sections:

Section	Status
Motivation	✅ Present and substantive
Name	✅ Valid (satisfaction problem, no prefix needed)
Reference	✅ Two literature citations
Definition	✅ Formal definition with input, feasibility, objective
Variables	✅ Count, domain, meaning specified
Schema	⚠️ Multiplier indexing ambiguous (see below)
Dims	❌ Missing — must specify config space (e.g., [c(a_1)+1, c(a_2)+1, ..., c(a_m)+1])
Size fields	❌ Missing — must list getter names + meanings (e.g., num_vertices, num_arcs, max_capacity)
Complexity	❌ No concrete bound for declare_variants! (see below)
How to solve	✅ Brute-force and ILP checked
Example	❌ Instance 2 incoherent and incorrect (see below)
Expected Outcome	⚠️ Instance 1 has expected outcome; Instance 2 does not (and is wrong)

4b: Schema — multiplier indexing ambiguous.
multipliers: Vec<i32> "for each non-terminal vertex" — which indices map to which vertices? If length is num_vertices - 2, the mapping from index to vertex is unclear. Should specify: "multipliers[i] is h(v) for vertex i, where s and t have implicit multiplier 1" or store for all vertices.

4c: Complexity — no concrete bound.
The complexity section describes brute-force as O(product of (c(a)+1)) but does not provide a concrete worst-case expression using getter method names (required for declare_variants!). Needs something like "(max_capacity + 1)^num_arcs" (cf. DirectedTwoCommodityIntegralFlow which uses "(max_capacity + 1)^(2 * num_arcs)").

4d: Example quality — Instance 2 is incoherent and incorrect.
Instance 2 contains six inline failed attempts before arriving at the final set {3, 5, 7, 11}. The author's debugging process is visible in the issue text. Worse, the final instance is still incorrect (actually YES, not NO — see Correctness). All failed attempts must be removed, and a correct NO instance must be constructed.

To construct a valid NO instance: the PARTITION reduction requires that the answer is NO iff no subset of multiplier values sums to exactly R = sum/2. But the problem formulation uses ≥, not =. A correct NO instance would need capacities structured so that overshooting is impossible, or use an odd total sum where R = ⌈sum/2⌉ and no subset achieves exactly that (but subsets exceeding it also fail due to capacity constraints).

Recommendations

1. Fix Instance 2: Remove all failed attempts. Construct a correct NO instance where capacity constraints prevent any flow ≥ R. One approach: use the bipartite structure but add capacity limits that make overshooting impossible (e.g., capacity on arcs to t equals the multiplier value), then choose multipliers where no subset sums to exactly R.
2. Add Dims section: [c(a_1)+1, c(a_2)+1, ..., c(a_m)+1] for m = |A| arcs.
3. Add Size fields section: List getter names like num_vertices, num_arcs, max_capacity, requirement.
4. Add concrete complexity bound: e.g., "(max_capacity + 1)^num_arcs".
5. Clarify multiplier indexing: Specify whether multipliers are stored for all vertices or only non-terminals, and the index mapping.
6. Remove or qualify "Generalized Flow" alias: Standard generalized flow has arc gains and is polynomial; this is the NP-hard integral vertex-multiplier version.

[GiggleLiu]

Fix-issue changelog

• Removed misleading "Generalized Flow" alias from canonical name (standard generalized flow has arc gains and is polynomial; this problem has vertex multipliers)
• Changed multipliers, capacities, requirement types from i32 to u64 (definition requires Z^+); clarified multiplier indexing (length num_vertices, s/t values ignored)
• Added missing Dims section: [c(a_1)+1, ..., c(a_m)+1]
• Added missing Size Fields section: num_vertices, num_arcs, max_capacity, requirement
• Added concrete complexity bound (max_capacity + 1)^num_arcs for declare_variants! + pseudo-polynomial DP note
• Replaced broken Instance 2 (6 inline failed attempts, final answer incorrect — problem uses ≥ R not = R) with correct diamond-graph NO instance (4 vertices, 5 arcs, exhaustive case analysis proving max flow = 5 < 7 = R)

Applied by /fix-issue.