[Model] LongestPath

[isPANN]

---

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

Motivation

LONGEST PATH (P105) from Garey & Johnson, A2 ND29. A classical NP-complete problem useful for reductions. Asks for a simple s-t path in a graph maximizing total edge length. NP-complete even with unit edge lengths, where it generalizes the Hamiltonian path problem. Solvable in polynomial time on DAGs.

Associated reduction rules:

• As source: None found in the current rule set.
• As target: R50: HAMILTONIAN PATH BETWEEN TWO VERTICES -> LONGEST PATH

Definition

Name: LongestPath

Canonical name: LONGEST PATH (also: Longest Simple Path, Maximum Weight Path)
Reference: Garey & Johnson, Computers and Intractability, A2 ND29

Mathematical definition:

INSTANCE: Graph G = (V,E), length l(e) ∈ Z^+ for each e ∈ E, specified vertices s,t ∈ V.
OBJECTIVE: Find a simple path in G from s to t that maximizes the total edge length, i.e., maximize the sum of l(e) over all edges e in the path.

Variables

• Count: |E| binary variables (one per edge), indicating whether the edge is included in the path.
• Per-variable domain: {0, 1} -- edge is excluded or included in the s-t path.
• Meaning: The variable assignment encodes a subset of edges. A valid assignment is a subset S of E such that the subgraph induced by S forms a simple path from s to t. The objective value is the sum of l(e) for e in S. An assignment that does not form a valid simple s-t path is Invalid.

Schema (data type)

Type name: LongestPath
Variants: graph type (G), weight type (W)

Field	Type	Description
graph	G	The undirected graph G = (V, E)
lengths	Vec<W>	Edge length l(e) for each edge (indexed by edge index)
source	usize	Index of source vertex s
target	usize	Index of target vertex t

Notes:

• This is an optimization problem: Metric = SolutionSize<W>, implementing OptimizationProblem with Direction::Maximize.
• A configuration that does not form a valid simple s-t path evaluates to SolutionSize::Invalid.
• A valid simple s-t path evaluates to SolutionSize::Valid(total_length) where total_length is the sum of edge lengths along the path.
• The decision variant (is there a path of length ≥ K?) can be recovered by comparing the optimal value to the bound.
• The unit-weight special case is equivalent to finding the longest simple path by hop count.
• Polynomial-time solvable on DAGs (directed acyclic graphs) via topological sort + DP.

Complexity

• Best known exact algorithm: O*(2^n) via inclusion-exclusion / algebraic methods. The color-coding technique of Alon, Yuster, and Zwick (1995) solves the k-path problem in O*(2^k) time (FPT in path length k). For general longest path, exhaustive search over all simple paths dominates.
• Classic algorithm: O(n! / (n-k)!) brute force over all simple paths of length k; or O(n * 2^n) dynamic programming over vertex subsets (similar to Held-Karp).
• NP-completeness: NP-complete by transformation from HAMILTONIAN PATH BETWEEN TWO VERTICES (Garey & Johnson, ND29). Remains NP-complete with unit edge lengths.
• Special cases: Polynomial-time on DAGs, trees, interval graphs, and some other restricted graph classes.
• References:
  • N. Alon, R. Yuster, U. Zwick (1995). "Color-coding." Journal of the ACM, 42(4):844-856.
  • R. Williams (2009). "Finding paths of length k in O*(2^k) time." Information Processing Letters, 109(6):315-318.

Extra Remark

Full book text:

INSTANCE: Graph G = (V,E), length l(e) ∈ Z^+ for each e ∈ E, positive integer K, specified vertices s,t ∈ V.
QUESTION: Is there a simple path in G from s to t of length K or more, i.e., whose edge lengths sum to at least K?
Reference: Transformation from HAMILTONIAN PATH BETWEEN TWO VERTICES.
Comment: Remains NP-complete if l(e) = 1 for all e ∈ E, as does the corresponding problem for directed paths in directed graphs. The general problem can be solved in polynomial time for acyclic digraphs, e.g., see [Lawler, 1976a]. The analogous directed and undirected "shortest path" problems can be solved for arbitrary graphs in polynomial time (e.g., see [Lawler, 1976a]), but are NP-complete if negative lengths are allowed.

How to solve

• It can be solved by (existing) bruteforce -- enumerate all simple s-t paths and return the one with maximum total length.
• It can be solved by reducing to integer programming.
• Other: Held-Karp-style DP in O(n * 2^n); color-coding in O*(2^k) for k-length paths.

Example Instance

Instance 1 (optimal path length = 20):
Graph G with 7 vertices {0, 1, 2, 3, 4, 5, 6} and 10 edges:

• Edges with lengths: {0,1}:3, {0,2}:2, {1,3}:4, {2,3}:1, {2,4}:5, {3,5}:2, {4,5}:3, {4,6}:2, {5,6}:4, {1,6}:1
• s = 0, t = 6
• Optimal path: 0 → 1 → 3 → 2 → 4 → 5 → 6
  • Length: 3 + 4 + 1 + 5 + 3 + 4 = 20
• Suboptimal path: 0 → 2 → 4 → 5 → 3 → 1 → 6
  • Length: 2 + 5 + 3 + 2 + 4 + 1 = 17
