[Rule] HAMILTONIAN CIRCUIT to LONGEST CIRCUIT

[isPANN]

Source: HAMILTONIAN CIRCUIT
Target: LONGEST CIRCUIT
Motivation: Establishes NP-completeness of LONGEST CIRCUIT via polynomial-time reduction from HAMILTONIAN CIRCUIT. The reduction is trivial: assign unit weight to every edge and set the length bound K = |V|, so a simple circuit of length at least K exists if and only if a Hamiltonian circuit exists.

Reference: Garey & Johnson, Computers and Intractability, ND28, p.213

GJ Source Entry

[ND28] LONGEST CIRCUIT
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.

Reduction Algorithm

Summary:
Given a HAMILTONIAN CIRCUIT instance G = (V, E) with n = |V| vertices, construct a LONGEST CIRCUIT instance as follows:

1. Graph: Use the same graph G' = G = (V, E).

2. Edge lengths: For every edge e in E, set the length l(e) = 1 (unit weights).

3. Bound: Set K = n (the number of vertices).

4. Correctness (forward): If G has a Hamiltonian circuit C visiting all n vertices, then C is a simple circuit in G' with exactly n edges, each of length 1, so the total length is n = K. Thus the LONGEST CIRCUIT instance is a YES instance.

5. Correctness (reverse): If G' has a simple circuit of length >= K = n with unit-weight edges, then the circuit has at least n edges. Since the circuit is simple (no repeated vertices) and the graph has only n vertices, a simple circuit can have at most n edges. Therefore the circuit has exactly n edges and visits all n vertices -- it is a Hamiltonian circuit in G.

Key invariant: With unit weights, a simple circuit of length >= n exists if and only if the circuit visits all n vertices, i.e., it is Hamiltonian.

Time complexity of reduction: O(|E|) to assign unit weights.

Size Overhead

Symbols:

• n = num_vertices of source HamiltonianCircuit instance (|V|)
• m = num_edges of source HamiltonianCircuit instance (|E|)

Target metric (code name)	Polynomial (using symbols above)
num_vertices	num_vertices
num_edges	num_edges
bound	num_vertices

Derivation: The graph is unchanged. The bound K equals the number of vertices n. Each edge simply gets a unit length assigned.

Validation Method

• Closed-loop test: reduce a HamiltonianCircuit instance to LongestCircuit, solve target with BruteForce, extract solution, verify on source
• Test with known YES instance: the Petersen graph is Hamiltonian; the longest circuit instance with K = 10 should be satisfiable
• Test with known NO instance: the Petersen graph minus one vertex is not Hamiltonian; verify that no circuit of length >= 9 exists in that subgraph with the same construction
• Compare with known results from literature

Example

Source instance (HamiltonianCircuit):
Graph G with 6 vertices {0, 1, 2, 3, 4, 5} and 9 edges:

• Edges: {0,1}, {1,2}, {2,3}, {3,4}, {4,5}, {5,0}, {0,3}, {1,4}, {2,5}
• (Triangular prism / prism graph)
• Hamiltonian circuit exists: 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 0

Constructed target instance (LongestCircuit):

• Same graph G' = G with 6 vertices and 9 edges
• Edge lengths: l(e) = 1 for all 9 edges
• Bound K = 6

Solution mapping:

• LongestCircuit solution: simple circuit 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 0
• Circuit length: 6 edges x 1 = 6 >= K = 6
• This circuit visits all 6 vertices exactly once, forming a Hamiltonian circuit in G

Verification:

• Forward: HC 0->1->2->3->4->5->0 maps to circuit of length 6 = K
• Reverse: any simple circuit of length >= 6 with 6 vertices must visit all vertices -> Hamiltonian circuit

References

• [Morrow and Goodman, 1976]: [Morrow1976] C. Morrow and S. Goodman (1976). "An efficient algorithm for finding a longest cycle in a tournament". In: Proceedings of the 7th Southeastern Conference on Combinatorics, Graph Theory, and Computing, pp. 453-462. Utilitas Mathematica Publishing.
• [Itai and Rodeh, 1977b]: [Itai1977c] Alon Itai and Michael Rodeh (1977). "Some matching problems". In: Automata, Languages, and Programming. Springer.

[isPANN]

Issue Quality Check — Rule

