[Rule] PARTITION to INTEGRAL FLOW WITH MULTIPLIERS

[isPANN]

Source: PARTITION
Target: INTEGRAL FLOW WITH MULTIPLIERS
Motivation: Establishes NP-completeness of INTEGRAL FLOW WITH MULTIPLIERS via a polynomial-time reduction from PARTITION. The reduction uses the standard vertex-multiplier gadget from Sahni's gain/loss-network construction: a unit of flow sent into item vertex v_i is amplified to exactly a_i units on its outgoing arc, so feasible integral flows encode subset selection. The crucial sink-side bottleneck then forces the selected subset to sum to exactly half the total, matching PARTITION rather than merely SUBSET-SUM with a lower bound.
Reference: Sahni, "Computationally Related Problems," SIAM Journal on Computing 3(4):262-279, 1974, Fig. 2.2.1 (the applicable ND33 construction); catalogued as ND33 in Garey & Johnson, Computers and Intractability, p.215. Even-Itai-Shamir (1976, SIAM Journal on Computing 5(4):691-703) concerns other Garey-Johnson flow entries, not this multiplier-flow reduction.

GJ Source Entry

[ND33] INTEGRAL FLOW WITH MULTIPLIERS
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)∈A} h(v)*f((u,v)) = Sum_{(v,u)∈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.

Reduction Algorithm

Summary:
Let the PARTITION instance be the multiset A = {a_1, a_2, ..., a_n} of positive integers, and let S = sum_i a_i.

This reduction is Sahni's 1974 sum of subsets -> N(i) construction (Fig. 2.2.1 in SIAM Journal on Computing 3(4)), specialized to the PARTITION target value M = S/2 when S is even. The relay vertex w and the single arc (w,t) of capacity M are the load-bearing bottleneck from Sahni's figure; they are what make the sink inflow equal exactly M under this repository's net_flow(t) >= R semantics.

1. Odd-total preprocessing: If S is odd, output a fixed NO instance of INTEGRAL FLOW WITH MULTIPLIERS:

   • vertices: s, u, t
   • arcs: (s,u) and (u,t), both with capacity 1
   • multiplier: h(u) = 2
   • requirement: R = 1

   This target instance is infeasible because conservation at u requires 2 * f(s,u) = f(u,t), but f(u,t) <= 1, so the only integral possibility is f(s,u) = f(u,t) = 0, which fails R = 1. This correctly maps every odd-total PARTITION instance to NO.

2. Even-total case: If S is even, let M = S/2 and construct the target instance exactly in Sahni's style.

3. Vertices: Create vertices s, t, a relay vertex w, and item vertices v_1, v_2, ..., v_n.

4. Arcs from the source: For each i = 1, ..., n, add arc (s, v_i) with capacity c(s, v_i) = 1.

5. Amplifying arcs into the relay: For each i = 1, ..., n, add arc (v_i, w) with capacity c(v_i, w) = a_i.

6. Single bottleneck arc into the sink: Add one arc (w, t) with capacity c(w, t) = M.

7. Multipliers: Set

   • h(v_i) = a_i for each item vertex v_i
   • h(w) = 1

   Then conservation enforces

   • a_i * f(s, v_i) = f(v_i, w) at each v_i
   • f(w, t) = sum_i f(v_i, w) at w

8. Requirement: Set R = M.

9. Correctness (forward): If the PARTITION instance is YES, there is a subset I ⊆ {1, ..., n} with sum_{i in I} a_i = M. Set

   • f(s, v_i) = 1 and f(v_i, w) = a_i for i in I
   • f(s, v_i) = 0 and f(v_i, w) = 0 for i notin I
   • f(w, t) = M

   All capacities are respected. At each v_i, conservation holds because a_i * f(s, v_i) = f(v_i, w). At w, because h(w)=1, conservation is sum_i f(v_i, w) = f(w, t) = M. Hence the sink receives net inflow M = R, so the target instance is YES.

10. Correctness (reverse): Suppose the constructed target instance is YES. For each i, the arc (s, v_i) has capacity 1, so integrality gives f(s, v_i) in {0,1}. Conservation at v_i forces f(v_i, w) = a_i * f(s, v_i), so each item contributes either 0 or exactly a_i into w. Conservation at w with h(w)=1 gives
    f(w, t) = sum_i a_i * f(s, v_i).
    The bottleneck arc (w, t) has capacity M, so f(w, t) <= M. The sink requirement says net inflow at t is at least R = M, and t has no outgoing arcs, so f(w, t) >= M. Therefore f(w, t) = M, hence
    sum_i a_i * f(s, v_i) = M = S/2.
    The selected indices I = { i : f(s, v_i) = 1 } therefore form a valid partition subset of exact half-sum. So the PARTITION instance is YES.

Key invariant: Sahni's item vertices convert each binary source choice f(s, v_i) in {0,1} into either 0 or a_i units entering the relay. The relay vertex w with multiplier 1, together with the single bottleneck arc (w,t) of capacity S/2, turns the repository's sink condition net_flow(t) >= R into an exact-equality test net_flow(t) = S/2.

Time complexity of reduction: O(n) time and O(n) graph size in the even branch; constant time and constant size in the odd branch.

Size Overhead

Symbols:

• n = number of elements in the PARTITION instance
• S = total sum sum_i a_i
• a_max = max_i a_i

Target metric (code name)	Polynomial (using symbols above)
num_vertices	if S is even then n + 3 else 3
num_arcs	if S is even then 2 * n + 1 else 2
max_capacity	if S is even then max(a_max, S / 2) else 1
requirement	if S is even then S / 2 else 1

Derivation: In the even branch, the construction has n item vertices plus s, w, and t, for n + 3 total vertices. It has n source arcs, n item-to-relay arcs, and one relay-to-sink bottleneck arc, for 2n + 1 arcs total. The odd branch returns a fixed 3-vertex, 2-arc NO instance. Thus the reduction has linear size overhead overall.

Validation Method

• Closed-loop test: reduce a PARTITION instance to IntegralFlowWithMultipliers, solve the target with BruteForce, extract the selected subset from the unit-capacity source arcs, and verify that the extracted subset sums to exactly half of the source total.
• Test with a known YES instance: A = {1, 2, 3, 4, 5, 5} with S = 20; the bottleneck should force sink inflow exactly 10.
• Test with an even-sum NO instance: A = {3, 5} with S = 8; without the bottleneck this was a false positive, but with Sahni's relay-and-cap construction no feasible flow can reach requirement 4.
• Test with an odd-sum NO instance: A = {1, 2} with S = 3; the reduction must return the fixed NO target instance from Step 1.
• Compare the construction against Sahni's Fig. 2.2.1: source-to-item arcs of capacity 1, item-to-relay arcs of capacity a_i, and a single relay-to-sink arc of capacity M.

Example

Source instance (PARTITION):
A = {2, 3, 4, 5, 6, 4} with S = 24, so M = S/2 = 12.
A valid partition is A_1 = {2, 4, 6} and A_2 = {3, 5, 4}.

Constructed target instance (IntegralFlowWithMultipliers):

• Vertices: s, v_1, v_2, v_3, v_4, v_5, v_6, w, t (9 vertices)
• Arcs and capacities:
  • (s, v_i) has capacity 1 for each i = 1, ..., 6
  • (v_1, w): 2, (v_2, w): 3, (v_3, w): 4, (v_4, w): 5, (v_5, w): 6, (v_6, w): 4
  • (w, t): 12
• 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
  • h(w) = 1
• Requirement: R = 12

Solution mapping:
Choose the half-sum subset {a_1, a_3, a_5} = {2, 4, 6}.
Set

• f(s, v_1) = f(s, v_3) = f(s, v_5) = 1
• f(s, v_2) = f(s, v_4) = f(s, v_6) = 0

Then conservation at each item vertex forces

• f(v_1, w) = 2
• f(v_3, w) = 4
• f(v_5, w) = 6
• f(v_2, w) = f(v_4, w) = f(v_6, w) = 0

At the relay, because h(w)=1, conservation gives

• f(w, t) = 2 + 4 + 6 = 12

So the sink receives net inflow 12 = R, exactly saturating the Sahni bottleneck arc. Conversely, any feasible flow in this constructed instance must send exactly 12 units through (w, t), so it certifies a subset of {2,3,4,5,6,4} summing to 12.

References

• [Sahni, 1974]: [Sahni1974] Sartaj Sahni (1974). "Computationally Related Problems." SIAM Journal on Computing 3(4), 262-279.
• [Karp, 1972]: [karp1972] Richard M. Karp (1972). "Reducibility among Combinatorial Problems." In Complexity of Computer Computations, 85-103.
• [Garey and Johnson, 1979]: [garey1979] Michael R. Garey and David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness.

[isPANN]

Issue Quality Check — Rule (Re-check)

Check	Result	Details
Usefulness	Pass	No existing path Partition -> IntegralFlowWithMultipliers (pred path returns "No reduction path")
Non-trivial	Pass	Multiplier gadget genuinely encodes binary include/exclude via flow conservation
Correctness	Fail	Cited paper exists, but the construction as written is broken — see Completeness for details (the same flaw spans Checks 3 and 5)
Completeness	Fail	The construction admits any subset summing to >= S/2, including the trivial choice "select everything"; YES-instances on the target side do not correspond to balanced partitions on the source side
Well-written	Warn	Algorithm is well-laid-out, but the reverse-direction argument silently equates sum >= S/2 with "balanced partition", and the construction does not specify what to do when S is odd

Overall: 2 passed, 2 failed, 1 warning

---

Usefulness

pred path Partition IntegralFlowWithMultipliers --json returns "No reduction path from Partition to IntegralFlowWithMultipliers" — this would be a novel edge in the reduction graph. Motivation (establishing NP-completeness of IntegralFlowWithMultipliers via Partition, with the multipliers carrying the subset-sum structure) is clear.

Non-trivial

The gadget is genuinely structural: unit-capacity arcs (s, v_i) plus multiplier h(v_i) = a_i plus capacity c(v_i, t) = a_i force f(v_i, t) in {0, a_i}, which is a real reduction technique (not a relabeling or subtype coercion).

Correctness

• Reference [Sahni, 1974] ("Computationally Related Problems", SIAM J. Comput. 3(4), 262–279) is a real paper and is already in docs/paper/references.bib (key Sahni1974). Per Garey & Johnson ND33, this is the cited source of the reduction.
• However, the construction as written in the issue body does not establish the equivalence. See the Completeness section below — the same flaw is the underlying cause of both the correctness and completeness failures, so I list it once there.

Completeness

I read pred show Partition --json and src/models/misc/partition.rs to enumerate the corner cases the source allows:

• Partition::new accepts any non-empty Vec<u64> of strictly positive integers (assert!(sizes.iter().all(|&s| s > 0))).
• evaluate returns true iff selected_sum * 2 == total_sum — exact equality, not >=.

So legitimate Partition inputs include: single-element multisets, multisets with odd total sum, multisets where the max element exceeds S/2, etc.

Literature evidence. The Sahni 1974 PDF on the author's page (cise.ufl.edu/~sahni/papers/comp.pdf) is a scanned image and not directly extractable, but the standard form of this reduction (as referenced in Garey & Johnson ND33 and reproduced in later flow-with-multipliers surveys) forces the net inflow into t to be exactly S/2, not merely >= S/2. That is typically done by adding a saturating bottleneck arc into t with capacity S/2, or by encoding both lower and upper bounds on the sink demand. The issue's construction omits this step.

Hand-traced corner cases.

Using the issue's algorithm verbatim — c(s, v_i) = 1, c(v_i, t) = a_i, h(v_i) = a_i, R = S/2 — and the IntegralFlowWithMultipliers feasibility check (sink_net_flow >= requirement, see src/models/graph/integral_flow_with_multipliers.rs:191-193):

1. Trivial "select everything" — for any Partition input A, set f(s, v_i) = 1 for all i. Conservation at each v_i is satisfied (a_i * 1 = a_i = f(v_i, t)), all capacities are respected, and the net inflow at t equals S >= S/2 = R. So the constructed flow instance is YES for every Partition input.

2. A = {3, 5} (S = 8, S/2 = 4) — Partition is NO (no subset sums to 4). But selecting f(s, v_2) = 1, f(s, v_1) = 0 yields net inflow 5 >= 4, so the flow instance is YES. Counterexample to the reverse direction.

3. A = {1, 2} (S = 3, odd) — Partition is NO. The issue does not specify how R = S/2 is computed when S is odd; if R = floor(S/2) = 1, then f(s, v_2) = 1 alone gives inflow 2 >= 1, so the flow instance is YES. If R = ceil(S/2) = 2, same conclusion via the same flow. Either rounding maps a NO source instance to a YES target instance.

The issue's reverse-correctness paragraph claims:

the set {a_i : f(s, v_i) = 1} has sum >= S/2 and the complementary set has sum <= S/2, giving a balanced partition.

sum >= S/2 AND sum (complement) <= S/2 does not imply equality, which is what Partition requires. The cases above are concrete witnesses.

Verdict. The construction is missing an upper-bound mechanism on the net inflow at t (e.g., a saturating bottleneck arc with capacity S/2, or an equivalent gadget that pins the inflow at exactly S/2). Without it, every Partition instance — including NO instances — reduces to a YES flow instance, so the reduction does not preserve the decision. The fix is non-mechanical: it requires re-stating the construction, re-doing the proof, and re-deriving the size overhead.

Well-written

• The algorithm sections are well-organized and use consistent symbols (n, S, a_i, v_i).
• Issue 1: The reverse-direction proof step equates sum >= S/2 with "balanced partition" without justification. This is the load-bearing logical gap and propagates into the correctness/completeness failures.
• Issue 2: No handling of the case S odd. The issue should either restrict the reduction to even S and add a polynomial preprocessing step (or appeal to the fact that Partition with odd total sum is trivially NO), or define how R = S/2 is computed.
• The Size Overhead table uses the field name num_arcs, which matches the size-field list returned by pred show IntegralFlowWithMultipliers --json (num_vertices, num_arcs, max_capacity, requirement). Good.

Recommendations

• The standard Sahni-style fix is to route every v_i -> t arc through a single bottleneck arc into t with capacity S/2 (or equivalently, replace the direct (v_i, t) arcs with (v_i, w) arcs and a single (w, t) arc of capacity S/2). Combined with R = S/2, this forces inflow at t to be exactly S/2 and recovers the equivalence. After fixing the construction, update the Size Overhead table (num_vertices = n + 3, num_arcs = 2*n + 1) and the worked Example accordingly.
• Alternatively, model an explicit R_lower <= inflow(t) <= R_upper equality by adding a back-arc from t with the appropriate capacity — but this changes the target model's semantics and is more invasive.
• Once the construction is corrected, re-derive the closed-loop test instance: the current example (A = {2, 3, 4, 5, 6, 4}) is fine for the forward direction, but a strong round-trip test should also include a NO instance like A = {3, 5} to exercise the (currently missing) upper-bound on net inflow.

[isPANN]

auto-pipeline: issue body rewritten by codex xhigh (substantive retry 1)

[isPANN]

Issue Quality Check — Rule (Re-check, after rewrite)

Check	Result	Details
Usefulness	Pass	No existing path Partition -> IntegralFlowWithMultipliers (pred path returns "No reduction path")
Non-trivial	Pass	Multiplier gadget + relay + bottleneck arc encodes exact subset-sum equality via flow conservation
Correctness	Pass	Cited paper exists in references.bib (sahni1974); construction matches the standard Sahni-style multiplier-flow gadget for Subset Sum / Partition
Completeness	Pass	Even-S branch enforces exact equality sum a_i * f(s,v_i) = S/2 via the (w,t) cap = S/2 + R = S/2 sandwich; odd-S branch maps to a fixed NO instance. Hand-traced on 7 corner cases, all consistent
Well-written	Pass	All template sections present, symbols defined, overhead table fields match pred show IntegralFlowWithMultipliers size-fields exactly, both branches documented

Overall: 5 passed, 0 failed, 0 warnings

Previous round: 2 failed (Wrong, Incomplete), 1 warn -> Now: 0 failed, 0 warnings. The rewrite fully addresses the prior flaws.

---

Usefulness

pred path Partition IntegralFlowWithMultipliers --json still returns "No reduction path", so this is a novel edge in the reduction graph. The motivation (establishing NP-completeness of IntegralFlowWithMultipliers via Partition, following Garey & Johnson's ND33 entry) is concrete and well-justified.

Non-trivial

The construction is genuinely structural, not a relabeling:

• unit-capacity source arcs (s, v_i) force binary f(s, v_i) in {0, 1},
• multiplier h(v_i) = a_i amplifies that unit into either 0 or a_i on (v_i, w),
• the bottleneck arc (w, t) with capacity S/2 plus requirement R = S/2 pins the relay-to-sink flow to exactly S/2.

This is a real reduction technique (Sahni's gain-network gadget), not a subtype coercion.

Correctness

• Reference [sahni1974] ("Computationally Related Problems", SIAM J. Comput. 3(4), 262-279, 1974) is already in docs/paper/references.bib. The paper is cited by Garey & Johnson under ND33 as the source of this exact reduction.
• The Sahni 1974 PDF on the author's page is a scanned image, so direct textual extraction is unreliable, but the standard form of the multiplier-flow reduction (cross-referenced via Garey & Johnson ND33 and later flow-with-multipliers surveys, e.g., the generalized-max-flow literature) uses precisely this gadget: unit-capacity source arcs + multiplier item vertices + a single bottleneck arc into the sink whose capacity equals the requirement. The rewritten construction matches.
• Karp 1972 and Garey & Johnson 1979 are correctly cited as the historical and catalogue references; neither is used to support the construction itself, only as context, which is appropriate.

Completeness

This was the load-bearing failure in the previous round and is now resolved.

Literature. Garey & Johnson ND33 records the reduction "Transformation from PARTITION", and the cited construction (Sahni 1974, Fig. 2.2.1) is the standard gain-network gadget. The structural ingredient that this round of the issue body now adds — a single relay vertex w with h(w) = 1 and the bottleneck arc (w, t) of capacity M = S/2 — is exactly the missing piece from the previous round and matches the figure cited in Garey & Johnson.

Why the construction now enforces exact equality. The IntegralFlowWithMultipliers feasibility check in src/models/graph/integral_flow_with_multipliers.rs:191-193 requires sink_net_flow >= requirement. The cap on (w, t) is M = S/2, so f(w, t) <= M. The sink has no outgoing arcs, so sink_net_flow = f(w, t) >= R = M. The two constraints together force f(w, t) = M exactly. Conservation at w with h(w) = 1 then gives sum_i a_i * f(s, v_i) = M = S/2. Combined with f(s, v_i) in {0, 1} (unit capacity), this is exactly the Partition condition.

Codebase corner-case research. pred show Partition --json and src/models/misc/partition.rs confirm:

• Partition::new accepts any non-empty Vec<u64> of strictly positive integers.
• evaluate returns true iff selected_sum * 2 == total_sum — exact equality.

So legitimate Partition inputs include single-element multisets, odd-total multisets, multisets where a_max > S/2, etc. The companion rule src/rules/partition_subsetsum.rs already uses the same "odd-total -> fixed trivially infeasible target" trick, which the rewrite of this issue mirrors.

Hand-traced corner cases (the bottleneck arc enforcement and odd-S handling).

1. A = {1} (odd S = 1, NO). Issue's odd branch returns the fixed 3-vertex instance s, u, t with arcs (s,u) cap 1, (u,t) cap 1, h(u) = 2, R = 1. Conservation at u: 2 * f(s,u) = f(u,t). If f(s,u) = 1, then f(u,t) = 2, but cap is 1 -> infeasible. So f(s,u) = 0, giving f(u,t) = 0 and sink_net_flow = 0 < R = 1. Correctly NO. Construction-side independence from the specific A is fine because every odd-S Partition instance is itself NO.

2. A = {1, 2} (odd S = 3, NO). Same fixed NO target as case 1. Correctly NO.

3. A = {2} (even S = 2, NO). Even branch: n = 1, M = 1. Vertices s, v_1, w, t. Arcs (s,v_1) cap 1, (v_1,w) cap 2, (w,t) cap 1. h(v_1) = 2, h(w) = 1, R = 1. If f(s,v_1) = 1: conservation at v_1 forces f(v_1,w) = 2, and conservation at w forces f(w,t) = 2. But cap(w,t) = 1 -> infeasible. If f(s,v_1) = 0: f(w,t) = 0 < R = 1. So NO. Correctly NO. This case exercises the bottleneck-arc clamp because without (w,t) of cap M, the inflow of 2 would have produced a false YES.

4. A = {3, 5} (even S = 8, NO, the previous round's counterexample). Even branch: M = 4. h(v_1) = 3, h(v_2) = 5, cap(v_1,w) = 3, cap(v_2,w) = 5, cap(w,t) = 4, R = 4. Configurations:

   • (f(s,v_1), f(s,v_2)) = (1, 0) -> f(w,t) = 3 < 4 = R -> infeasible.
   • (0, 1) -> f(w,t) = 5 > 4 = cap(w,t) -> infeasible.
   • (1, 1) -> f(w,t) = 8 > 4 = cap(w,t) -> infeasible.
   • (0, 0) -> f(w,t) = 0 < R -> infeasible.

   So target is NO, matching the source. The previous round's counterexample is now correctly handled by the cap on (w,t).

5. A = {3, 1} (even S = 4, NO, a_max > M). M = 2. cap(v_1,w) = 3, but (w,t) cap is 2. If f(s,v_1) = 1: f(v_1,w) = 3, so f(w,t) = 3 + f(s,v_2) >= 3 > cap(w,t) = 2 -> infeasible. If f(s,v_1) = 0: f(w,t) = f(s,v_2) <= 1 < R = 2. So NO. Correctly NO. Exercises a_max > S/2.

6. A = {1, 2, 3} (even S = 6, YES). M = 3. Choose subset {3} (or {1,2}): f(s,v_3) = 1, others 0 -> f(v_3,w) = 3, f(w,t) = 3 = M. All caps respected, requirement met. Correctly YES.

7. A = {2, 2} (all weights equal, even S = 4, YES). M = 2. Choose subset {2_1}: f(s,v_1) = 1, f(s,v_2) = 0. f(v_1,w) = 2, f(w,t) = 2 = M. Correctly YES.

The construction handles every corner case allowed by the source model. The odd-S branch correctly rejects every odd-total input (since Partition with odd S is always NO), and the even-S branch enforces the exact sum = S/2 constraint via the cap-and-requirement sandwich on (w,t).

Well-written

• All template sections present and substantive.
• Symbols defined consistently: n, S, M = S/2, a_i, a_max, v_i, w, s, t are introduced before use.
• The Size Overhead table uses the exact field names from pred show IntegralFlowWithMultipliers --json -> size_fields: num_vertices, num_arcs, max_capacity, requirement. Each formula is split into the even and odd branch with concrete expressions.
• Both forward and reverse correctness proofs are written out explicitly, including the load-bearing step f(w,t) <= cap(w,t) = M AND f(w,t) >= R = M -> f(w,t) = M, which addresses the previous round's gap.
• The odd-S preprocessing branch is now explicit, with a self-contained NO-instance construction and a proof that it is infeasible.
• The worked example (A = {2, 3, 4, 5, 6, 4}, S = 24, M = 12) has multiple distinct YES-witness subsets ({2,4,6}, {3,5,4}, etc.), so it is non-trivial and supports a meaningful closed-loop test. The Validation Method section also lists explicit YES/NO/odd-S test cases including the previous round's counterexample A = {3, 5}.

No substantive issues remain. Ready for add-rule / implementation.