• Invalid configuration: edges {0,1}, {0,2}, {1,3} do not form a simple s-t path → Invalid

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem not yet in reduction graph; connects via Hamiltonian Path reduction
Non-trivial	✅ Pass	Distinct from TravelingSalesman and other existing graph problems
Correctness	❌ Fail	Example Instance 2 is incorrect — a path of length 20 exists
Well-written	⚠️ Warn	Minor notation issues; see details below

Overall: 2 passed, 1 failed, 1 warning

---

Usefulness

Pass. LongestPath does not exist in the current reduction graph (pred show LongestPath fails). The problem is a classical NP-complete problem (Garey & Johnson ND29) with a clear connection to Hamiltonian Path. The issue identifies a concrete associated reduction (Hamiltonian Path → Longest Path). The motivation correctly notes that it generalizes Hamiltonian path and is useful as a reduction target. Having this in the graph would enable new reduction chains.

Non-trivial

Pass. LongestPath has genuinely different feasibility constraints from all existing problems:

• Unlike TravelingSalesman, which requires a Hamiltonian cycle and minimizes total weight, LongestPath asks for a simple s-t path with total length at least K (a satisfaction/decision problem).
• Unlike MaximumIndependentSet, MaximumClique, etc., this is a path-finding problem with connectivity constraints.
• Not a trivial variant of any existing problem.

Correctness

Fail. The literature references are verified, but Example Instance 2 is mathematically incorrect.

References verified:

• ✅ Alon, Yuster, Zwick (1995). "Color-coding." Journal of the ACM, 42(4):844–856. Confirmed: O*(2^k) for k-path. DOI: 10.1145/210332.210337.
• ✅ Williams (2009). "Finding paths of length k in O*(2^k) time." Information Processing Letters, 109(6):315–318. Confirmed: arxiv 0807.3026.
• ✅ Garey & Johnson ND29 reference is consistent with the known classification.

Complexity claims verified:

• ✅ O(n · 2^n) DP over vertex subsets (Held-Karp style) is the standard best exact algorithm.
• ✅ Color-coding O*(2^k) for parameterized version is correct.
• ✅ NP-completeness via Hamiltonian Path is correct.

Example error:

• ❌ Instance 2 is wrong. The issue claims no simple path from s=0 to t=6 has length ≥ 20, asserting the best path is 0→2→4→5→3→1→6 with length 17. However, the path 0→1→3→2→4→5→6 uses edges {0,1}:3 + {1,3}:4 + {3,2}:1 + {2,4}:5 + {4,5}:3 + {5,6}:4 = 20, which is a valid simple path achieving exactly K=20. Therefore Instance 2 should be a YES instance, not NO.
• To fix: either increase K to 21 (making it a genuine NO instance since 20 is the true optimum), or choose a different graph.

Well-written

Warn. The issue is generally well-structured and follows the template, but has some items to address:

Positive:

• ✅ All required template sections are present and substantive.
• ✅ Mathematical definition is clear and matches Garey & Johnson.
• ✅ Variables section correctly identifies edge-based binary encoding.
• ✅ Schema is well-designed with appropriate fields.
• ✅ Complexity section is thorough with multiple references.
• ✅ Solver methods are identified (brute-force and Held-Karp DP).

Issues:

• ⚠️ The issue proposes this as a satisfaction problem (Metric = bool) with a bound K, but the project's existing problems of this nature (like Satisfiability, KSatisfiability) tend to be logic-based. Graph optimization problems in this project typically use OptimizationProblem with Direction::Maximize (e.g., MaximumIndependentSet). Consider whether the optimization variant (maximize path length, no bound K) would be more useful for reductions — the decision version can always be recovered from the optimization version. If kept as satisfaction, the naming LongestPath is slightly misleading since it includes a bound.
• ⚠️ The "How to solve" section checks brute-force and "Other" but leaves ILP unchecked without explanation. LongestPath can be formulated as an ILP (flow-based formulation), which would be worth noting.
• ⚠️ The bound field in the schema uses type W (the weight type), but W is typically reserved for edge weights. Since K is a threshold on the sum of weights, using W::Sum or a dedicated type might be more appropriate to match the WeightElement / NumericSize pattern.

Recommendations

• Fix Example Instance 2: change K to 21 so that it is a genuine NO instance (the true longest s→t path has length 20).
• Consider proposing this as an optimization problem (Direction::Maximize, maximize path length) rather than a satisfaction problem, since optimization versions are generally more useful for reduction chains.
• Add ILP as a solver method — longest path has a natural flow-based ILP formulation.

[GiggleLiu]

Fix-issue changelog

• Switched from satisfaction (Metric = bool) to optimization (Direction::Maximize, Metric = SolutionSize<W>)
• Removed bound field from Schema (no longer needed for optimization framing)
• Updated Definition from decision question to optimization objective
• Updated Variables to describe Valid/Invalid optimization semantics
• Fixed incorrect Example Instance 2 (K=20 was achievable — path 0→1→3→2→4→5→6 has length 20); replaced with single verified instance showing optimal (20), suboptimal (17), and invalid configurations
• Checked ILP solver box
• Updated bruteforce description for optimization

Applied by /fix-issue.