Check	Result	Details
Usefulness	✅ Pass	No existing path HamiltonianCircuit → LongestCircuit
Non-trivial	⚠️ Warn	Legitimate G&J reduction but no structural transformation (graph copied as-is)
Correctness	⚠️ Warn	Main reference (G&J ND28) confirmed; one secondary reference unverifiable
Well-written	✅ Pass	All sections complete; example programmatically validated

Overall: 2 passed, 2 warnings, 0 failed

---

Usefulness

Pass. pred path HamiltonianCircuit LongestCircuit returns no existing path. This is a novel direct reduction. HamiltonianCircuit currently only reduces to TravelingSalesman.

Non-trivial

Warn — borderline. The reduction copies the graph unchanged, assigns unit edge weights, and sets bound K = |V|. There are no gadgets, auxiliary vertices, penalty terms, or structural transformation. The issue itself states "The reduction is trivial."

For comparison, the existing HC → TSP reduction constructs a complete graph with differential edge weights (1 for existing edges, 2 for non-edges) — genuinely more structural work.

That said, this reduction does not match any explicit Fail criterion: it adds new parameters (weights + bound) rather than just relabeling variables, and it connects two genuinely different problems. It is a standard "restriction" reduction from G&J that establishes NP-completeness of Longest Circuit.

Correctness

Primary reference: Garey & Johnson ND28

Confirmed. Cross-referenced with the University of Liverpool's Annotated List of NP-complete Problems, which lists ND28 as "Longest Circuit" with transformation from Hamiltonian Circuit. Multiple independent academic sources (UCSD, MIT, NTU course materials) confirm this standard reduction. Page 213 is plausible but unverifiable without the physical book.

[Morrow and Goodman, 1976]

Unverifiable. The 7th Southeastern Conference on Combinatorics, Graph Theory, and Computing (1976, LSU) and publisher Utilitas Mathematica are confirmed real. However, no indexed record of a paper by "Morrow and Goodman" with this title was found. A related paper by Dixon and Goodman (1976), "An algorithm for the longest cycle problem," published in Networks 6:139-149 exists — possible author confusion. This is a G&J citation reproduced verbatim; verification would require MathSciNet/zbMATH or the physical proceedings volume.

[Itai and Rodeh, 1977b]

Confirmed with caveat. The paper exists in ICALP 1977, LNCS vol. 52, Springer (indexed on SpringerLink). However, the paper's content ("Some matching problems") is about bipartite matching NP-completeness, not directly about circuits. Itai and Rodeh's circuit-related work ("Finding a minimum circuit in a graph") may be the more relevant paper for the GJ Comment context.

Reduction correctness

Verified. Unit weights + K=|V| correctly reduces HC to LC: a simple circuit of length ≥ n with unit weights must visit all n vertices, hence is Hamiltonian. Conversely, any Hamiltonian circuit has exactly n edges with total weight n = K.

Well-written

Information Completeness

All 8 required sections are present and substantive: Source, Target, Motivation, Reference, Reduction Algorithm, Size Overhead, Validation Method, Example.

Algorithm Completeness

The algorithm is a complete step-by-step procedure (5 numbered steps including correctness arguments). Implementable as stated.

Symbol and Notation Consistency

• n = |V| defined ✓
• G = (V, E) used consistently ✓
• K = n defined ✓
• Overhead table metrics (num_vertices, num_edges, bound) match target LongestCircuit getter methods ✓
• Expression variables (num_vertices, num_edges) match source HamiltonianCircuit getter methods ✓

Example Quality (Python-validated)

The triangular prism example (6 vertices, 9 edges) was programmatically verified:

• 30 simple circuits total: 18 at length 4, 12 at length 6
• 12 directed Hamiltonian circuits (6 unique undirected) — all satisfy K=6
• Round-trip verified: every length-6 target circuit maps to a valid source HC, and vice versa
• Non-trivial: good mix of satisfying (12) and non-satisfying (18) circuits distinguishes correctness
• Size overhead confirmed: identity mapping preserves num_vertices and num_edges exactly

Recommendations

• Consider whether the secondary references (Morrow & Goodman, Itai & Rodeh) are needed in the issue body — they are from the GJ Comment section and add context about related results, not about the reduction itself. If kept, verify Morrow & Goodman via MathSciNet.
• The GJ Source Entry's unweighted definition ("at least k nodes") and the issue's weighted formulation ("edge lengths sum to at least K") are equivalent when l(e)=1 for all edges. This equivalence is correctly noted in the algorithm but could be stated more explicitly.