[Model] LongestCircuit

[isPANN]

---

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

Motivation

LONGEST CIRCUIT (P104) from Garey & Johnson, A2 ND28. A classical NP-complete problem useful for reductions. Asks whether a graph contains a simple circuit whose total edge length meets or exceeds a given bound K. NP-complete even with unit edge lengths (where it reduces to finding a longest simple cycle).

Associated reduction rules:

• As source: None found in the current rule set.
• As target: R49: HAMILTONIAN CIRCUIT -> LONGEST CIRCUIT

Definition

Name: LongestCircuit

Canonical name: LONGEST CIRCUIT (also: Longest Cycle, Maximum Weight Simple Cycle)
Reference: Garey & Johnson, Computers and Intractability, A2 ND28

Mathematical definition:

INSTANCE: Graph G = (V,E), length l(e) ∈ Z^+ for each e ∈ E, positive integer K.
QUESTION: Is there a simple circuit in G of length K or more, i.e., whose edge lengths sum to at least K?

Variables

• Count: |E| binary variables (one per edge), indicating whether the edge is included in the circuit.
• Per-variable domain: {0, 1} -- edge is excluded or included in the circuit.
• Meaning: The variable assignment encodes a subset of edges. A satisfying assignment is a subset S of E such that the subgraph induced by S forms a simple circuit (connected 2-regular subgraph) and the sum of l(e) for e in S is at least K.

Dims

[2; num_edges] — one binary variable per edge indicating inclusion in the circuit.

Schema (data type)

Type name: LongestCircuit
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)
bound	W	The length bound K

Notes:

• This is a satisfaction (decision) problem: Metric = bool, implementing SatisfactionProblem.
• For the optimization variant, one would maximize the circuit length (removing the bound K), making it an OptimizationProblem with Direction::Maximize.
• The unit-weight special case (l(e) = 1 for all e) is equivalent to finding the longest simple cycle by number of edges.

Size fields

Getter	Meaning
num_vertices	Number of vertices |V|
num_edges	Number of edges |E|
bound	The length bound K

Complexity

