[Model] LengthBoundedDisjointPaths

[isPANN]

---

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

Motivation

LENGTH-BOUNDED DISJOINT PATHS from Garey & Johnson, A2 ND41. A classical NP-complete problem useful for reductions. It models the routing problem where multiple connections must share a network between the same source-sink pair, with quality-of-service constraints on path length. Applications include telecommunications routing and VLSI design.

Associated reduction rules:

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

Definition

Name: LengthBoundedDisjointPaths
Canonical name: Length-Bounded Disjoint Paths (also: Length-Constrained Vertex-Disjoint Paths)
Reference: Garey & Johnson, Computers and Intractability, A2 ND41

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, none involving more than K edges?

Variables

• Count: J * |V| binary variables. For each of J path slots and each vertex v, a binary variable x_{j,v} indicates whether vertex v is on path j.
• Per-variable domain: binary {0, 1}.
• dims() specification: vec![2; num_paths_required * num_vertices] — J * |V| binary variables, laid out as path 0's vertices first, then path 1's vertices, etc.
• Meaning: The variable assignment encodes J candidate paths from s to t. For each path slot j (0 <= j < J), the selected vertices must form a simple s-t path of at most K edges in G. The paths must be vertex-disjoint at internal vertices (s and t are shared). The metric is bool: True if the encoded paths satisfy all constraints, False otherwise.

Schema (data type)

Type name: LengthBoundedDisjointPaths<G> where G: GraphSpec (default SimpleGraph)
Variants: graph topology (graph type parameter G)

Field	Type	Description
graph	G	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
max_length	usize	K — maximum number of edges per path

Size fields (getter methods for overhead expressions):

• num_vertices() -> usize (= |V|)
• num_edges() -> usize (= |E|)
• num_paths_required() -> usize (= J)
• max_length() -> usize (= K)

Notes:

• This is a satisfaction (decision) problem: Metric = bool, implementing SatisfactionProblem.
• No weight type is needed.
• Note: s and t are shared by all paths; the vertex-disjointness applies to internal vertices only.

Complexity

