[Model] FixedLengthDisjointPaths

[isPANN]

---

name: Problem
about: Propose a new problem type
title: "[Model] FixedLengthDisjointPaths"
labels: model
assignees: ''

Motivation

MAXIMUM FIXED-LENGTH DISJOINT PATHS (P118) from Garey & Johnson, A2 ND42. A classical NP-complete problem useful for reductions. It is a stricter variant of the length-bounded disjoint paths problem (ND41), requiring each path to have exactly K edges rather than at most K. This arises in uniform-latency network routing where all connections must have the same delay.

Associated reduction rules:

• As source: None found in current rule set.
• As target: R63 (3SAT to MAXIMUM FIXED-LENGTH DISJOINT PATHS)

Definition

Name: FixedLengthDisjointPaths
Canonical name: Maximum Fixed-Length Disjoint Paths (also: Exact-Length Vertex-Disjoint Paths)
Reference: Garey & Johnson, Computers and Intractability, A2 ND42

Mathematical definition:

INSTANCE: Graph G = (V,E), specified vertices s and t, positive integers J,K <= |V|.
QUESTION: Does G contain J or more mutually vertex-disjoint paths from s to t, each involving exactly K edges?

Variables

• Count: J * |V| binary variables (for each of J paths, one variable per vertex indicating inclusion).
• Per-variable domain: binary {0, 1} — whether vertex v is on path j.
• Meaning: The variable assignment encodes J candidate paths from s to t. Each path must have exactly K edges (not fewer, not more). The paths must be vertex-disjoint at internal vertices (s and t are shared). The metric is bool: True if J such paths exist, False otherwise.

Schema (data type)

Type name: FixedLengthDisjointPaths
Variants: graph topology (graph type parameter G)

Field	Type	Description
graph	SimpleGraph	The undirected graph G = (V, E)
source	usize	The source vertex s
sink	usize	The sink vertex t
num_paths_required	usize	J — minimum number of disjoint paths required
fixed_length	usize	K — exact number of edges each path must have

Notes:

• This is a satisfaction (decision) problem: Metric = bool, implementing SatisfactionProblem.
• No weight type is needed.
• Key getter methods: num_vertices() (= |V|), num_edges() (= |E|), num_paths_required() (= J), fixed_length() (= K).
• The key difference from ND41 is "exactly K" vs "at most K" — this makes the problem NP-complete starting at K >= 4 instead of K >= 5.

Complexity

• Decision complexity: NP-complete for fixed K >= 4 (Itai, Perl, and Shiloach, 1982). Solvable in polynomial time for K <= 3.
• Best known exact algorithm: Brute force enumeration of all possible path combinations of exactly K edges. Worst case exponential in |V|.
• Complexity string (for general K >= 4): "2^num_vertices" (brute force)
• Special cases:
  • K <= 3: polynomial time
  • Edge-disjoint version: NP-complete for K >= 4, polynomial for K <= 2, open for K = 3
  • Directed version: same results, except arc-disjoint version is polynomial for K <= 3, open for K = 4
• Comparison with ND41 (length-bounded): The exact-length constraint makes the problem NP-complete one step earlier (K >= 4 vs K >= 5).
• References:
  • A. Itai, Y. Perl, Y. Shiloach (1982). "The complexity of finding maximum disjoint paths with length constraints." Networks, 12(3):277-286. (Journal publication of the 1977 technical report cited in Garey & Johnson as "[Itai, Perl, and Shiloach, 1977]".)

Extra Remark

Full book text:

INSTANCE: Graph G = (V,E), specified vertices s and t, positive integers J,K <= |V|.
QUESTION: Does G contain J or more mutually vertex-disjoint paths from s to t, each involving exactly K edges?
Reference: [Itai, Perl, and Shiloach, 1977]. Transformation from 3SAT.
Comment: Remains NP-complete for fixed K >= 4. Solvable in polynomial time for K <= 3. Corresponding problem for edge-disjoint paths is NP-complete for fixed K >= 4, polynomially solvable for K <= 2, and open for K = 3. The same results hold for directed graphs and directed paths, except that the arc-disjoint version is polynomially solvable for K <= 3 and open for K = 4.

