[Model] DisjointConnectingPaths

[isPANN]

---

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

Motivation

DISJOINT CONNECTING PATHS (P116) from Garey & Johnson, A2 ND40. A classical NP-complete problem useful for reductions. It models the fundamental routing/interconnection problem: given a set of terminal pairs in a network, can all pairs be simultaneously connected by vertex-disjoint paths? This has applications in VLSI design, network routing, and wire layout.

Associated reduction rules:

• As source: None found in current rule set.
• As target: R61 (3SAT to DISJOINT CONNECTING PATHS)

Definition

Name: DisjointConnectingPaths
Canonical name: Disjoint Connecting Paths (also: Vertex-Disjoint Paths Problem, Node-Disjoint Paths, Interconnection Problem)
Reference: Garey & Johnson, Computers and Intractability, A2 ND40

Mathematical definition:

INSTANCE: Graph G = (V,E), collection of disjoint vertex pairs (s_1,t_1),(s_2,t_2),...,(s_k,t_k).
QUESTION: Does G contain k mutually vertex-disjoint paths, one connecting s_i and t_i for each i, 1 <= i <= k?

Variables

Let k = |terminal_pairs| denote the number of terminal pairs.

• Count: |E| binary variables (one per edge).
• Per-variable domain: {0, 1} — whether edge e is included in any of the k paths.
• Meaning: A valid configuration selects edges that form exactly k vertex-disjoint paths, one connecting s_i to t_i for each i, 1 ≤ i ≤ k. The metric is bool: True if such paths exist, False otherwise.

Schema (data type)

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

Field	Type	Description
graph	SimpleGraph	The undirected graph G = (V, E)
terminal_pairs	Vec<(usize, usize)>	The k disjoint terminal pairs (s_i, t_i)

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_pairs() (= k).
• The terminal vertices must be pairwise disjoint (no vertex appears in more than one pair).

Complexity

• Decision complexity: NP-complete (Knuth 1974, Karp 1975, Lynch 1974; transformation from 3SAT). Remains NP-complete for planar graphs (Lynch 1975).
• Fixed-parameter tractability: For fixed k (number of terminal pairs), the problem is solvable in polynomial time:
  • O(n^3) by Robertson and Seymour's graph minor algorithm (1995), as part of their Graph Minors series.
  • O(n^2) by Kawarabayashi, Kobayashi, and Reed (2012), improving the cubic bound.
  • However, the constant factor is enormous (tower of exponentials in k), making these algorithms impractical.
• Best known exact algorithm (general k): Brute force enumeration of all possible edge subsets. No faster exact algorithm is known for the general case.
• Complexity string (for general k): "2^num_edges" (brute force over all possible edge subsets; no faster exact algorithm is known for general k)
• References:
  • N. Robertson and P.D. Seymour (1995). "Graph Minors. XIII. The Disjoint Paths Problem." Journal of Combinatorial Theory, Series B, 63(1):65-110. Polynomial algorithm for fixed k.
  • K. Kawarabayashi, Y. Kobayashi, B. Reed (2012). "The disjoint paths problem in quadratic time." Journal of Combinatorial Theory, Series B, 102(2):424-435.

Extra Remark

Full book text:

INSTANCE: Graph G = (V,E), collection of disjoint vertex pairs (s_1,t_1),(s_2,t_2),...,(s_k,t_k).
QUESTION: Does G contain k mutually vertex-disjoint paths, one connecting s_i and t_i for each i, 1 <= i <= k?
Reference: [Knuth, 1974c], [Karp, 1975a], [Lynch, 1974]. Transformation from 3SAT.
Comment: Remains NP-complete for planar graphs [Lynch, 1974], [Lynch, 1975]. Complexity is open for any fixed k >= 2, but can be solved in polynomial time if k = 2 and G is planar or chordal [Perl and Shiloach, 1978]. (A polynomial time algorithm for the general 2 path problem has been announced in [Shiloach, 1978]). The directed version of this problem is also NP-complete in general and solvable in polynomial time when k = 2 and G is planar or acyclic [Perl and Shiloach, 1978].

How to solve

• It can be solved by (existing) bruteforce. Enumerate all possible assignments of paths for each terminal pair and check vertex-disjointness.
• It can be solved by reducing to integer programming. Introduce binary variables for edge usage per path, add flow conservation constraints, and vertex-disjointness constraints.
• Other: For fixed k, Robertson-Seymour O(n^3) or Kawarabayashi-Kobayashi-Reed O(n^2). For k = 2, polynomial algorithms exist (Shiloach 1978).

Example Instance

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

0 — 1 — 3
|   |   |
2 — 4 — 5

• Edges: {0,1}, {1,3}, {0,2}, {1,4}, {2,4}, {3,5}, {4,5}
• Terminal pairs: (0, 3), (2, 5)

Vertex-disjoint paths:

• P1: 0 → 1 → 3 (connecting 0 to 3, using vertices {0, 1, 3})
• P2: 2 → 4 → 5 (connecting 2 to 5, using vertices {2, 4, 5})
• The paths are vertex-disjoint: {0, 1, 3} ∩ {2, 4, 5} = ∅
• Answer: YES

Instance 2 (NO — no disjoint paths):
Graph G with 6 vertices {0, 1, 2, 3, 4, 5} and 5 edges:

