Repository navigation
[Rule] HamiltonianPath to HamiltonianCircuit #1097
Description
Source
HamiltonianPath/SimpleGraph
Target
HamiltonianCircuit/SimpleGraph
Motivation
This is the standard path-to-cycle construction and supplies a missing reverse connection between two canonical Hamiltonian problems. There is currently no path from Hamiltonian Path to Hamiltonian Circuit.
Reference
Bowen Waggoner, “Standard 21: P and NP 2: NP-Completeness”, gives this mapping reduction explicitly: add a new vertex adjacent to every old vertex, extend a Hamiltonian path through it, and recover a Hamiltonian path by deleting it from a Hamiltonian cycle. The notes state the construction for directed graphs using both incident arc directions; for this repository's undirected SimpleGraph, those two directions become one undirected edge {x,v} and the same proof applies verbatim.
Garey and Johnson, Computers and Intractability, 1979, is retained as a reference for the Hamiltonian Path and Hamiltonian Circuit problem definitions and their classical complexity status; its catalog entries are not the source of the universal-vertex construction.
Reduction Algorithm
Let G=(V,E), n=|V|, and m=|E|.
- If
n<2, the source implementation accepts the unique empty/singleton ordering. Return a fixed triangle, and during extraction return the unique source ordering. - Otherwise add a new vertex
x. - Preserve every edge in
Eand add{x,v}for everyv in V. - Given a Hamiltonian cycle in the target, rotate it to start at
x, deletex, and return the remaining vertex order.
For n>=2, a Hamiltonian path v_0,...,v_{n-1} extends to cycle x,v_0,...,v_{n-1},x. Conversely deleting x from any target Hamiltonian cycle leaves a Hamiltonian path in G. The explicit small-instance branch covers the full behavior of the source model, whose empty and singleton instances are satisfiable while the target rejects circuits with fewer than three vertices.
The repository's SimpleGraph representation permits self-loops and parallel edges. The construction copies them unchanged. They do not affect correctness: no new edge joins two old vertices, so every consecutive pair remaining after x is deleted must already be adjacent in G; loops cannot join two distinct positions of a Hamiltonian ordering, and parallel copies do not change adjacency.
Size Overhead
The formulas are safe polynomial upper bounds including the fixed small-instance output.
| Target metric | Formula |
|---|---|
num_vertices |
num_vertices + 3 |
num_edges |
num_edges + num_vertices + 3 |
For n>=2, the exact sizes are n+1 vertices and m+n edges.
Validation Method
- Exhaust every simple graph through four vertices and compare source/target feasibility.
- Check both cycle orientations and rotation during extraction.
- Explicitly test
n=0,n=1, two isolated vertices, a single edge, disconnected graphs, stars, self-loops, and parallel edges.
Example
- Source instance:
V={0,1,2,3,4}, edges{01,12,23,34,02,13}. It has Hamiltonian path0-1-2-3-4, alongside many invalid and partial orderings. - Construction: add vertex
5and edges{05,15,25,35,45}. - Target instance: six vertices and eleven edges.
- Round trip: cycle
5-0-1-2-3-4-5maps to source path0-1-2-3-4. As a negative companion, the four-vertex star has no Hamiltonian path, and its augmented graph has no Hamiltonian cycle. Both were checked exhaustively.
BibTeX
@misc{Waggoner2025NPCompleteness,
author = {Waggoner, Bowen},
title = {Standard 21: P and NP 2: NP-Completeness},
year = {2025},
howpublished = {University of Colorado Boulder course notes},
url = {https://bowaggoner.com/courses/2025/csci3104/book/standards/21-pnp-complete.html},
note = {Accessed 2026-08-01}
}
@book{GareyJohnson1979,
author = {Garey, Michael R. and Johnson, David S.},
title = {Computers and Intractability: A Guide to the Theory of NP-Completeness},
publisher = {W. H. Freeman},
year = {1979}
}
Activity
isPANN commentedon Aug 1, 2026
Issue Quality Check — Rule
pred path HamiltonianPath HamiltonianCircuit --jsonreports no existing reduction path.SimpleGraphrepresentation permits.Overall: 3 passed, 1 failed, 1 warning
Usefulness
Both endpoints resolve as existing
SimpleGraphvariants. The current graph has noHamiltonianPath → HamiltonianCircuitpath, so this supplies a genuinely missing direction rather than a dominated shortcut. The motivation explains the missing reverse connection.Non-trivial
For
n >= 2, the rule constructs a new graph by adding a universal vertex andnincident edges. Extracting a source witness requires rotating the target cycle around the new vertex and deleting it. This is a genuine structural transformation, not relabeling, subtype coercion, or an identity map.Correctness
The cited book exists and is already present in
docs/paper/references.bib. I checked the scanned text directly:The mathematical construction itself is independently corroborated by Bowen Waggoner's NP-completeness notes, which explicitly gives the mapping reduction: add one vertex adjacent to every old vertex, extend a Hamiltonian path through it, and conversely delete it from a Hamiltonian cycle. The issue's own forward and reverse arguments are also correct.
I additionally ran a standalone exhaustive validator over every simple graph through four vertices; it confirmed source/target feasibility for this construction, including the explicit
n < 2branch.The failure is therefore a citation-support failure, not a discovered mathematical counterexample. Please replace or supplement the reference with a source that explicitly states this reduction (including the theorem/proof location), or accurately describe the construction as self-contained and cite G&J only for the two problem definitions.
Completeness
Literature scope. The independent construction above is stated for an arbitrary Hamiltonian Path instance and has no connectivity, degree, or endpoint precondition. Its proof covers all ordinary undirected graphs: a source path becomes
x,v_0,…,v_(n-1),x, and deletingxfrom any target cycle leaves only original edges between consecutive old vertices.Repository semantics.
pred show HamiltonianPath --jsonreports size fieldsnum_verticesandnum_edges, with source variantSimpleGraph. The source evaluator accepts the empty ordering forn=0and[0]forn=1; the target evaluator rejects every circuit with fewer than three vertices.SimpleGraph::newalso does not reject self-loops or parallel edges.Hand traces beyond the worked example:
n=0). The explicit branch returns a triangle. The triangle has a Hamiltonian circuit; extraction returns[], which the source evaluator accepts. Feasibility and witness extraction are preserved.n=2). The construction addsxand edges{x,0}and{x,1}. The target is a length-two path, not a 3-cycle, so it has no Hamiltonian circuit; the source has no Hamiltonian path. Feasibility is preserved.xis new, so loops and duplicate edges neither create an old-to-old adjacency that was absent nor affect the delete-xproof. The mapping remains well-defined.Existing rules from the same source were also inspected:
hamiltonianpath_isomorphicspanningtree.rsexplicitly handlesn=0viaSimpleGraph::path(0), whilehamiltonianpath_degreeconstrainedspanningtree.rsexplicitly returns[]and[0]for the two smallest witness cases. The proposed branch matches those source semantics.Because the algorithm works on the traced representation-level cases but the issue does not explicitly document allowed loops and parallel edges, this check is a warning rather than a failure.
Well-written
All required template sections are present.
nandmare defined before use; target metric names matchHamiltonianCircuit'snum_verticesandnum_edges; the formulas are valid upper bounds and the exactn >= 2sizes are separately stated. The five-vertex positive example contains chords, fully lists the constructed target, gives a round-trip witness, and includes a nontrivial negative companion.Recommendations
isPANN commentedon Aug 1, 2026
Rule Fix
Diagnosis:
Or -> Orcompatibility, and target validity. No undirected cross-gadget rerouting risk applies because deleting the sole new vertex leaves only original consecutive edges.Literature:
Changes:
Smoke test:
n=0,n=1, two isolated vertices, a single edge, a four-vertex star, and a graph containing a self-loop plus parallel edges.isPANN commentedon Aug 1, 2026
Issue Quality Re-check — Rule
pred path HamiltonianPath HamiltonianCircuit --jsonstill reports no existing path.n < 2semantics plus allowed self-loops and parallel edges; exhaustive and witness-level checks passed.Overall: 5 passed, 0 failed, 0 warnings
Previously: 3 passed, 1 failed, 1 warning. The citation-support failure and representation-edge-case warning are resolved.
Usefulness
pred showresolvesHamiltonianPath/SimpleGraphandHamiltonianCircuit/SimpleGraph. There is no current reduction path from the source to the target, so this is a novel connection rather than a dominated direct edge. The motivation states that graph-connectivity purpose.Non-trivial
For
n >= 2, the rule copies the source and adds a new universal vertex withnincident edges. A target witness is rotated around that new vertex and shortened to recover the source ordering. This changes graph structure and requires a genuine witness mapping.Correctness
Bowen Waggoner's “Standard 21: P and NP 2: NP-Completeness” explicitly states the Hamiltonian Path to Hamiltonian Cycle mapping: add a new vertex incident in both directions to every old vertex, extend a source path through it, and delete it from a target cycle for the converse. In an undirected graph the two opposite arcs are represented by the single edge
{x,v}, exactly as the edited issue explains.The independent proof in the body is complete:
x,v_0,...,v_(n-1),xproves the forward direction, while rotating any target cycle toxand deleting it proves the reverse direction because every remaining consecutive edge is an original edge. Garey and Johnson is now explicitly cited only for the two problem definitions and their classical status, matching what its catalog entries support.The value types are compatible (
Or -> Or), the target size fields are correctly named, and the stated bounds cover both branches. Forn >= 2, the exact construction hasn+1vertices andm+nedges; forn < 2, the fixed triangle is bounded byn+3vertices andm+n+3edges.Completeness
Literature scope. Waggoner's mapping begins with an arbitrary Hamiltonian Path instance and states no connectivity, degree, or endpoint precondition. The undirected specialization likewise applies to every repository instance.
Repository semantics and traces. The source evaluator accepts
[]forn=0and[0]forn=1, while the target rejects circuits below three vertices; the explicit triangle branch preserves both cases. Two isolated vertices reduce to a three-vertex path and remain infeasible. The repository representation allows loops and parallel edges, and the body now states that they are copied unchanged: loops cannot join distinct positions and parallel copies do not alter adjacency.The ephemeral validator checked the worked YES/NO examples, five boundary/representation cases, every simple graph through four vertices (76 instances), every feasible extracted witness, overhead spot-checks, and target validity. All 227 bucketed assertions passed.
Well-written
All required sections are present.
G,V,E,n, andmare defined before use; extraction is explicit; the target metrics matchHamiltonianCircuit; and the five-vertex example gives the source, all added edges, exact target size, a target cycle, and the extracted source path, plus a nontrivial negative companion.Recommendations
isPANN commentedon Nov 3, 2026
Please kindly check the following items (PR #1231):
predcommands for HamiltonianPath to HamiltonianCircuitJoin the discussion on Zulip — feel free to ask questions or leave feedback there.