How to solve

• It can be solved by (existing) bruteforce. Enumerate all sets of J vertex-disjoint s-t paths of exactly K edges.
• It can be solved by reducing to integer programming. Multi-commodity flow formulation with binary edge variables per path, flow conservation, vertex-disjointness, and exact path-length constraints (sum of edges per path = K).
• Other: For K <= 3, polynomial-time algorithms exist.

Example Instance

Instance 1 (YES — disjoint paths of exact length exist):
Graph G with 10 vertices {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} and 14 edges:

• Edges: {0,1}, {1,2}, {2,9}, {0,3}, {3,4}, {4,9}, {0,5}, {5,6}, {6,9}, {0,7}, {7,8}, {8,9}, {1,4}, {5,8}
• s = 0, t = 9, J = 3, K = 3

Three vertex-disjoint s-t paths of exactly 3 edges:

• P_1: 0 → 1 → 2 → 9 (exactly 3 edges)
• P_2: 0 → 3 → 4 → 9 (exactly 3 edges)
• P_3: 0 → 5 → 6 → 9 (exactly 3 edges)
• Internal vertex sets: {1,2}, {3,4}, {5,6} — pairwise disjoint ✓
• All paths have exactly 3 edges ✓
• Answer: YES

Instance 2 (NO — paths exist but not of exact length):
Graph G with 6 vertices {0, 1, 2, 3, 4, 5} and 7 edges:

• Edges: {0,1}, {1,5}, {0,2}, {2,3}, {3,5}, {0,4}, {4,5}
• s = 0, t = 5, J = 2, K = 3

Paths from 0 to 5:

• 0 → 1 → 5 (length 2, not exactly 3)
• 0 → 2 → 3 → 5 (length 3 ✓)
• 0 → 4 → 5 (length 2, not exactly 3)
• Only one path of exactly 3 edges exists; J = 2 requires two such paths.
• Answer: NO

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem not yet in the reduction graph
Non-trivial	✅ Pass	Distinct feasibility constraints from all existing problems
Correctness	⚠️ Warn	Complexity threshold claim needs clarification; reference year mismatch
Well-written	⚠️ Warn	Naming convention concern; minor notation issues

Overall: 2 passed, 0 failed, 2 warnings

---

Usefulness

Pass. The problem MaximumFixedLengthDisjointPaths does not exist in the current codebase (24 problems registered). It is a classical NP-complete problem from Garey & Johnson (A2 ND42) with a known reduction from 3SAT, which would connect it to the existing reduction graph. The motivation is clear: it models uniform-latency network routing and is a natural companion to length-bounded disjoint paths problems.

The issue identifies one associated reduction rule (3SAT → MaximumFixedLengthDisjointPaths), which would connect this problem to the existing graph through KSatisfiability.

Non-trivial

Pass. This problem has genuinely different feasibility constraints from all 24 existing problems. The combination of vertex-disjointness, exact path length, and multi-path requirement is not captured by any existing model. It is not a variant of any existing graph problem — it requires path enumeration with length and disjointness constraints, which is structurally distinct from independent sets, covers, colorings, matchings, or any other existing problem type.

Correctness

Warn — complexity threshold needs clarification.

Reference verification: The primary reference — A. Itai, Y. Perl, Y. Shiloach (1982), "The complexity of finding maximum disjoint paths with length constraints," Networks 12(3):277–286 — is a real, well-cited paper (Wiley, NJIT). The DOI is 10.1002/net.3230120306. ✅

Reference year discrepancy: The issue body says "Itai, Perl, and Shiloach (1982)" but the "Extra Remark" section cites "[Itai, Perl, and Shiloach, 1977]" (matching the Garey & Johnson reference, which likely refers to a conference/technical report version). This is a minor inconsistency — the 1982 date is the journal publication, while 1977 is the earlier report cited by Garey & Johnson. Both refer to the same work. Minor issue, no label needed.

