[Rule] INDEPENDENT SET to INTEGRAL FLOW WITH BUNDLES

[isPANN]

Source: MaximumIndependentSet
Target: INTEGRAL FLOW WITH BUNDLES
Motivation: Establishes NP-completeness of INTEGRAL FLOW WITH BUNDLES via polynomial-time reduction from MaximumIndependentSet. The reduction encodes adjacency constraints as shared bundle capacities, showing that even simple bundle structures make integer network flow intractable.

Reference: Garey & Johnson, Computers and Intractability, ND36, p.216

GJ Source Entry

[ND36] INTEGRAL FLOW WITH BUNDLES
INSTANCE: Directed graph G=(V,A), specified vertices s and t, "bundles" I_1,I_2,···,I_k⊆A such that ⋃_{1≤j≤k} I_j=A, bundle capacities c_1,c_2,···,c_k∈Z^+, requirement R∈Z^+.
QUESTION: Is there a flow function f: A→Z_0^+ such that
(1) for 1≤j≤k, Σ_{a∈I_j} f(a)≤c_j,
(2) for each v∈V−{s,t}, flow is conserved at v, and
(3) the net flow into t is at least R?
Reference: [Sahni, 1974]. Transformation from INDEPENDENT SET.
Comment: Remains NP-complete if all capacities are 1 and all bundles have two arcs. Corresponding problem with non-integral flows allowed can be solved by linear programming.

Reduction Algorithm

Optimization-to-feasibility framing: MaximumIndependentSet is an optimization problem (find the largest independent set), whereas INTEGRAL FLOW WITH BUNDLES is a feasibility/threshold problem (does a flow of value ≥ R exist?). To bridge this gap, we set the requirement R equal to the optimal MIS value. A brute-force or exact solver first determines the maximum independent set size, and the reduction then asks whether a feasible bundled flow of that value exists. Equivalently, for any threshold K, the graph has an independent set of size ≥ K if and only if the constructed flow instance with R = K is feasible.

