[Model] IntegralFlowBundles

[isPANN]

Motivation

INTEGRAL FLOW WITH BUNDLES (P112) from Garey & Johnson, A2 ND36. A classical NP-complete problem that generalizes standard network flow by partitioning arcs into "bundles" with shared capacity constraints. While standard network flow (with per-arc capacities) is polynomial, the bundle capacity variant is NP-complete even when all bundle capacities are 1 and all bundles have exactly two arcs.

Associated reduction rules:

• As source: None in current set.
• As target: [Rule] INDEPENDENT SET to INTEGRAL FLOW WITH BUNDLES #366: INDEPENDENT SET → IntegralFlowBundles

Definition

Name: IntegralFlowBundles

Canonical name: INTEGRAL FLOW WITH BUNDLES
Reference: Garey & Johnson, Computers and Intractability, A2 ND36

Mathematical definition:

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?

Variables

• Count: |A| (one variable per arc in the directed graph).
• Per-variable domain: {0, 1, ..., B(a)} where B(a) = min_{j: a ∈ I_j} c_j is the minimum capacity among all bundles containing arc a. In the unit-capacity case (all c_j = 1), domain is {0, 1}.
• Meaning: Each variable f(a) represents the integer flow on arc a. A valid configuration satisfies all bundle capacity constraints (sum of flows within each bundle does not exceed its capacity), flow conservation at non-terminal vertices, and achieves net flow into t of at least R.

Schema (data type)

Type name: IntegralFlowBundles
Variants: None (single variant; problem is always on a directed graph).

Field	Type	Description
num_vertices	usize	Number of vertices |V|
arcs	Vec<(usize, usize)>	Directed arcs (u, v) in the graph
source	usize	Source vertex s
sink	usize	Sink vertex t
bundles	Vec<Vec<usize>>	Bundles I_j, each a list of arc indices
bundle_capacities	Vec<u64>	Capacity c_j for each bundle
requirement	u64	Flow requirement R

Notes:

• This is a satisfaction (decision) problem: Metric = bool, implementing SatisfactionProblem.
• Bundles cover the arc set (every arc belongs to at least one bundle; bundles may overlap).
• Capacities c_j and requirement R are positive integers (Z^+); flow values f(a) are non-negative integers (Z_0^+).
• NP-complete even with all capacities = 1 and all bundles of size 2.
• The non-integral variant can be solved by linear programming.

Complexity

• Best known exact algorithm: The problem is NP-complete (Sahni, 1974). Brute-force enumeration over all integer flow assignments takes O(∏_{a ∈ A} (B(a)+1)) time, where B(a) = min_{j: a ∈ I_j} c_j. With unit capacities, O(2^|A|). No sub-exponential exact algorithm is known.
• Complexity string: "2^num_arcs" (unit-capacity case)
• NP-completeness: Referenced by Garey & Johnson as transformation from INDEPENDENT SET (Sahni, 1974).
• Special cases: With unit capacities and bundles of size 2, the problem is equivalent to finding an independent set in a conflict graph defined by the bundles.
• References:
  • S. Sahni (1974). "Computationally related problems". SIAM Journal on Computing 3, pp. 262-279.

Extra Remark

Full book text:

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.

How to solve

• It can be solved by (existing) bruteforce.
• It can be solved by reducing to integer programming.
• Other: Formulate as an ILP: integer variables f(a) >= 0 for each arc, constraints sum_{a in I_j} f(a) <= c_j for each bundle, flow conservation at each non-terminal vertex, and objective/constraint that net flow into t >= R.

Example Instance

Instance (YES):
Directed graph with 4 vertices {0=s, 1, 2, 3=t} and 6 arcs:

• a_0 = (0,1) -- s to 1
• a_1 = (0,2) -- s to 2
• a_2 = (1,3) -- 1 to t
• a_3 = (2,3) -- 2 to t
• a_4 = (1,2) -- 1 to 2
• a_5 = (2,1) -- 2 to 1

Bundles (all capacity 1):

• I_1 = {a_0, a_1} (capacity 1) -- at most 1 unit leaves s via these arcs combined
• I_2 = {a_2, a_5} (capacity 1) -- bundle linking arc 1->t and 2->1
• I_3 = {a_3, a_4} (capacity 1) -- bundle linking arc 2->t and 1->2

Requirement R = 1.

Solution: f(a_0) = 1, f(a_2) = 1, all others = 0.

• Bundle I_1: f(a_0) + f(a_1) = 1 + 0 = 1 <= 1.
• Bundle I_2: f(a_2) + f(a_5) = 1 + 0 = 1 <= 1.
• Bundle I_3: f(a_3) + f(a_4) = 0 + 0 = 0 <= 1.
• Conservation: vertex 1: in = 1 (a_0), out = 1 (a_2) + 0 (a_4) = 1. vertex 2: in = 0, out = 0.
• Net flow into t: f(a_2) + f(a_3) = 1 >= R = 1. Answer: YES.

Instance (NO):
Same graph and bundles but R = 2.

• Bundle I_1 limits total outflow from s to 1, so max flow into the network is 1. Cannot achieve R = 2.
• Answer: NO.

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem not yet in reduction graph
Non-trivial	✅ Pass	Distinct feasibility constraints from all existing problems
Correctness	⚠️ Warn	Sahni (1974) verified as real paper; specific reduction from INDEPENDENT SET not independently verified from paper text
Well-written	❌ Fail	Multiple issues: contradictory notes on bundles, naming inconsistency, missing brute-force solver option, domain upper bound issue