NP-completeness threshold: The issue claims the exact-length vertex-disjoint version is NP-complete for fixed K ≥ 4 and polynomial for K ≤ 3. This is consistent with the Garey & Johnson "Full book text" quoted in the issue. Cross-referencing with Golovach & Thilikos (2009, "Paths of Bounded Length and Their Cuts"), who cite Itai, Perl, and Shiloach [19]: they confirm that the bounded version (BVUP, at most l) is polynomial for l ≤ 4 and NP-complete for l ≥ 5. The issue's claim that the exact-length version shifts the threshold one step earlier (K ≥ 4 instead of K ≥ 5) is plausible and consistent with the Garey & Johnson text, but I was unable to independently verify this specific threshold from the paper's abstract alone (the full paper is behind a paywall). The claim is treated as a warning rather than a failure since the Garey & Johnson text explicitly states it.

Complexity string: "2^num_vertices" is stated as brute force. This is acceptable as a conservative bound, though not the best known algorithm — it simply enumerates all configurations. No better exact algorithm was found during the search.

Well-written

Warn — naming convention concern and minor issues.

4a: Information completeness: All required template sections are present and substantive: ✅

• Motivation ✅, Name ✅, Reference ✅, Definition ✅, Variables ✅, Schema ✅, Complexity ✅, How to solve ✅, Example Instance ✅

4b: Definition completeness: The formal definition is clear and taken directly from Garey & Johnson. Input, feasibility constraints (vertex-disjoint, exact K edges), and the decision question are all precisely stated. ✅

4c: Naming convention concern: The problem is named MaximumFixedLengthDisjointPaths but is defined as a satisfaction (decision) problem with Metric = bool. The Maximum prefix in this project is reserved for optimization problems (e.g., MaximumIndependentSet, MaximumClique). Since this is a decision problem ("does G contain J or more..."), the name should either:

1. Drop the Maximum prefix (e.g., FixedLengthDisjointPaths) to follow the convention for satisfaction problems (like Satisfiability, Factoring), or
2. Reformulate as an optimization problem that maximizes the number of disjoint paths (with Metric = SolutionSize<usize> and Direction::Maximize), which would justify the Maximum prefix.

Option 2 would be more natural since the underlying problem is "find the maximum number of vertex-disjoint paths of exactly K edges," and the decision version is derived by asking "is this maximum ≥ J?". The optimization formulation would also be more useful for reductions. ⚠️

4d: Symbol consistency: Symbols are generally consistent across sections. The variables section defines J * |V| binary variables and explains their meaning clearly. The schema fields map to the definition well. Minor: the getter method num_paths_required() returns J, but the complexity string "2^num_vertices" doesn't reference J or K, which is acceptable for a brute-force bound. ✅

4e: Example quality: Two examples provided — one YES and one NO instance. Both are non-trivial and fully worked with step-by-step verification. The YES instance (10 vertices, 14 edges, J=3, K=3) is illustrative, and the NO instance (6 vertices, 7 edges, J=2, K=3) clearly demonstrates why exact-length matters. ✅

Recommendations

• Naming: Consider renaming to FixedLengthDisjointPaths (satisfaction) or reformulating as an optimization problem maximizing the number of paths (which would justify the Maximum prefix). The optimization formulation would be more versatile for reductions.
• Reference year: Clarify that "1977" in the Garey & Johnson citation refers to the technical report, while "1982" is the journal publication.
• Complexity: The "2^num_vertices" bound is very conservative. If the problem is reformulated as optimization, a tighter complexity string accounting for K and J might be appropriate, though brute force is acceptable as a starting point.

[isPANN]

Closing as not planned. This is nearly identical to #298 (LengthBoundedDisjointPaths) — only differs by "exactly K" vs "at most K" edges. Both are leaf nodes in the reduction graph with no outgoing reductions, so keeping only the more general variant (#298).