[Model] IntegralFlowHomologousArcs

[isPANN]

Motivation

INTEGRAL FLOW WITH HOMOLOGOUS ARCS (P111) from Garey & Johnson, A2 ND35. A classical NP-complete problem that generalizes standard network flow by requiring equal flow on designated pairs of "homologous" arcs. The integrality constraint combined with the equal-flow requirement makes the problem intractable, even though the non-integral variant reduces to linear programming.

Associated reduction rules:

• As source: [Rule] IntegralFlowHomologousArcs → ILP #733: IntegralFlowHomologousArcs → ILP
• As target: [Rule] Satisfiability → IntegralFlowHomologousArcs #732: Satisfiability → IntegralFlowHomologousArcs, [Rule] 3SAT to INTEGRAL FLOW WITH HOMOLOGOUS ARCS #365: 3SAT → IntegralFlowHomologousArcs

Definition

Name: IntegralFlowHomologousArcs

Canonical name: INTEGRAL FLOW WITH HOMOLOGOUS ARCS
Reference: Garey & Johnson, Computers and Intractability, A2 ND35

Mathematical definition:

INSTANCE: Directed graph G = (V,A), specified vertices s and t, capacity c(a) ∈ Z^+ for each a ∈ A, requirement R ∈ Z^+, set H ⊆ A × A of "homologous" pairs of arcs.
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}, flow is conserved at v,
(3) for all pairs <a,a'> ∈ H, f(a) = f(a'), and
(4) 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, ..., c(a)} where c(a) is the capacity of arc a. In the unit-capacity case, domain is {0, 1}.
• Meaning: Each variable f(a) represents the integer flow on arc a. A configuration is a valid integral flow if it satisfies capacity constraints, flow conservation at all non-terminal vertices, equal-flow constraints on homologous pairs, and achieves total flow into t of at least R.

Schema (data type)

Type name: IntegralFlowHomologousArcs
Variants: None (single variant; problem is always on a directed graph with integer capacities).

Field	Type	Description
num_vertices	usize	Number of vertices |V|
arcs	Vec<(usize, usize)>	Directed arcs (u, v) in the graph
capacities	Vec<u64>	Capacity c(a) for each arc
source	usize	Source vertex s
sink	usize	Sink vertex t
requirement	u64	Flow requirement R
homologous_pairs	Vec<(usize, usize)>	Pairs of arc indices that must carry equal flow

Notes:

• This is a satisfaction (decision) problem: Metric = bool, implementing SatisfactionProblem.
• The problem asks whether there exists an integral flow meeting all constraints.
• NP-complete even with unit capacities (c(a) = 1 for all a).
• The non-integral version is polynomially equivalent to LINEAR PROGRAMMING.

Complexity

• Best known exact algorithm: The problem is NP-complete (Sahni, 1974). Brute-force enumeration over all possible integer flow assignments takes O(∏_{a ∈ A} (c(a)+1)) time. With unit capacities, this is O(2^|A|). No significantly better exact algorithm is known for the general case.
• Complexity string: "2^num_arcs" (unit-capacity case)
• NP-completeness: Referenced by Garey & Johnson as transformation from 3SAT (Sahni, 1974). Remains NP-complete with unit capacities (Even, Itai, and Shamir, 1976).
• Special cases: The variant without integrality constraint (allowing real-valued flows with equal-flow constraints) is polynomially equivalent to LINEAR PROGRAMMING (Itai, 1977).
• References:
  • S. Sahni (1974). "Computationally related problems". SIAM Journal on Computing 3, pp. 262-279.
  • S. Even, A. Itai, A. Shamir (1976). "On the complexity of timetable and multicommodity flow problems". SIAM J. Comput. 5, pp. 691-703.
  • A. Itai (1977). "Two commodity flow". Dept. of Computer Science, Technion. (Technical report; the journal version may have appeared in 1978.)

Extra Remark

Full book text:

INSTANCE: Directed graph G = (V,A), specified vertices s and t, capacity c(a) ∈ Z^+ for each a ∈ A, requirement R ∈ Z^+, set H ⊆ A × A of "homologous" pairs of arcs.
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}, flow is conserved at v,
(3) for all pairs <a,a'> ∈ H, f(a) = f(a'), and
(4) the net flow into t is at least R?
Reference: [Sahni, 1974]. Transformation from 3SAT.
Comment: Remains NP-complete if c(a) = 1 for all a ∈ A (by modifying the construction in [Even, Itai, and Shamir, 1976]). Corresponding problem with non-integral flows is polynomially equivalent to LINEAR PROGRAMMING [Itai, 1977].

