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

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.