• Decision complexity: NP-complete for all fixed K >= 5 (Itai, Perl, and Shiloach, 1982). Solvable in polynomial time for K <= 4.
• Best known exact algorithm: For fixed K, brute force enumeration of all possible path combinations. For general K, this is equivalent to a constrained multi-commodity flow problem. Worst case exponential in |V|. For fixed J and K, the search space is polynomial O(n^{JK}).
• Parameterized complexity: FPT when parameterized by J + K on certain graph classes. On general graphs, W[1]-hard parameterized by various combinations of parameters.
• Complexity string (for general K >= 5): "2^(num_paths_required * num_vertices)" (brute force over J·|V| binary variables)
• Special cases:
  • K <= 4: polynomial time
  • No length constraint (K = |V|): polynomial time by standard network flow (Menger's theorem)
  • Edge-disjoint version: NP-complete for K >= 5, polynomial for K <= 3, open for K = 4

declare_variants! guidance:

crate::declare_variants! {
    LengthBoundedDisjointPaths<SimpleGraph> => "2^(num_paths_required * num_vertices)",
}

• References:
  • A. Itai, Y. Perl, Y. Shiloach (1982). "The complexity of finding maximum disjoint paths with length constraints." Networks, 12(3):277-286.

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, none involving more than K edges?
Reference: [Itai, Perl, and Shiloach, 1977]. Transformation from 3SAT.
Comment: Remains NP-complete for all fixed K >= 5. Solvable in polynomial time for K <= 4. Problem where paths need only be edge-disjoint is NP-complete for all fixed K >= 5, polynomially solvable for K <= 3, and open for K = 4. The same results hold if G is a directed graph and the paths must be directed paths. The problem of finding the maximum number of disjoint paths from s to t, under no length constraint, is solvable in polynomial time by standard network flow techniques in both the vertex-disjoint and edge-disjoint cases.

How to solve

• It can be solved by (existing) bruteforce. Enumerate all sets of J vertex-disjoint s-t paths of length <= K.
• It can be solved by reducing to integer programming. Multi-commodity flow formulation with binary edge variables per path, flow conservation, vertex-disjointness, and path-length constraints.
• Other: For K <= 4, polynomial-time algorithms exist. For unbounded K, standard maximum flow / Menger's theorem gives the answer in polynomial time.

Example Instance

Instance 1 (YES — disjoint paths exist):
Graph G with 8 vertices {0, 1, 2, 3, 4, 5, 6, 7} and 12 edges:

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

Three vertex-disjoint s-t paths of length <= 3:

• P_1: 0 -> 1 -> 4 -> 7 (length 3)
• P_2: 0 -> 2 -> 5 -> 7 (length 3)
• P_3: 0 -> 3 -> 6 -> 7 (length 3)
• All internal vertices {1,4}, {2,5}, {3,6} are pairwise disjoint
• All paths have exactly 3 edges (<= K = 3)
• Answer: YES

Instance 2 (YES — disjoint paths of different lengths):
Graph G with 7 vertices {0, 1, 2, 3, 4, 5, 6} and 8 edges:

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

Two vertex-disjoint s-t paths of length <= 3:

• P_1: 0 → 1 → 6 (length 2)
• P_2: 0 → 2 → 3 → 6 (length 3)
• Internal vertex sets: {1}, {2,3} — pairwise disjoint ✓
• P_1 has 2 edges (<= 3 ✓), P_2 has 3 edges (<= 3 ✓)
• Answer: YES (paths have different lengths: 2 and 3)

Instance 3 (NO — not enough short disjoint paths):
Same graph as above but with J = 3, K = 2:

• Any path of length 2 from 0 to 7 must go 0 -> v -> 7 where v is a common neighbor of 0 and 7.
• Neighbors of 0: {1, 2, 3}. Neighbors of 7: {4, 5, 6}.
• No vertex is a common neighbor of both 0 and 7, so no path of length 2 exists.
• Answer: NO (cannot find even J = 1 path of length <= 2)

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem not in the reduction graph
Non-trivial	✅ Pass	Distinct feasibility constraints from all existing problems
Correctness	⚠️ Warn	Reference verified; complexity string is loose; minor date discrepancy in body
Well-written	⚠️ Warn	Naming convention issue; variable encoding needs refinement

Overall: 2 passed, 0 failed, 2 warnings

---

Usefulness

The problem MaximumLengthBoundedDisjointPaths does not exist in the current codebase. It is a classical NP-complete problem from Garey & Johnson (A2 ND41). The issue identifies a planned inbound reduction from 3SAT (R62), which would connect it to the existing reduction graph. The motivation (telecommunications routing, VLSI design) is concrete and well-articulated.

Result: Pass.

Non-trivial

This problem has a genuinely distinct feasibility constraint from all 24 existing problems: it requires finding J vertex-disjoint s-t paths, each bounded by K edges. No existing problem in the codebase encodes this combination of vertex-disjointness and length-bounded path constraints. It is not a variant of any existing graph problem.

Result: Pass.

Correctness

Reference verification:

• The paper "The complexity of finding maximum disjoint paths with length constraints" by A. Itai, Y. Perl, and Y. Shiloach was published in Networks, vol. 12, no. 3, pp. 277–286, 1982 (Wiley). This is confirmed to exist and matches the issue's citation.
• The Garey & Johnson reference "[Itai, Perl, and Shiloach, 1977]" (in the Extra Remark section) refers to an earlier technical report or conference version. The journal version appeared in 1982. Both dates are legitimate — the issue body correctly uses 1982 for the journal citation, while the "Full book text" section quotes Garey & Johnson verbatim (which used the 1977 date). This is consistent and not an error.
• The key claims are correct: NP-complete for fixed K >= 5, polynomial for K <= 4, transformation from 3SAT.

Complexity string:

• The issue proposes "2^num_vertices" as the complexity string. This is technically valid (brute force) but very loose — it does not reflect the best known exact algorithm. For a satisfaction problem where we enumerate combinations of J paths each of length at most K, the actual search space is smaller than 2^n. However, since no better exact algorithm appears to be known in the literature for the general case, this is acceptable as an upper bound.
• Warning: The complexity string should ideally reflect a tighter bound. For fixed J and K, the search space is polynomial (O(n^{JK})), but for general J and K the brute-force bound is reasonable.

Result: Warn — reference is correct, but the complexity string is loose. Consider adding a comment about the parameterized complexity being polynomial for fixed J and K.

Well-written

4a: Information Completeness — All required sections are present and substantive: Motivation, Name, Reference, Definition, Variables, Schema, Complexity, How to solve, Example Instance. No placeholder sections.

4b: Definition Completeness — The mathematical definition is taken directly from Garey & Johnson and is precise: input (graph, s, t, J, K), decision question (J vertex-disjoint s-t paths of length <= K). Clear and implementable.

4c: Symbol and Notation Consistency:

• Symbols are generally consistent (G, V, E, s, t, J, K used throughout).
• The Schema field names (num_paths_required, max_length, source, sink) are well-chosen and match the getter methods listed.

4d: Naming Convention Issue:

• The name MaximumLengthBoundedDisjointPaths uses the Maximum prefix, but the issue defines this as a satisfaction problem (Metric = bool). Per the project's naming conventions, the Maximum/Minimum prefix is reserved for optimization problems. Since this is a decision problem ("does G contain J or more paths..."), the name should not start with Maximum. Consider names like LengthBoundedDisjointPaths or DisjointPathsLengthBounded.

4e: Variable Encoding:

• The variable section says "J * |V| binary variables" but this encoding is somewhat informal. For implementation, it is important to clarify how the dims() and evaluate() functions would work. If each variable is binary (vertex v on path j), then dims() should return vec![2; J * |V|]. The issue acknowledges this with "or equivalently encode as a selection of J vertex-disjoint s-t paths" but does not commit to a specific encoding for implementation.

4f: Example Quality:

• Both examples are well-constructed. Instance 1 (YES) has 8 vertices and clearly shows 3 vertex-disjoint paths. Instance 2 (NO) demonstrates impossibility with tighter constraints. Both are brute-force verifiable.

Result: Warn — The naming convention conflict (Maximum prefix on a satisfaction problem) should be resolved before implementation. Variable encoding should be made more precise.

Recommendations

• Rename to LengthBoundedDisjointPaths or similar to avoid the Maximum prefix on a satisfaction problem.
• Commit to a specific variable encoding for dims() and evaluate() (e.g., J * |V| binary variables with one-hot path encoding per path slot).
• Consider whether this should be an optimization problem (maximize J) rather than a decision problem (is J achievable). The optimization version would justify the Maximum prefix and align better with other problems in the codebase.
• The complexity string "2^num_vertices" could be tightened if better algorithms are found.

[isPANN]

Changelog (fix-issue-batch)

• Fixed complexity string: "2^num_vertices" → "2^(num_paths_required * num_vertices)" — the search space has J·|V| binary variables, not just |V|
• No other changes needed (size fields already present, variable encoding sufficient)