• Edges: {0,2}, {1,2}, {2,3}, {3,4}, {3,5}
• Terminal pairs: (0, 4), (1, 5)
• Vertex 2 and vertex 3 are cut vertices; any path from 0 to 4 must pass through 2 and 3, and any path from 1 to 5 must also pass through 2 and 3. Since both paths must share vertices 2 and 3, no vertex-disjoint solution exists.
• Answer: NO

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem not in the reduction graph; concrete routing applications
Non-trivial	✅ Pass	Distinct satisfaction problem with vertex-disjoint path constraints
Correctness	⚠️ Warn	References verified but complexity string is imprecise; see details
Well-written	❌ Fail	Example Instance 1 is broken (author failed to find valid paths); variable encoding is vague

Overall: 2 passed, 1 warning, 1 failed

---

Usefulness

Pass. DisjointConnectingPaths does not exist in the codebase (confirmed via pred show and pred list). The problem is a classical NP-complete problem (Garey & Johnson A2/ND40) with applications in VLSI design and network routing. The issue identifies a planned reduction from 3SAT, which would connect this problem to the existing reduction graph. The motivation is concrete and well-justified.

Non-trivial

Pass. This is a satisfaction problem with genuinely different feasibility constraints from all 24 existing problems. No existing problem models the "find k vertex-disjoint paths connecting given terminal pairs" constraint. It is not a variant of any existing graph problem in the codebase.

Correctness

Warn. The core references check out but the complexity string needs attention.

References verified:

• Robertson & Seymour (1995), "Graph Minors XIII. The Disjoint Paths Problem," JCTB 63(1):65-110 — Confirmed. O(n^3) algorithm for fixed k. The paper exists and the claim is accurate.
• Kawarabayashi, Kobayashi & Reed (2012), "The disjoint paths problem in quadratic time," JCTB 102(2):424-435 — Confirmed. O(n^2) improvement over Robertson-Seymour for fixed k.
• Garey & Johnson ND40, NP-completeness via transformation from 3SAT — Confirmed. The problem is listed in the GJ appendix under Network Design. NP-completeness attributions to Knuth (1974), Karp (1975), and Lynch (1975) are consistent with the literature. Lynch (1975) showed it remains NP-complete for planar graphs.

Complexity string issue: The proposed string "2^num_vertices" is a very loose upper bound (brute-force enumeration). For most problems in this codebase, the complexity string represents the best known exact algorithm, not a naive brute-force bound. Since the disjoint paths problem (for general k) does not appear to have a well-known exact algorithm with a tighter exponential base than 2^n, the bound may be acceptable, but it should be explicitly noted that no better exact algorithm is known. The issue's comment about Robertson-Seymour and Kawarabayashi-Kobayashi-Reed being polynomial for fixed k is correct, but those algorithms have impractical constant factors (tower of exponentials in k) and do not apply to the parameterized-by-k setting this problem models.

Note on GJ numbering: The issue header says "P116 from Garey & Johnson, A2 ND40." The "A2" refers to the appendix section and "ND40" is the problem number within Network Design — this is consistent formatting though slightly unusual (most references just say "ND40").

Well-written

Fail. Several issues need to be addressed:

1. Example Instance 1 is broken. The author visibly struggled to find vertex-disjoint paths and the example degenerates into a stream-of-consciousness with multiple failed attempts. The final "solution" requires adding an edge {2,5} that was not in the original graph — meaning the example instance was changed mid-explanation. This is not a valid worked example. A proper example must:

   • State the complete instance upfront (graph + terminal pairs)
   • Show the solution step-by-step without revisions
   • Be verified correct before submission

2. Variable encoding is vague and potentially inconsistent. The Variables section says "|E| binary variables (one per edge)" but then hedges with "or equivalently, for each terminal pair i, choose a path P_i." The actual variable encoding for a satisfaction problem needs to be precise — it determines dims() and evaluate(). For a decision problem asking "do k disjoint paths exist?", the natural encoding is one binary variable per vertex per path (indicating membership), not one per edge. The section should commit to a single encoding and define it precisely.

3. Symbol k used inconsistently. In the Definition, k is the number of terminal pairs. In the Complexity section, the "fixed k" discussion conflates the parameter with the variable. The Variables section should explicitly define all symbols.

4. Schema section is reasonable but the getter method num_pairs() is proposed without being standard in the codebase. This is acceptable as a new getter for a new problem type.

5. Example Instance 2 (NO instance) is good. The cut-vertex argument for the NO instance is clear and correct.

Recommendations

• Replace Example Instance 1 entirely with a clean, pre-verified instance. For example: a simple graph where two disjoint s-t paths clearly exist (e.g., a small grid or ladder graph).
• Commit to a single variable encoding. Suggestion: for each terminal pair i, binary variables over possible simple paths from s_i to t_i, or alternatively a vertex-assignment encoding where x_{v,i} = 1 means vertex v is on path i. The edge-based encoding mentioned first is also viable but needs constraints to form actual paths.
• Define all symbols explicitly before first use in the Variables section.

[GiggleLiu]

Fix-issue changelog

• Defined symbol k explicitly in Variables section (k = |terminal_pairs|)
• Committed to edge-based variable encoding (|E| binary variables), removed hedging about alternative encodings
• Updated complexity string from "2^num_vertices" to "2^num_edges" to match edge-based encoding; added note that no faster exact algorithm is known for general k
• Replaced broken Example Instance 1 (stream-of-consciousness with failed attempts) with clean, pre-verified 6-vertex grid instance (k=2, terminal pairs (0,3) and (2,5))
• Fixed Example Instance 2 edge count from "6 edges" to "5 edges"

Applied by /fix-issue.