How to solve

• It can be solved by (existing) bruteforce.
• It can be solved by reducing to integer programming.
• Other: Enumerate all integer flow assignments on arcs (exponential), check capacity, conservation, homologous-pair, and requirement constraints. Alternatively, formulate as an ILP with flow variables, capacity constraints, conservation constraints, and equality constraints for homologous pairs.

Example Instance

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

• a_0 = (0,1) cap 1, a_1 = (0,2) cap 1, a_2 = (1,3) cap 1, a_3 = (2,3) cap 1
• a_4 = (1,4) cap 1, a_5 = (2,4) cap 1, a_6 = (3,5) cap 1, a_7 = (4,5) cap 1
• Homologous pairs: H = {(a_2, a_5), (a_4, a_3)} meaning f(a_2)=f(a_5) and f(a_4)=f(a_3).
• Requirement R = 2.

Solution: f(a_0)=1, f(a_1)=1, f(a_2)=1, f(a_5)=1, f(a_4)=0, f(a_3)=0, f(a_6)=1, f(a_7)=1.

• Capacity: all flows <= 1.
• Conservation: vertex 1: in=1(a_0), out=1(a_2)+0(a_4)=1. vertex 2: in=1(a_1), out=0(a_3)+1(a_5)=1. vertex 3: in=1(a_2)+0(a_3)=1, out=1(a_6). vertex 4: in=0(a_4)+1(a_5)=1, out=1(a_7).
• Homologous: f(a_2)=f(a_5)=1, f(a_4)=f(a_3)=0.
• Net flow into t=5: f(a_6)+f(a_7) = 2 >= R=2. Answer: YES.

Instance (NO):
Directed graph with 4 vertices {0=s, 1, 2, 3=t} and 4 arcs (all unit capacity):

• a_0 = (0,1) cap 1, a_1 = (0,2) cap 1, a_2 = (1,2) cap 1, a_3 = (2,3) cap 1
• Homologous pairs: H = {(a_0, a_1)}, meaning f(a_0) = f(a_1).
• Requirement R = 1.

Without the homologous constraint, R = 1 is achievable: send flow along s→1→2→t with f(a_0)=1, f(a_2)=1, f(a_3)=1, f(a_1)=0. Flow into t = 1 ≥ R.

With H: f(a_0) = f(a_1), so both must be 0 or 1 (unit capacity).

• If f(a_0) = f(a_1) = 1: by conservation at vertex 1, f(a_2) = f(a_0) = 1. At vertex 2: inflow = f(a_1) + f(a_2) = 1 + 1 = 2, but outflow = f(a_3) ≤ 1. Conservation violated.
• If f(a_0) = f(a_1) = 0: no flow enters the network. Flow = 0 < R = 1.
  Answer: NO. The homologous constraint forces equal flow on both paths out of s, creating a bottleneck at vertex 2 that prevents any feasible flow of value 1.

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	⚠️ Warn	Novel problem, but no planned reduction rules as source; only one incoming rule mentioned
Non-trivial	✅ Pass	Distinct feasibility constraints (homologous arc equality) not present in any existing problem
Correctness	⚠️ Warn	Main references verified; Itai 1977 reference may actually be Itai 1978; Sahni reduction is from Non-Tautology, not 3SAT
Well-written	❌ Fail	Example NO instance is self-contradictory; brute-force solver unchecked; naming convention issue; missing complexity string

Overall: 1 passed, 2 warnings, 1 failed

---

Usefulness

The problem IntegralFlowHomologousArcs does not exist in the current codebase (confirmed via pred show). It is a classical NP-complete problem from Garey & Johnson (A2 ND35), which adds legitimacy.

However, the issue lists no outgoing reductions ("As source: None") and only one incoming rule (R56: 3SAT -> Integral Flow). A problem with only one incoming edge and no outgoing edges has limited utility in the reduction graph. The Motivation section explains why the problem is theoretically interesting but does not describe concrete use cases (quantum computing, scheduling, etc.) or what further reductions this problem would enable.

Verdict: Warn — the problem is novel but risks being an orphan node without planned outgoing reductions.

Non-trivial

This is a genuinely distinct problem. The combination of:

• Integer flow on a directed graph
• Capacity constraints
• Flow conservation
• Homologous arc equality constraints (pairs of arcs must carry equal flow)
• Flow requirement threshold

...is not equivalent to any existing problem in the codebase. The homologous arc equality constraint is the distinguishing feature — standard network flow, ILP, and other existing problems do not capture this structure directly.

Checked against all 24 existing problems via pred list. No isomorphism found.

Verdict: Pass