Overall: 2 passed, 1 warning, 1 failed

---

Usefulness

Pass. The problem IntegralFlowBundles does not exist in the current codebase (24 problems currently implemented). It generalizes standard network flow in a genuinely different way (bundle capacity constraints on arc subsets), and the issue identifies a planned reduction rule (R57: INDEPENDENT SET → INTEGRAL FLOW WITH BUNDLES) that would connect it to the existing reduction graph.

Non-trivial

Pass. This is a genuine network flow variant with shared capacity constraints across arc bundles — structurally different from all existing problems in the codebase. No existing problem captures bundle capacity constraints. The feasibility condition (per-bundle capacity + flow conservation + flow requirement) is distinct from ILP, QUBO, or any graph problem currently implemented.

Correctness

Warn. Partial verification:

• Sahni (1974) paper exists: Confirmed. "Computationally Related Problems," SIAM Journal on Computing 3, pp. 262–279, 1974. The paper discusses "Problem N(iv): Integer flows with bundles" among problems shown to be computationally equivalent (all polynomial-time solvable iff any one is).
• Garey & Johnson reference: The problem is listed as ND36 in the G&J appendix, and appears in the Wikipedia list of NP-complete problems. The G&J entry says "Transformation from INDEPENDENT SET" with reference to Sahni (1974).
• Specific reduction claim: The issue states "NP-completeness proved by Sahni (1974) via reduction from INDEPENDENT SET." This is consistent with the G&J entry, but I could not independently verify the specific reduction from the paper text (PDF was not machine-readable). The Sahni paper's abstract describes showing problems are "computationally related" (polynomial-time equivalent), which is consistent with showing NP-completeness via reductions between them. The claim is plausible but not independently confirmed from the original paper.
• Complexity bound: The issue correctly states that brute-force takes O(prod(C_max+1)) over all arcs, and O(2^|A|) for unit capacities. No sub-exponential algorithm claim is made, which is appropriate for a satisfaction problem.
• Special case claim: "With unit capacities and bundles of size 2, the problem is equivalent to finding an independent set in a conflict graph defined by the bundles" — this is a reasonable interpretation consistent with the G&J comment.

Well-written

Fail. Several issues found:

1. Contradictory notes on bundles: The Notes section states: "Bundles partition the arc set (every arc belongs to at least one bundle; bundles may overlap)." This is self-contradictory — a partition requires that elements belong to exactly one subset (no overlap). The mathematical definition only requires that the union of all bundles covers A (i.e., a cover), and does not require disjointness. The Notes should say "Bundles cover the arc set" not "partition," or should clarify that bundles may overlap. The G&J definition uses "bundles I_1,...,I_k ⊆ A such that ∪ I_j = A" which is a cover, not a partition.

2. Per-variable domain issue: The Variables section says "Per-variable domain: {0, 1, ..., C_max} where C_max = max_j c_j." This is not quite right — the per-arc flow is bounded by the minimum bundle capacity among all bundles containing that arc, not the global maximum capacity. The actual upper bound per arc a is min_{j: a ∈ I_j} c_j, which could be much smaller than max_j c_j. For the dims() implementation, each arc's domain size needs to be determined from the bundle capacities of the bundles it belongs to.

3. Brute-force solver unchecked: The "How to solve" section leaves brute-force unchecked, but this is a satisfaction problem with finite discrete domains — brute-force enumeration is always applicable. It should be checked.

4. Symbol inconsistency: The Schema uses u64 for bundle_capacities and requirement, but the Definition uses Z^+ (positive integers) and Z_0^+ (non-negative integers). While u64 is a reasonable implementation choice, the issue should note that the R and c_j values are positive (not zero) per the formal definition, and the flow values are non-negative.

5. Naming: The issue uses IntegralFlowBundles as the type name. Per project naming conventions, a more descriptive name like IntegralFlowWithBundles would better match the canonical name "INTEGRAL FLOW WITH BUNDLES." This is a minor point but worth considering for clarity.

Recommendations

• Fix the contradictory partition/cover statement in Notes.
• Correct the per-variable domain description to reflect per-arc bounds based on containing bundles.
• Check the brute-force solver option.
• Consider renaming to IntegralFlowWithBundles for consistency with the canonical name.
• Add a note about the positivity constraint on capacities and requirement vs. non-negativity of flow values.

[GiggleLiu]

Fix-issue changelog

• Removed template frontmatter block from issue body
• Fixed contradictory "partition" statement in Notes → "Bundles cover the arc set (every arc belongs to at least one bundle; bundles may overlap)"
• Corrected per-variable domain bound from max_j c_j to min_{j: a ∈ I_j} c_j (minimum capacity among containing bundles)
• Checked brute-force solver box
• Added complexity string "2^num_arcs" for declare_variants!
• Added note about positivity constraints (capacities/requirement are Z^+, flow values are Z_0^+)
• Updated associated rules reference to use issue [Rule] INDEPENDENT SET to INTEGRAL FLOW WITH BUNDLES #366

Applied by /fix-issue.