[Model] MinimumEdgeCostFlow

[isPANN]

Motivation

MINIMUM EDGE-COST FLOW (P108) from Garey & Johnson, A2 ND32. A classical NP-hard problem useful for reductions.

Associated rules:

• R53: X3C -> MINIMUM EDGE-COST FLOW (establishes NP-hardness via reduction from Exact Cover by 3-Sets [Even and Johnson, 1977])

This problem is a fixed-charge variant of the standard minimum-cost flow problem. Unlike standard min-cost flow (which is polynomial with linear costs), the edge-cost version charges a fixed price p(a) for each arc that carries any nonzero flow. This fixed-charge structure is what makes the problem NP-hard. The problem remains NP-hard even when capacities are 2 and prices are 0 or 1, but becomes polynomial when all capacities are 1.

Definition

Name: MinimumEdgeCostFlow
Reference: Garey & Johnson, Computers and Intractability, A2 ND32

Mathematical definition:

INSTANCE: Directed graph G = (V,A), specified vertices s and t, capacity c(a) ∈ Z^+ and price p(a) ∈ Z_0^+ for each a ∈ A, requirement R ∈ Z^+.
OBJECTIVE: Find a flow function f: A → Z_0^+ that minimizes the total edge cost Σ_{a ∈ A': f(a)≠0} p(a) subject to:
(1) f(a) ≤ c(a) for all a ∈ A,
(2) for each v ∈ V − {s,t}, Σ_{(u,v) ∈ A} f((u,v)) = Σ_{(v,u) ∈ A} f((v,u)), i.e., flow is "conserved" at v,
(3) Σ_{(u,t) ∈ A} f((u,t)) − Σ_{(t,u) ∈ A} f((t,u)) ≥ R, i.e., the net flow into t is at least R.

The objective value is Min(Σ_{a ∈ A'} p(a)) where A' = {a ∈ A: f(a) ≠ 0}.

Variables

• Count: |A| (one variable per arc, representing the flow on that arc)
• Per-variable domain: {0, 1, ..., c(a)} -- the integer flow on arc a, bounded by its capacity
• Meaning: f(a) ∈ {0, ..., c(a)} assigns an integer flow value to each arc. A feasible solution satisfies capacity constraints, flow conservation at non-terminal vertices, and delivers at least R units of flow to the sink. The objective minimizes the total fixed price of arcs carrying nonzero flow.

Schema (data type)

Type name: MinimumEdgeCostFlow
Variants: none (operates on a general directed graph with fixed-charge edge costs)

Field	Type	Description
num_vertices	usize	Number of vertices
edges	Vec<(usize, usize, i64, i64)>	Directed arcs: (source, target, capacity, price)
source	usize	Index of source vertex s
sink	usize	Index of sink vertex t
required_flow	i64	Minimum flow requirement R

Complexity

• Best known exact algorithm: The problem is NP-hard (G&J ND32). It is a special case of the fixed-charge network flow problem. The brute-force approach enumerates all feasible integer flow assignments, giving a worst-case complexity of O((max_capacity + 1)^num_edges) where max_capacity is the maximum arc capacity. Standard approaches use branch-and-bound or branch-and-cut methods via ILP formulation. For small capacities (c(a) = 1 for all a), the problem is polynomial [Even and Johnson, 1977]. When the fixed-charge cost is replaced by the linear cost Σ p(a)*f(a), the problem becomes the standard polynomial-time min-cost flow [Lawler, 1976a].

Extra Remark

Full book text:

INSTANCE: Directed graph G = (V,A), specified vertices s and t, capacity c(a) ∈ Z^+ and price p(a) ∈ Z_0^+ for each a ∈ A, requirement R ∈ Z^+, bound B ∈ 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}, Σ_{(u,v) ∈ A} f((u,v)) = Σ_{(v,u) ∈ A} f((v,u)), i.e., flow is "conserved" at v,
(3) Σ_{(u,t) ∈ A} f((u,t)) − Σ_{(t,u) ∈ A} f((t,u)) ≥ R, i.e., the net flow into t is at least R, and
(4) if A' = {a ∈ A: f(a) ≠ 0}, then Σ_{a ∈ A'} p(a) ≤ B?
Reference: [Even and Johnson, 1977]. Transformation from X3C.
Comment: Remains NP-complete if c(a) = 2 and p(a) ∈ {0,1} for all a ∈ A. Solvable in polynomial time if c(a) = 1 for all a ∈ A [Even and Johnson, 1977] or if (4) is replaced by Σ_{a ∈ A} p(a)·f(a) ≤ B (e.g., see [Lawler, 1976a]). However, becomes NP-complete once more if (4) is replaced by Σ_{a ∈ A} (p_1(a)f(a)^2 + p_2(a)f(a)) ≤ B [Herrmann, 1973].

How to solve

• It can be solved by (existing) bruteforce. (Enumerate all possible integer flow assignments on each arc within capacity bounds; check feasibility and flow requirement; return minimum edge cost.)
• It can be solved by reducing to integer programming. (ILP with integer flow variables and binary indicator variables for nonzero flow; capacity constraints, flow conservation, flow requirement; minimize total price of active arcs.) See companion issue [Rule] MinimumEdgeCostFlow to ILP #962.
• Other: Branch-and-bound methods for fixed-charge network flow.

Reduction Rule Crossref

• [Rule] MinimumEdgeCostFlow to ILP #962 — [Rule] MinimumEdgeCostFlow to ILP (direct ILP formulation)

Example Instance

Input:
G = (V, A) with V = {0, 1, 2, 3, 4} (5 vertices), source s = 0, sink t = 4, required flow R = 3.

The graph has three parallel paths from s to t, each via a different intermediate vertex:

• Path via v1: arcs (0,1) and (1,4), price 3+0 = 3 (expensive)
• Path via v2: arcs (0,2) and (2,4), price 1+0 = 1 (cheapest)
• Path via v3: arcs (0,3) and (3,4), price 2+0 = 2 (medium)

Arcs (source, target, capacity, price):

1. (0, 1, 2, 3) — s to v1, capacity 2, price 3
2. (0, 2, 2, 1) — s to v2, capacity 2, price 1
3. (0, 3, 2, 2) — s to v3, capacity 2, price 2
4. (1, 4, 2, 0) — v1 to t, capacity 2, price 0
5. (2, 4, 2, 0) — v2 to t, capacity 2, price 0
6. (3, 4, 2, 0) — v3 to t, capacity 2, price 0

Why not all paths can be avoided: Each path has capacity 2, so a single path can deliver at most 2 units of flow. Since R = 3, at least two paths must be used. The fixed-charge cost depends on which paths carry nonzero flow, not on how much flow each carries.

Optimal solution:
Use the two cheapest paths (via v2 and v3), avoiding the expensive path via v1:

• f(0,2) = 1, f(2,4) = 1 (path via v2)
• f(0,3) = 2, f(3,4) = 2 (path via v3)
• All other flows = 0

Verification:

• Capacity: all flows within bounds ✓
• Conservation: v1: 0=0 ✓; v2: 1=1 ✓; v3: 2=2 ✓
• Flow requirement: net flow into t = 1 + 2 = 3 ≥ R = 3 ✓
• Active arcs: {(0,2), (0,3), (2,4), (3,4)} with prices {1, 2, 0, 0}, total edge cost = 3

Expected Outcome

Optimal value: Min(3) — the minimum total edge cost to deliver R = 3 units of flow is 3, achieved by using the two cheapest paths (prices 1 + 2 = 3) and avoiding the expensive path (price 3). There are 17 feasible solutions with 4 distinct cost values (3, 4, 5, 6), and 3 optimal solutions all using the same pair of active arcs with different flow distributions.

[isPANN]

Issue Quality Check — Model

Check	Result	Details
Usefulness	⚠️ Warn	Problem is novel, but ILP solver claim lacks companion issue
Non-trivial	✅ Pass	Distinct fixed-charge flow feasibility; not isomorphic to any existing problem
Correctness	⚠️ Warn	[Even and Johnson, 1977] reference cannot be independently verified; complexity section lacks concrete expression
Well-written	❌ Fail	Missing concrete complexity expression; ILP claim not backed by companion issue

Overall: 1 passed, 2 warnings, 1 failed

---

Usefulness

Pass (with warning). The problem MinimumEdgeCostFlow does not exist in the codebase (confirmed via pred show). The issue mentions a planned reduction R53: X3C -> MinimumEdgeCostFlow, and ExactCoverBy3Sets already exists in the reduction graph, so the problem would not be orphaned.

However, the "How to solve" section checks ILP as a solver path but does not link a companion [Rule] MinimumEdgeCostFlow to ILP issue. Per project conventions, if direct ILP solving is claimed, a companion issue must be linked. Warning: Add a [Rule] MinimumEdgeCostFlow to ILP companion issue or remove the ILP claim.

Non-trivial

Pass. The problem has genuinely distinct feasibility constraints from all existing problems. While there are several flow-related problems already in the codebase (DirectedTwoCommodityIntegralFlow, IntegralFlowBundles, IntegralFlowHomologousArcs, IntegralFlowWithMultipliers, PathConstrainedNetworkFlow, UndirectedFlowLowerBounds, UndirectedTwoCommodityIntegralFlow), none of them model the fixed-charge edge-cost structure where a price p(a) is charged once for each arc carrying nonzero flow. This is a fundamentally different objective criterion from standard min-cost flow (linear costs) or commodity-restricted flow variants.

Correctness

Warning — reference verification inconclusive.

1. [Even and Johnson, 1977]: This reference is cited as the source of the NP-completeness proof via transformation from X3C. However, I could not independently verify this paper exists. The G&J bibliography may reference it (the issue faithfully reproduces what appears to be the G&J entry for ND32), but the actual paper by "Even and Johnson" from 1977 does not appear in Google Scholar, Semantic Scholar, or arxiv. It is possible this is a technical report or proceedings paper not indexed online, or the authorship may be slightly different (e.g., Johnson, Lenstra, and Rinnooy Kan published "The Complexity of the Network Design Problem" in Networks, 1978). Without verifying the original paper, the NP-completeness claim via X3C reduction cannot be independently confirmed — though the claim itself is plausible given G&J's authority.

2. [Herrmann, 1973]: Referenced in the Extra Remark section for the quadratic cost variant. Not verified.

3. [Lawler, 1976a]: Referenced for the polynomial-time linear-cost variant. A lawler1978 entry exists in the project bibliography but covers scheduling, not network flow. The specific "1976a" reference was not verified.

4. Complexity section: The issue states "No known exact algorithm improves substantially over the O(prod c(a)) brute-force enumeration" but does not provide a concrete complexity expression in terms of problem size parameters (e.g., num_arcs, max_capacity). A concrete expression like (max_capacity + 1)^num_arcs is required.

5. Definition correctness: The mathematical definition is well-formed and consistent with the standard fixed-charge network flow formulation. The feasibility constraints (capacity, conservation, flow requirement, edge-cost bound) are clearly stated.

Well-written

Fail — multiple items need attention.

4a: Information Completeness

Section	Status
Motivation	✅ Present and substantive
Name	✅ Valid
Reference	✅ G&J ND32 cited
Definition	✅ Formal and complete
Variables	✅ Present
Schema	✅ Complete field table
Complexity	❌ Missing concrete complexity expression — must provide a formula like (max_capacity + 1)^num_arcs, not just prose
How to solve	⚠️ ILP checked but no companion [Rule] issue linked
Example Instance	✅ Present
Expected Outcome	✅ YES answer with verification

4b: Definition Completeness

The definition is precise and implementable — input structure, feasibility constraints, and the decision question are all clearly stated with explicit quantifiers.

4c: Symbol and Notation Consistency

Symbols are consistent across sections. The schema field names (num_vertices, edges, source, sink, required_flow, bound) align with the definition's V, A, s, t, R, B.

4d: Example Quality

The example has 5 vertices and 6 arcs with a search space of 729 configurations. The proposed solution is mathematically correct (verified: capacity, conservation, flow requirement, and edge-cost bound all satisfied). The instance has both feasible and infeasible configurations, making it suitable for round-trip testing.

Specific failures:

1. Complexity expression missing: The Complexity section describes the problem's NP-completeness status and discusses special cases but does not provide the required concrete complexity expression (e.g., (max_capacity + 1)^num_arcs). This is required by the template.
2. ILP companion issue not linked: The "How to solve" section claims ILP solvability but does not reference a companion [Rule] MinimumEdgeCostFlow to ILP issue.

Recommendations

• Add a concrete complexity expression to the Complexity section, e.g., "(max_capacity + 1)^num_arcs" to match the brute-force enumeration bound.
• Either file a companion [Rule] MinimumEdgeCostFlow to ILP issue and link it, or uncheck the ILP box.
• Consider verifying the [Even and Johnson, 1977] reference more precisely — it may be a technical report or the authorship may differ from what G&J cites.
• The edges field type Vec<(usize, usize, i64, i64)> packs capacity and price into a tuple. Consider whether separate capacities and prices vectors or a named struct would be clearer for implementation.

[isPANN]

Converted from decision framing (with bound B) to optimization framing: the objective now minimizes total edge cost subject to capacity, conservation, and flow requirement constraints. Removed the bound field from the schema. Removed PoorWritten label.

[isPANN]

Fix-issue changelog

• Complexity: added concrete brute-force expression (max_capacity + 1)^num_edges
• Example: replaced incorrect example (claimed solution f(3,4)=3 exceeded capacity 2; claimed optimal Min(2) was wrong — actual optimal was Min(3)) with new 3-parallel-paths example: 5 vertices, 6 arcs, R=3, 17 feasible solutions, 4 distinct cost values (3,4,5,6), optimal Min(3)
• ILP companion: created [Rule] MinimumEdgeCostFlow to ILP #962 [Rule] MinimumEdgeCostFlow to ILP and linked in new "Reduction Rule Crossref" section
• Expected Outcome: added explicit section with Min(3) and solution statistics
• How to solve: updated ILP bullet to reference companion issue [Rule] MinimumEdgeCostFlow to ILP #962

Applied by /fix-issue.