Summary:
Given a MaximumIndependentSet instance (graph G'=(V',E')), construct an INTEGRAL FLOW WITH BUNDLES instance as follows:

1. Vertex gadgets: For each vertex v_i in V', create two arcs: a_i^in = (s, w_i) and a_i^out = (w_i, t), where w_i is a fresh intermediate node. Each vertex contributes a two-arc path s → w_i → t.

2. Edge bundles: For each edge {v_i, v_j} in E', create a bundle I_{ij} = {a_i^out, a_j^out} with bundle capacity c_{ij} = 1. This constraint ensures that at most one of a_i^out and a_j^out carries flow 1 — i.e., at most one endpoint of each edge is "selected."

3. Vertex bundles: Each arc a_i^out also belongs to a singleton bundle {a_i^out} with capacity 1, ensuring flow on each arc is at most 1.

4. Requirement: Set R = optimal MIS value (the maximum independent set size in G').

The graph G' has an independent set of size ≥ R if and only if there exists an integral flow of value at least R in the constructed network satisfying all bundle capacity constraints. Selecting flow 1 on arc a_i^out corresponds to including vertex v_i in the independent set; the edge bundle constraint ensures no two adjacent vertices are both selected.

Size Overhead

Target metric (code name)	Polynomial (using symbols above)
num_vertices	n + 2 where n = |V'| (s, t, and one intermediate node per vertex)
num_arcs	2n (one arc s→w_i and one arc w_i→t per vertex)
num_bundles	|E'| + n (one bundle per edge plus one singleton per vertex)

Validation Method

• Closed-loop test: reduce source MaximumIndependentSet instance, solve target integral flow with bundles using BruteForce, extract solution, verify on source
• Compare with known results from literature
• Verify that graphs with independent set of size ≥ R yield feasible flow ≥ R and those without do not

Example

Source (MaximumIndependentSet):
Graph G' with 6 vertices {v_1, v_2, v_3, v_4, v_5, v_6} and 7 edges:

• Edges: {v_1,v_2}, {v_2,v_3}, {v_3,v_4}, {v_4,v_5}, {v_5,v_6}, {v_6,v_1}, {v_1,v_4}
  Optimal MIS size: K = 3 (e.g., {v_2, v_4, v_6})

Constructed Target (Integral Flow with Bundles):

Vertices: s, w_1, w_2, w_3, w_4, w_5, w_6, t (8 vertices total).

Arcs: For each i in {1..6}:

• a_i^in = (s, w_i) and a_i^out = (w_i, t)

Bundles (edge bundles, capacity 1 each):

• I_{12} = {a_1^out, a_2^out} — edge {v_1, v_2}
• I_{23} = {a_2^out, a_3^out} — edge {v_2, v_3}
• I_{34} = {a_3^out, a_4^out} — edge {v_3, v_4}
• I_{45} = {a_4^out, a_5^out} — edge {v_4, v_5}
• I_{56} = {a_5^out, a_6^out} — edge {v_5, v_6}
• I_{61} = {a_6^out, a_1^out} — edge {v_6, v_1}
• I_{14} = {a_1^out, a_4^out} — edge {v_1, v_4}

Singleton bundles (capacity 1 each): {a_i^out} for i = 1..6.

Requirement R = 3.

Solution mapping:
Independent set {v_2, v_4, v_6} of size 3:

• Flow: f(a_2^in) = f(a_2^out) = 1, f(a_4^in) = f(a_4^out) = 1, f(a_6^in) = f(a_6^out) = 1, all others 0.
• Bundle checks: I_{12}: f(a_1^out)+f(a_2^out) = 0+1 = 1 ≤ 1. I_{23}: 1+0 = 1 ≤ 1. I_{34}: 0+1 = 1 ≤ 1. I_{45}: 1+0 = 1 ≤ 1. I_{56}: 0+1 = 1 ≤ 1. I_{61}: 1+0 = 1 ≤ 1. I_{14}: 0+1 = 1 ≤ 1.
• Total flow into t = 3 = R. ✓

References

• [Sahni, 1974]: [Sahni1974] S. Sahni (1974). "Computationally related problems". SIAM Journal on Computing 3, pp. 262-279.

[zazabap]

Issue Quality Check — Rule

Check	Result	Details
Usefulness	✅ Pass	No existing path MaximumIndependentSet → IntegralFlowBundles; first incoming reduction for IntegralFlowBundles
Non-trivial	✅ Pass	Gadget construction: vertex arcs + edge bundles encode adjacency as shared capacity constraints
Correctness	⚠️ Warn	Sahni 1974 paper confirmed real; GJ ND36 entry consistent; but paper PDF is scanned image — specific reduction details could not be independently verified from the original text
Well-written	❌ Fail	Multiple issues found (see details below)

Overall: 2 passed, 1 warning, 1 failed

---

Usefulness

Pass. The target problem IntegralFlowBundles already exists in the codebase but currently has zero incoming reductions (reduces_from: []). It only reduces to ILP. Adding this reduction from MaximumIndependentSet would be the first edge connecting IntegralFlowBundles to the rest of the reduction graph, which is highly valuable — it prevents the problem from being an orphan node reachable only from ILP.

No existing direct or composite path exists between MaximumIndependentSet and IntegralFlowBundles.

Non-trivial

Pass. The reduction constructs a directed flow network with bundle capacity constraints that encode independent set adjacency constraints. This involves:

• Creating vertex-specific arc gadgets (s → w_i → t per vertex)
• Encoding edge conflicts as shared-capacity bundles ({a_i, a_j} with capacity 1)
• Mapping the independent set size target to a flow requirement

This is a genuine structural transformation, not a variable relabeling or subtype coercion.

Correctness

Warn. The reference [Sahni, 1974] "Computationally Related Problems", SIAM J. Comput. 3(4):262–279 is confirmed to exist in the project bibliography (docs/paper/references.bib entry sahni1974) with matching title, author, journal, volume, pages, and year. The Garey & Johnson entry ND36 (p.216) cites Sahni 1974 for the reduction from Independent Set, which is consistent with the issue's claims.

However, the actual paper PDF is a scanned image that cannot be machine-read, so I could not independently verify the exact reduction construction described in the issue against the original paper. The construction described in the issue is logically sound (the bundle capacity constraints correctly enforce that at most one endpoint of each edge carries flow), but it is marked with "⚠️ Unverified: AI-generated summary" — it may be a plausible reconstruction rather than the exact construction from Sahni 1974.

Well-written

Fail. Several issues found:

4a: Information Completeness

All template sections are present and substantive. ✅

4b: Algorithm Completeness

The algorithm is reasonably detailed and implementable. ✅

4c: Symbol and Notation Consistency

• Inconsistency between algorithm and example: The algorithm summary refers to arcs as a_i, but the example uses a_i^in and a_i^out (two arcs per vertex). The algorithm's step 1 says "create a path s -> w_i -> t using arc a_i = (w_i, t)" — this only names one arc per vertex, but the construction actually requires two arcs per vertex (s→w_i and w_i→t). The example correctly shows both, but the algorithm description is ambiguous about this.
• Problem name mismatch: The issue uses "INDEPENDENT SET" (decision problem) as the source, but the codebase problem is MaximumIndependentSet (optimization). The issue should clarify which framing is intended and how solution extraction works for the optimization-to-feasibility mapping (MIS value → flow requirement R).

4d: Example Quality

• Suboptimal target value K=2 when maximum IS is 3: The example graph (6-cycle plus diagonal {v_1,v_4}) has a maximum independent set of size 3 (e.g., {v_1, v_3, v_5}). Setting K=2 means the problem is trivially satisfiable and does not test the boundary case. For a meaningful round-trip closed-loop test, K should equal the actual maximum IS size so that only correct reductions produce the right answer. With K=2 and actual optimum 3, any buggy reduction that finds some IS of size >= 2 would pass the test.
• Solution shown is suboptimal: The example shows {v_2, v_5} of size 2, but {v_1, v_3, v_5} is a larger independent set (size 3). A round-trip test that solves the target optimally and maps back would find a different (larger) solution, making the example misleading for verification purposes.
• Recommendation: Either increase K to 3 (the true maximum IS of this graph) and show the optimal solution, or use a different graph where K matches the maximum IS. The example should have at least 2 suboptimal feasible solutions in addition to the optimal one to meaningfully test correctness.

Additional Notes

• The IntegralFlowBundles problem already exists in the codebase with size_fields: ["num_arcs", "num_bundles", "num_vertices"]. The overhead table's code metric names mostly match, though max_bundle_size, max_capacity, and requirement are not actual size fields on the target — they should be removed or clarified as descriptive only.
• The issue correctly notes this is a feasibility (decision) problem, but should explicitly address how it maps to the codebase's MaximumIndependentSet (optimization) framing.

Recommendations

• Fix the example to use K=3 (the actual maximum IS) and show the optimal solution {v_1, v_3, v_5}
• Unify arc naming between the algorithm (uses a_i) and the example (uses a_i^in, a_i^out)
• Remove max_bundle_size, max_capacity, and requirement from the overhead table (not size fields on the target)
• Clarify the optimization-to-feasibility framing for the codebase implementation

[zazabap]

Changelog (fix-issue)

Fixes applied:

1. Source name: "INDEPENDENT SET" → "MaximumIndependentSet" (matches crate naming)
2. Algorithm arc naming: consistent use of a_i^in / a_i^out throughout (step 1 and all subsequent references)
3. Algorithm step 4: R = optimal MIS value (not just K), clarifying the optimization-to-feasibility bridge
4. Optimization-to-feasibility framing: added explanatory paragraph at the top of the algorithm section
5. Overhead table: removed non-size-field rows (max_bundle_size, max_capacity, requirement) — these are instance parameters, not size metrics
6. Example: K=2 → K=3 using optimal solution {v_2, v_4, v_6}; updated all bundle checks and flow values accordingly
7. Validation: updated problem name to MaximumIndependentSet

[zazabap]

Issue Quality Check — Rule (Re-check, --force)

Previous check (2026-03-26): 2 passed, 1 warning, 1 failed. After fix-issue pass: arc naming unified, K updated to 3, overhead table cleaned, optimization-to-feasibility framing added.

Check	Result	Details
Usefulness	✅ Pass	No path MaximumIndependentSet → IntegralFlowBundles; this is the first incoming reduction for IntegralFlowBundles
Non-trivial	✅ Pass	Gadget construction: per-vertex arc pairs + edge bundles encoding adjacency as shared capacity constraints
Correctness	⚠️ Warn	Sahni 1974 confirmed in project bibliography; GJ ND36 consistent; exact construction in paper not independently verifiable (scanned PDF)
Well-written	✅ Pass	All previously failed items fixed: arc naming unified, K=3 matches true MIS, overhead table uses valid size fields only

Overall: 3 passed, 1 warning — previously 1 failed → now 0 failures

---

Usefulness

Pass. pred path MaximumIndependentSet IntegralFlowBundles returns no path. The target problem IntegralFlowBundles currently has reduces_from: [], making it an orphan in the incoming-reduction sense. This reduction would be the first edge connecting it to the rest of the graph (aside from its outgoing ILP edge), which is highly valuable for establishing its NP-hardness chain.

Non-trivial

Pass. The reduction constructs a directed flow network from scratch:

• A fresh source/sink s/t and one intermediate vertex w_i per source vertex (vertex gadgets)
• Two arcs per vertex gadget: a_i^in = (s, w_i) and a_i^out = (w_i, t)
• Edge bundles I_{ij} = {a_i^out, a_j^out} with capacity 1 that encode the adjacency constraint (at most one endpoint selected)
• Singleton bundles per arc enforcing binary flow
• A requirement R = optimal MIS size bridging the optimization-to-feasibility gap

This involves genuine structural transformation (new vertices, arcs, bundle capacity constraints), not a variable relabeling or subtype coercion.

Correctness

Warn. The reference [Sahni, 1974] — S. Sahni, "Computationally Related Problems," SIAM J. Comput. 3(4):262–279 — is confirmed in docs/paper/references.bib (key sahni1974) with matching author, title, journal, volume, pages, and year. The Garey & Johnson entry ND36 (p. 216) cites Sahni 1974 for the reduction from Independent Set, consistent with the issue. The GJ entry also notes the two-arc-per-bundle special case, which matches the construction described.

However, the original paper PDF is a scanned image and cannot be machine-read, so the specific construction (vertex gadgets, arc pairs, bundle layout) could not be verified against the original text. The construction is logically sound and consistent with the GJ entry, but it may be a plausible reconstruction rather than the verbatim Sahni 1974 reduction. No better or more recent construction was found that would supersede this result.

Well-written

Pass. All failures from the prior check have been resolved:

• Arc naming unified (was: inconsistent): Algorithm now consistently uses a_i^in / a_i^out throughout (steps 1–4 and the example), eliminating the prior ambiguity where only a_i was named in the algorithm but two arcs per vertex appeared in the example.
• K=3 (was: K=2): Example now sets R = 3, which equals the true maximum independent set of the example graph. The example graph has exactly two optimal IS solutions — {v_1, v_3, v_5} and {v_2, v_4, v_6} — and shows {v_2, v_4, v_6}, which is genuinely optimal. The round-trip test is now meaningful: only a correct reduction would map to total flow = 3.
• Overhead table cleaned (was: extra rows): max_bundle_size, max_capacity, and requirement rows removed. The three remaining rows — num_vertices, num_arcs, num_bundles — all correspond to actual size_fields on IntegralFlowBundles (["num_arcs", "num_bundles", "num_vertices"]).
• Optimization-to-feasibility framing: A paragraph at the top of the Reduction Algorithm section clarifies that R is set to the optimal MIS value, bridging the optimization (MIS) and feasibility (bundled flow) framings.

One minor note (not a failure): the issue title and GJ entry use "INDEPENDENT SET" (the decision variant), but the source in the body is correctly MaximumIndependentSet. The optimization-to-feasibility bridge paragraph in the algorithm handles this adequately.

Recommendations

• No blocking issues remain. The issue is ready for implementation.
• Consider noting in the algorithm that the optimal MIS value can be determined by running BruteForce::find_witness() on the source instance before constructing the target, as this is the expected implementation pattern for optimization-to-feasibility bridges.