Correctness

Reference verification:

1. Sahni (1974), "Computationally Related Problems", SIAM J. Comput. 3, pp. 262-279 — Verified. The paper exists and is published as cited. However, the issue states the NP-completeness proof is "via reduction from 3SAT." According to the literature, Sahni's original reduction is from Non-Tautology (complement of Tautology), not 3SAT. Garey & Johnson's appendix may describe it as a transformation from 3SAT, but the original paper uses a different source problem. This is a minor inaccuracy.

2. Even, Itai, Shamir (1976), "On the Complexity of Timetable and Multicommodity Flow Problems", SIAM J. Comput. 5, pp. 691-703 — Verified. The paper exists with correct authors, title, journal, volume, and pages. The paper proves NP-completeness of multicommodity integral flow even with two commodities. The issue's claim that unit-capacity NP-completeness follows from "modifying the construction" in this paper is consistent with Garey & Johnson's note.

3. Itai (1977), polynomial equivalence to LINEAR PROGRAMMING — The issue cites "Itai, 1977" but Alon Itai's relevant publication on two-commodity flow appeared in JACM in 1978, not 1977. The year may be off by one. The claim that the non-integral version is polynomially equivalent to LP is supported by modern literature (Ding et al. confirm this connection).

Verdict: Warn — References exist and broadly support the claims, but (a) the Sahni reduction source problem is described imprecisely, and (b) the Itai year may be 1978 rather than 1977.

Well-written

Several issues found:

4a: Information Completeness

• How to solve: The "brute-force" checkbox is unchecked, yet the problem has finite discrete domains and could be solved by brute force (enumerate all flow assignments). This should be checked, or an explanation given for why brute-force is not applicable.
• Complexity section: No concrete complexity string suitable for declare_variants! is provided. The issue says "O(2^|A|)" for unit capacities but does not provide a best-known exact algorithm with a precise base (the project requires strings like "2^num_arcs" with concrete numeric values).

4b: Naming Convention
The proposed name IntegralFlowHomologousArcs does not follow the project's naming conventions. Satisfaction problems in the codebase use descriptive names without optimization prefixes (e.g., Satisfiability, CircuitSAT, Factoring). The name is acceptable but unusually long. Consider whether a shorter canonical name exists.

4c: Symbol Consistency
Symbols are generally consistent between sections. The Definition, Variables, and Schema sections all use compatible notation.

4d: Example Quality

• YES instance: Well-constructed and fully worked. Flow values are shown, all constraints verified step by step. Good.
• NO instance: Self-contradictory. The issue first proposes H = {(a_0, a_1), (a_6, a_7)} with R = 2, then works through the logic and concludes "this is actually YES as well." It then changes to R = 3, giving a trivial NO instance (max flow is 2, so R = 3 is obviously infeasible). A proper NO instance should demonstrate infeasibility due to the homologous arc constraints specifically, not just because the requirement exceeds the max flow. This defeats the purpose of illustrating the problem's difficulty.

Verdict: Fail — The NO example is poorly constructed (self-contradictory, then trivially infeasible). The brute-force solver option should be checked. Missing concrete complexity string for implementation.

Recommendations

• Fix the NO example: construct an instance where R would be achievable without the homologous constraints but becomes infeasible with them. This demonstrates the problem's hardness.
• Check the brute-force solver box — the problem has finite domains and brute-force enumeration is straightforward.
• Provide a concrete complexity string for declare_variants! (e.g., "2^num_arcs" for unit-capacity case).
• Verify Itai reference year: likely 1978, not 1977.
• Clarify that Sahni's original reduction is from Non-Tautology (or cite Garey & Johnson directly for the 3SAT transformation).
• Consider adding at least one planned outgoing reduction to avoid an orphan node in the reduction graph.

[GiggleLiu]

Fix-issue changelog

• Removed template frontmatter block from issue body
• Updated associated rules: added [Rule] IntegralFlowHomologousArcs → ILP #733 (IntegralFlowHomologousArcs → ILP) as outgoing, added [Rule] Satisfiability → IntegralFlowHomologousArcs #732 (Satisfiability →) as additional incoming rule
• Checked brute-force solver box (problem has finite discrete domains)
• Clarified Sahni NP-completeness citation: "Referenced by Garey & Johnson as transformation from 3SAT (Sahni, 1974)"
• Added complexity string "2^num_arcs" for declare_variants!
• Added note about Itai (1977) being a Technion technical report (journal version may be 1978)
• Replaced self-contradictory NO example with clean 4-vertex instance demonstrating homologous-constraint-induced infeasibility

Applied by /fix-issue.