• Best known exact algorithm: O(n^2 · 2^n) deterministic dynamic programming via Held-Karp adaptation — enumerate subsets, tracking cycle structure. (For the special case of Hamiltonian Cycle detection, Björklund (2014) achieves O*(1.657^n) randomized time.)
• NP-completeness: NP-complete by transformation from HAMILTONIAN CIRCUIT (Garey & Johnson, ND28). Remains NP-complete with unit edge lengths.
• Approximation: No constant-factor approximation is known for the general case.
• Special cases: For claw-free graphs, O*(1.6818^n) time with exponential space, or O*(1.8878^n) with polynomial space (Broersma, Fomin, van 't Hof, and Paulusma, 2013).
• References:
  • A. Björklund (2014). "Determinant Sums for Undirected Hamiltonicity." SIAM Journal on Computing, 43(1):280-299.
  • H.J. Broersma, F.V. Fomin, P. van 't Hof, D. Paulusma (2013). "Exact Algorithms for Finding Longest Cycles in Claw-Free Graphs." Algorithmica, 65(1):129-145.

Extra Remark

Full book text:

INSTANCE: Graph G = (V,E), length l(e) ∈ Z^+ for each e ∈ E, positive integer K.
QUESTION: Is there a simple circuit in G of length K or more, i.e., whose edge lengths sum to at least K?
Reference: Transformation from HAMILTONIAN CIRCUIT.
Comment: Remains NP-complete if l(e) = 1 for all e ∈ E, as does the corresponding problem for directed circuits in directed graphs. The directed problem with all l(e) = 1 can be solved in polynomial time if G is a "tournament" [Morrow and Goodman, 1976]. The analogous directed and undirected problems, which ask for a simple circuit of length K or less, can be solved in polynomial time (e.g., see [Itai and Rodeh, 1977b]), but are NP-complete if negative lengths are allowed.

How to solve

• It can be solved by (existing) bruteforce -- enumerate all subsets of edges and check if they form a simple circuit with total length >= K.
• It can be solved by reducing to integer programming.
• Other: Held-Karp-style DP in O(n^2 * 2^n).

Example Instance

Instance 1 (YES -- circuit of length >= K exists):
Graph G with 6 vertices {0, 1, 2, 3, 4, 5} and 10 edges:

• Edges with lengths: {0,1}:3, {1,2}:2, {2,3}:4, {3,4}:1, {4,5}:5, {5,0}:2, {0,3}:3, {1,4}:2, {2,5}:1, {3,5}:2
• K = 17
• Simple circuit: 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 0
  • Length: 3 + 2 + 4 + 1 + 5 + 2 = 17 >= K = 17
• Answer: YES

Instance 2 (NO -- no circuit of length >= K):
Same graph, K = 20.

• The Hamiltonian circuit above has length 17.
• Alternative circuit: 0 -> 3 -> 2 -> 5 -> 4 -> 1 -> 0: length = 3 + 4 + 1 + 5 + 2 + 3 = 18.
• No simple circuit can have length >= 20 (the maximum over all Hamiltonian circuits is 18).
• Answer: NO

Expected Outcome

• Instance 1 (K = 17): YES — the Hamiltonian circuit 0→1→2→3→4→5→0 has total length 3+2+4+1+5+2 = 17 ≥ K. This is a valid simple circuit (visits each vertex exactly once) and meets the bound.
• Instance 2 (K = 20): NO — brute-force enumeration of all 24 simple circuits in the graph confirms the maximum circuit length is 18 (achieved by the Hamiltonian circuit 0→3→2→5→4→1→0 with length 3+4+1+5+2+3 = 18). Since 18 < 20, no circuit meets the bound.

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem not yet in reduction graph
Non-trivial	✅ Pass	Distinct feasibility constraints from existing problems
Correctness	❌ Fail	Wrong citation for claw-free graph result; O*(1.657^n) claim for longest cycle conflates Hamiltonian Cycle detection
Well-written	⚠️ Warn	Variable encoding uses edges (exponential in

Overall: 2 passed, 1 failed, 1 warning

---

Usefulness

Pass. LongestCircuit does not exist in the current reduction graph (24 problem types). The problem is a classical NP-complete problem from Garey & Johnson (ND28) and enables a natural reduction from Hamiltonian Circuit. It fills a gap in the graph problems category.

Non-trivial

Pass. LongestCircuit has a genuinely different feasibility constraint from all existing problems. The closest existing problem is TravelingSalesman, which requires visiting all vertices (Hamiltonian cycle) and minimizes total weight. LongestCircuit asks for any simple circuit meeting a length bound — a distinct combinatorial structure. It is not a variant of any existing model.

Correctness

Fail. Two issues with the cited references:

1. Wrong paper for claw-free result. The issue cites: "van 't Hof, Paulusma, Woeginger (2011). 'Partitioning graphs into connected parts.' Algorithmica." This is incorrect on multiple counts:

   • The actual paper "Partitioning graphs into connected parts" by van 't Hof, Paulusma, and Woeginger was published in Theoretical Computer Science (vol. 410, pp. 4834–4843, 2009), not Algorithmica 2011.
   • That paper is about the 2-Disjoint Connected Subgraphs problem and longest path contractibility — it does not contain results about longest cycles.
   • The correct paper for the O*(1.6818^n) and O*(1.8878^n) longest cycle results on claw-free graphs is: Broersma, Fomin, van 't Hof, and Paulusma (2013). "Exact algorithms for finding longest cycles in claw-free graphs." Algorithmica, 65(1):129–145. Note different author list (Woeginger is not an author; Broersma and Fomin are).

2. O*(1.657^n) claim is misleading for Longest Cycle. Björklund (2014) "Determinant Sums for Undirected Hamiltonicity" (SIAM J. Comput. 43(1):280–299) is a real paper and does achieve O*(1.657^n) — but for Hamiltonian Cycle detection, not for finding the longest cycle. Finding the longest cycle in a general graph is a harder problem: one cannot simply run a single Hamiltonian Cycle check. The issue states this complexity is achieved "via reduction to Hamiltonian Cycle detection," but this conflation is not justified without explanation. The naive approach of binary-searching on cycle length and checking Hamiltonicity of subgraphs does not directly yield O*(1.657^n) for longest cycle.

3. Held-Karp bound is correct. The O(n^2 · 2^n) DP bound for the classic algorithm is standard and well-established.

4. NP-completeness claim is correct. Transformation from Hamiltonian Circuit per Garey & Johnson ND28 is accurate.

Well-written

Warn. The issue is generally well-structured and covers all required template sections. Some concerns:

1. Variable encoding is suboptimal. The issue proposes |E| binary edge variables. This gives a search space of 2^|E|, which for dense graphs is much larger than 2^|V|. A more natural encoding for brute-force would use |V| variables indicating circuit membership (or a permutation-based encoding). The edge-based encoding also requires complex feasibility checks (connected 2-regular subgraph). Consider whether a vertex-based encoding would be more aligned with the Held-Karp DP approach.

2. Schema field naming. The field lengths stores edge weights — this is fine but should be noted that it differs from TravelingSalesman's distances convention. The field name should match the getter method that overhead expressions will reference (e.g., num_edges(), bound()).

3. Example is adequate. Both YES and NO instances are provided with fully worked solutions. The graph has 6 vertices and 10 edges, which is non-trivial enough. The arithmetic checks out: circuit 0→1→2→3→4→5→0 has length 17, and the alternative 0→3→2→5→4→1→0 has length 18.

4. Missing optimization variant discussion. The Notes mention an optimization variant (maximize circuit length) but the issue only proposes the decision version. This is fine per Garey & Johnson's formulation, but the project may prefer the optimization formulation (Metric = SolutionSize<W>, Direction::Maximize) since most graph problems in the codebase are optimization problems. This should be a deliberate design choice.

Recommendations

• Fix the van 't Hof et al. citation to: Broersma, Fomin, van 't Hof, Paulusma (2013), Algorithmica 65(1):129–145.
• Clarify or remove the O*(1.657^n) claim for longest cycle — either explain the reduction precisely or state the Held-Karp O(n^2 · 2^n) as the best known general-graph exact algorithm.
• Consider whether the optimization formulation (maximize cycle length, no bound K) would be more useful for the reduction graph, as it would allow direct comparison with TravelingSalesman.
• Consider a vertex-based variable encoding for more efficient brute-force solving.

[isPANN]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem; HamiltonianCircuit (implemented) → LongestCircuit reduction planned
Non-trivial	✅ Pass	Distinct feasibility constraints from TravelingSalesman and HamiltonianCircuit
Correctness	❌ Fail	Wrong citation for claw-free graph result; O*(1.657^n) conflates HC detection with Longest Cycle
Well-written	❌ Fail	Missing required Dims and Size fields sections

Overall: 2 passed, 2 failed, 0 warnings

---

Usefulness

Pass. LongestCircuit does not exist in the codebase (confirmed via pred show). The issue mentions reduction R49: HamiltonianCircuit → LongestCircuit, and HamiltonianCircuit is already implemented (HamiltonianCircuit/SimpleGraph with complexity 1.657^num_vertices). This provides a concrete connection to the existing reduction graph. Motivation is substantive — classical NP-complete problem (G&J ND28) with pickup-and-delivery routing applications.

Non-trivial

Pass. LongestCircuit is genuinely distinct from all existing problems:

• vs TravelingSalesman: TSP requires visiting ALL vertices (Hamiltonian cycle) and minimizes total weight. LongestCircuit asks for ANY simple circuit with total edge length ≥ K — different feasibility constraint and opposite optimization direction.
• vs HamiltonianCircuit: HC asks whether a Hamiltonian cycle exists (all vertices visited exactly once). LongestCircuit allows circuits of any size and adds edge lengths with a bound constraint.
• Cannot be handled as a variant of an existing model — it requires a bound parameter K and edge lengths, which neither HC nor TSP's schema supports in the right combination.

Correctness

Fail. Two issues with the cited references:

1. Wrong paper for claw-free graph result. The issue cites: "P. van 't Hof, D. Paulusma, G.J. Woeginger (2011). 'Partitioning graphs into connected parts.' Algorithmica." This is wrong on multiple counts:

   • The paper "Partitioning graphs into connected parts" by van 't Hof, Paulusma, and Woeginger was published in Theoretical Computer Science (2009), not Algorithmica 2011.
   • That paper is about the 2-Disjoint Connected Subgraphs problem — it does not contain results about longest cycles.
   • The correct paper for the O*(1.6818^n) and O*(1.8878^n) longest cycle results in claw-free graphs is: Broersma, Fomin, van 't Hof, and Paulusma (2013). "Exact Algorithms for Finding Longest Cycles in Claw-Free Graphs." Algorithmica, 65(1):129–145. Note: different author list (Woeginger is not an author; Broersma and Fomin are), different year (2013), different title.

2. O*(1.657^n) claim is imprecise. Björklund (2014) "Determinant Sums for Undirected Hamiltonicity" (SIAM J. Comput. 43(1):280–299) does achieve O*(1.657^n) — but specifically for Hamiltonian Cycle detection, not for finding the longest cycle. The extension to Longest Cycle is possible via binary search on cycle length (check Hamiltonicity of subgraphs of increasing size), but this is not straightforward and not what the paper proves. The issue should either explain the reduction precisely or state the Held-Karp O(n^2 · 2^n) as the primary exact algorithm.

3. NP-completeness claim is correct. Transformation from Hamiltonian Circuit per Garey & Johnson ND28 is accurate.

4. Examples verified correct. Brute-force enumeration of all 24 simple circuits in Instance 1 confirms: maximum circuit length is 18 (two Hamiltonian circuits achieve this), the circuit 0→1→2→3→4→5→0 has length 17 (≥ K=17 ✓), and no circuit has length ≥ 20. There are 22 suboptimal feasible solutions for K=17.

Well-written

Fail. Two required template sections are missing:

1. Missing Dims section. The Variables section mentions "|E| binary variables" with domain {0, 1}, but there is no explicit Dims section stating the config space (e.g., [2; num_edges] for binary edge variables). This is required for implementing dims().

2. Missing Size fields section. No section listing getter names and their meanings (e.g., num_vertices → |V|, num_edges → |E|, bound → K). This is required for overhead expression validation in reduction rules.

3. Variable encoding is valid but suboptimal. The |E| binary edge variables give a search space of 2^|E|, which for dense graphs is much larger than 2^|V|. A vertex-based or permutation encoding aligned with Held-Karp DP would be more natural. This is a design choice, not a failure.

4. Expected Outcome is inline. The examples have YES/NO answers with worked solutions inline — acceptable but could be structured more clearly as a separate subsection.

5. Notation is consistent. Symbols (V, E, l(e), K) are defined and used consistently across sections.

Recommendations

• Fix the van 't Hof et al. citation to: Broersma, Fomin, van 't Hof, Paulusma (2013), "Exact Algorithms for Finding Longest Cycles in Claw-Free Graphs," Algorithmica 65(1):129–145.
• Clarify or remove the O*(1.657^n) claim — either explain the reduction from Longest Cycle to Hamiltonian Cycle detection precisely, or state O(n^2 · 2^n) as the primary exact algorithm.
• Add a Dims section: e.g., [2; num_edges] for binary edge inclusion.
• Add a Size fields section listing getter names: num_vertices, num_edges, bound.
• Consider the Frederickson (1979) JACM 26(3):538–554 reference for the NP-completeness proof of the directed variant — the issue's Extra Remark mentions this but the Complexity section does not cite it precisely.

[isPANN]

Fix-issue changelog

• Complexity section: Rewrote with O(n²·2^n) Held-Karp DP as the primary exact algorithm; Björklund's O*(1.657^n) noted as applicable to Hamiltonian Cycle detection only
• Citation fix: Replaced incorrect "van 't Hof, Paulusma, Woeginger (2011), Partitioning graphs into connected parts, Algorithmica" with correct "Broersma, Fomin, van 't Hof, Paulusma (2013), Exact Algorithms for Finding Longest Cycles in Claw-Free Graphs, Algorithmica 65(1):129–145"
• Added Dims section: [2; num_edges] — one binary variable per edge
• Added Size fields section: num_vertices (|V|), num_edges (|E|), bound (K)
• Added Expected Outcome section: Explicit verification for both YES and NO instances
• How to solve: Removed misleading Björklund reference from "Other" line

Applied by /fix-issue.