[Rule] HamiltonianPath to HamiltonianCircuit

[isPANN]

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|.

1. If n<2, the source implementation accepts the unique empty/singleton ordering. Return a fixed triangle, and during extraction return the unique source ordering.
2. Otherwise add a new vertex x.
3. Preserve every edge in E and add {x,v} for every v in V.
4. Given a Hamiltonian cycle in the target, rotate it to start at x, delete x, 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

1. Source instance: V={0,1,2,3,4}, edges {01,12,23,34,02,13}. It has Hamiltonian path 0-1-2-3-4, alongside many invalid and partial orderings.
2. Construction: add vertex 5 and edges {05,15,25,35,45}.
3. Target instance: six vertices and eleven edges.
4. Round trip: cycle 5-0-1-2-3-4-5 maps to source path 0-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}
}

[isPANN]

Issue Quality Check — Rule

Check	Result	Details
Usefulness	✅ Pass	pred path HamiltonianPath HamiltonianCircuit --json reports no existing reduction path.
Non-trivial	✅ Pass	Adds a universal vertex, changes graph structure, and defines non-identity witness extraction.
Correctness	❌ Fail	The construction is correct, but the cited Garey–Johnson entries do not contain or prove this reduction.
Completeness	⚠️ Warn	The mapping passed exhaustive small-graph checks and the traced edge cases, but the issue does not document self-loops or parallel edges, which the repository's SimpleGraph representation permits.
Well-written	✅ Pass	All required sections are substantive; the notation, size fields, algorithm, extraction, and worked example are implementable and consistent.

Overall: 3 passed, 1 failed, 1 warning

---

Usefulness

Both endpoints resolve as existing SimpleGraph variants. The current graph has no HamiltonianPath → HamiltonianCircuit path, 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 and n incident 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:

• Garey & Johnson (1979), Appendix A1.3, p. 199, entry GT37, defines Hamiltonian Circuit and cites a transformation from Vertex Cover.
• Garey & Johnson (1979), Appendix A1.3, pp. 199–200, entry GT39, defines Hamiltonian Path and likewise cites a transformation from Vertex Cover.
• Neither entry states the universal-vertex reduction, and the claimed HP-to-HC theorem/proof was not found there. Thus the sentence “The universal-vertex construction is the standard textbook reduction” is not supported by the reference as cited.

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 < 2 branch.

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 deleting x from any target cycle leaves only original edges between consecutive old vertices.

Repository semantics. pred show HamiltonianPath --json reports size fields num_vertices and num_edges, with source variant SimpleGraph. The source evaluator accepts the empty ordering for n=0 and [0] for n=1; the target evaluator rejects every circuit with fewer than three vertices. SimpleGraph::new also does not reject self-loops or parallel edges.

Hand traces beyond the worked example:

1. Empty graph (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.
2. Two isolated vertices (n=2). The construction adds x and 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.
3. Self-loop/parallel-edge input. Original edges are copied and x is new, so loops and duplicate edges neither create an old-to-old adjacency that was absent nor affect the delete-x proof. The mapping remains well-defined.

Existing rules from the same source were also inspected: hamiltonianpath_isomorphicspanningtree.rs explicitly handles n=0 via SimpleGraph::path(0), while hamiltonianpath_degreeconstrainedspanningtree.rs explicitly 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. n and m are defined before use; target metric names match HamiltonianCircuit's num_vertices and num_edges; the formulas are valid upper bounds and the exact n >= 2 sizes 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

• Add a precise source for the universal-vertex theorem/proof; keep G&J only as a definition/complexity reference unless an exact supporting passage can be identified.
• State explicitly that loops and parallel edges, if present in the repository representation, are copied and do not affect correctness.

[isPANN]

Rule Fix

Diagnosis:

• Correctness/citation support: the universal-vertex construction is mathematically sound, but the Garey–Johnson catalog entries cited in the original body do not state or prove this reduction.
• Target-instance completeness: the construction also works for the repository's allowed self-loops and parallel edges, but the original body did not document why.
• All other checklist items passed: direction, both proof directions, construction completeness, extraction, polynomial time, overhead, example, Or -> Or compatibility, and target validity. No undirected cross-gadget rerouting risk applies because deleting the sole new vertex leaves only original consecutive edges.

Literature:

• Bowen Waggoner's University of Colorado course notes, “Standard 21: P and NP 2: NP-Completeness,” explicitly give the universal-vertex mapping and both correctness directions.
• Garey and Johnson is now described only as a source for the classical problem definitions and complexity status, not as the source of this construction.

Changes:

• Replaced the unsupported construction attribution with the exact Waggoner source and added its BibTeX entry.
• Clarified the undirected specialization of the cited construction.
• Documented preservation and correctness for self-loops and parallel edges, and added those cases to the validation method.

Smoke test:

• 227 bucketed assertions passed across the worked YES/NO instances, five edge cases, all 76 simple graphs through four vertices, every feasible witness extraction, five overhead spot-checks, and target-validity checks.
• Key confirming instances included 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]

Issue Quality Re-check — Rule

Check	Result	Details
Usefulness	✅ Pass	Both endpoints resolve and pred path HamiltonianPath HamiltonianCircuit --json still reports no existing path.
Non-trivial	✅ Pass	Adds a universal vertex and defines non-identity cycle rotation/deletion extraction.
Correctness	✅ Pass	The construction now has an exact supporting source; Garey–Johnson is accurately limited to problem definitions and classical complexity status.
Completeness	✅ Pass	The body covers the evaluator's n < 2 semantics plus allowed self-loops and parallel edges; exhaustive and witness-level checks passed.
Well-written	✅ Pass	Every required section is substantive, notation and metric names are consistent, and the worked round trip is implementable.

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 show resolves HamiltonianPath/SimpleGraph and HamiltonianCircuit/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 with n incident 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),x proves the forward direction, while rotating any target cycle to x and 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. For n >= 2, the exact construction has n+1 vertices and m+n edges; for n < 2, the fixed triangle is bounded by n+3 vertices and m+n+3 edges.

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 [] for n=0 and [0] for n=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, and m are defined before use; extraction is explicit; the target metrics match HamiltonianCircuit; 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

• None blocking; the issue is ready for implementation.