[Rule] HAMILTONIAN CIRCUIT to HAMILTONIAN PATH

[isPANN]

Source: HamiltonianCircuit
Target: HamiltonianPath
Motivation: Establishes NP-completeness of Hamiltonian Path via a minimal modification to a Hamiltonian Circuit instance, showing that the path variant is no easier than the circuit variant despite removing the closing-edge requirement. Connects two currently isolated problems in the reduction graph.
Reference: Garey & Johnson, Computers and Intractability, 1979 (HC and HP are both NP-complete; the standard HC→HP reduction is the vertex-duplication construction with pendant endpoints). See also Wikipedia: Hamiltonian path problem, U of Toronto CSC 463 notes.

Reduction Algorithm

Given a HamiltonianCircuit instance G = (V, E) with n = |V| vertices and m = |E| edges, construct a HamiltonianPath instance G' = (V', E') as follows:

1. Pick a vertex. Choose an arbitrary vertex v ∈ V (the implementation uses v = 0).

2. Duplicate v. Create a new vertex v' (index n) and connect v' to every neighbor of v in G. That is, for each edge {v, u} ∈ E, add edge {v', u} to E'. The vertex v retains all its original edges.

3. Add pendant s. Create a new vertex s (index n + 1) with a single edge {s, v}. Since deg(s) = 1, any Hamiltonian path in G' must start or end at s.

4. Add pendant t. Create a new vertex t (index n + 2) with a single edge {t, v'}. Since deg(t) = 1, any Hamiltonian path in G' must start or end at t.

Result: G' = (V', E') where V' = V ∪ {v', s, t} and E' = E ∪ {{v', u} : {v, u} ∈ E} ∪ {{s, v}, {t, v'}}.

Correctness argument:

• (⇒) G has a Hamiltonian circuit ⟹ G' has a Hamiltonian path.
  Let C = (v, u₁, u₂, …, u_{n−1}, v) be a Hamiltonian circuit in G. Then P = (s, v, u₁, u₂, …, u_{n−1}, v', t) is a Hamiltonian path in G': the edge {s, v} exists by construction; the sub-path v → u₁ → … → u_{n−1} follows edges from C; the edge {u_{n−1}, v'} exists because {u_{n−1}, v} ∈ E and v' copies v's neighborhood; and {v', t} exists by construction.

• (⟸) G' has a Hamiltonian path ⟹ G has a Hamiltonian circuit.
  Any Hamiltonian path in G' must use s and t as endpoints (both have degree 1). So the path has the form (s, v, x₁, x₂, …, x_{n−1}, v', t) where {x₁, …, x_{n−1}} = V \ {v}. The sub-sequence (v, x₁, …, x_{n−1}) visits every vertex of G exactly once, and {x_{n−1}, v'} ∈ E' implies {x_{n−1}, v} ∈ E (since v' has the same neighbors as v). Therefore (v, x₁, …, x_{n−1}, v) is a Hamiltonian circuit in G.

Solution extraction: Given a Hamiltonian path P = (s, v, x₁, …, x_{n−1}, v', t) in G', return the Hamiltonian circuit (v, x₁, …, x_{n−1}) in G. (If P runs t-first, reverse it first.)

Size Overhead

Let n = num_vertices and m = num_edges of the source HamiltonianCircuit instance G, and let d = deg(v) where v is the chosen vertex.

Target metric (code name)	Expression	Derivation
num_vertices	num_vertices + 3	Original n vertices + v' + s + t
num_edges	num_edges + num_vertices + 1	Original m edges + d edges from v' + 2 pendant edges. Worst case: d = n − 1, giving m + (n − 1) + 2 = m + n + 1

Note: The exact edge count is m + d + 2 where d = deg(v). The implementation picks v = 0, so the actual count depends on deg(0). The overhead expression uses the worst case d = n − 1 since deg(v) is not available as a source size field.

Validation Method

• Closed-loop test: Construct a HamiltonianCircuit instance with a known Hamiltonian circuit, apply the reduction to get a HamiltonianPath instance, solve with BruteForce, verify a Hamiltonian path is found, and extract the solution back to verify it is a valid Hamiltonian circuit in the source.
• Pendant endpoint check: Verify that in every Hamiltonian path found in G', the endpoints are s and t (the degree-1 pendant vertices).
• Size verification: Check |V'| = |V| + 3 and |E'| = |E| + deg(v) + 2 for the specific instance.
• Negative test: Construct a graph without a Hamiltonian circuit (e.g., a path graph P_3), apply the reduction, and verify that no Hamiltonian path exists in the target.
• Round-trip: Brute-force solve the target, map back to the source, and confirm the mapped solution is valid in the source.

Example

Source instance (HamiltonianCircuit):
Graph G = C_4 (4-cycle) with 4 vertices and 4 edges:

• V = {0, 1, 2, 3}
• E = {(0,1), (1,2), (2,3), (0,3)}

G has 2 Hamiltonian circuits (the two traversal directions): [0, 1, 2, 3] and [0, 3, 2, 1].

Reduction (v = 0, neighbors of 0 = {1, 3}):

1. Duplicate v = 0: create v' = 4, add edges {(4,1), (4,3)}
2. Add pendant s = 5 with edge {(5,0)}
3. Add pendant t = 6 with edge {(6,4)}

Target instance (HamiltonianPath):

• V' = {0, 1, 2, 3, 4, 5, 6} — 7 vertices (= 4 + 3 ✓)
• E' = {(0,1), (1,2), (2,3), (0,3), (4,1), (4,3), (5,0), (6,4)} — 8 edges (= 4 + deg(0) + 2 = 4 + 2 + 2 ✓)

Hamiltonian paths in G' (all 4, verified by exhaustive enumeration):

1. [5, 0, 1, 2, 3, 4, 6] — corresponds to HC [0, 1, 2, 3]
2. [5, 0, 3, 2, 1, 4, 6] — corresponds to HC [0, 3, 2, 1]
3. [6, 4, 3, 2, 1, 0, 5] — reverse of path 1
4. [6, 4, 1, 2, 3, 0, 5] — reverse of path 2

All paths have endpoints {5, 6} = {s, t} ✓

Non-satisfying configurations (examples):

• [0, 1, 2, 3, 4, 5, 6]: fails because edge (4, 5) does not exist — s = 5 is only connected to v = 0
• [5, 0, 1, 2, 4, 3, 6]: fails because edge (2, 4) does not exist — v' = 4 is only connected to neighbors of v = 0, which are {1, 3}, not {2}

Solution extraction:
From HP [5, 0, 1, 2, 3, 4, 6], strip pendant endpoints s = 5 and t = 6, replace v' = 4 with v = 0: circuit [0, 1, 2, 3] → verify (0,1), (1,2), (2,3), (3,0) are all edges in G ✓

Negative test:
Source: P_3 (path graph, 3 vertices, 2 edges: (0,1), (1,2)) — no Hamiltonian circuit.
After reduction with v = 0 (neighbors = {1}): v' = 3, s = 4, t = 5. Target has 6 vertices, 5 edges: {(0,1), (1,2), (3,1), (4,0), (5,3)}.
Exhaustive search confirms: 0 Hamiltonian paths in the target ✓

[zazabap]

Issue Quality Check — Rule

Check	Result	Details
Usefulness	⚠️ Warn	Both source (HamiltonianCircuit) and target (HamiltonianPath) problems are not implemented
Non-trivial	✅ Pass	Construction involves structural graph modification (adding vertices, rewiring edges)
Correctness	❌ Fail	The described algorithm is not a general HC→HP reduction; it is tied to the VC→HC gadget construction
Well-written	❌ Fail	Algorithm not self-contained; example too large; undefined symbols from VC→HC context

Overall: 1 passed, 1 warning, 2 failed

---

Usefulness

Neither HamiltonianCircuit nor HamiltonianPath exist in the codebase (confirmed via pred show). This means this reduction rule cannot be implemented without first adding both problem models. As new problems, there is no existing path between them, so the reduction would be novel once the models exist. However, the practical value is limited until both models are added.

Non-trivial

The reduction involves genuine structural transformation: adding new vertices, rewiring edges, and creating pendant vertices to force path endpoints. This is not a variable substitution, subtype coercion, or identity mapping. Pass.

Correctness

The reference to Garey & Johnson (1979), Section 3.1.4, p.60 is valid — this book is already in the project bibliography (garey1979). The quoted passage is indeed from that section.

However, the reduction described in the issue is not a general Hamiltonian Circuit to Hamiltonian Path reduction. The algorithm specifically modifies "the graph G' obtained at the end of the construction" — meaning the graph produced by the VC→HC reduction. It references selector vertices a_1, ..., a_K, gadget paths (v, e_{v[deg(v)]}, 6), and other structures that only exist in the specific VC→HC construction. This means:

1. The algorithm only works on HC instances that were produced by the VC→HC reduction, not on arbitrary HC instances.
2. It is really a step in a composite VC→HP reduction, not a standalone HC→HP reduction.

The standard direct reduction from HC to HP is well-known and much simpler: given a graph G, pick any vertex v, create a copy v', connect v' to all neighbors of v. A Hamiltonian path from v to v' exists in the new graph iff a Hamiltonian cycle exists in G. This adds only 1 vertex and at most deg(v) edges, and works on any HC instance. See, e.g., the discussions at OWU NP-Complete Problems or GeeksforGeeks.

Well-written

Several issues:

1. Algorithm is not self-contained. The reduction algorithm references symbols from the VC→HC construction (a_1, ..., a_K, selector vertices, gadget paths (v, e_{v[deg(v)]}, 6)) without defining them. A reader (or implementer) cannot understand the algorithm without first reading the VC→HC proof in Garey & Johnson. A standalone HC→HP reduction should take an arbitrary graph with a Hamiltonian circuit question and produce a Hamiltonian path instance.

2. Example is too large to verify. The example uses a graph with 75 vertices (from VC→HC applied to K_4), producing a 78-vertex target. This is far too large for brute-force verification or hand-checking. A good example should use a small graph (4-6 vertices) where the Hamiltonian cycle and path can be verified by inspection.

3. Overhead table references undefined getter methods. The target problem HamiltonianPath does not exist in the codebase, so num_vertices and num_edges cannot be validated against actual getter methods.

4. Missing sections. The Validation Method describes testing via "R07" and "R08" (internal rule identifiers) rather than a standalone test strategy.

Recommendations

• Replace the described reduction with the standard direct HC→HP reduction (vertex duplication), which works on arbitrary HC instances and is simpler to implement and verify.
• Provide a small worked example (e.g., a 4- or 5-vertex graph with a known Hamiltonian cycle, showing the modified graph and the resulting Hamiltonian path).
• Ensure both HamiltonianCircuit and HamiltonianPath model issues exist before this rule issue, or file them first.
• Define all symbols used in the algorithm within the issue itself, independent of any prior reduction.

[zazabap]

Issue Quality Check — Rule

Check	Result	Details
Usefulness	⚠️ Warn	Both source and target problems do not exist in the codebase
Non-trivial	⚠️ Warn	Construction is non-trivial but depends on a specific prior reduction (VC→HC)
Correctness	❌ Fail	Reduction is not self-contained; describes a modification of a VC→HC construction, not a standalone HC→HP reduction
Well-written	❌ Fail	Multiple structural and content issues (see details below)

Overall: 0 passed, 2 warnings, 2 failed

---

Usefulness

Neither HamiltonianCircuit nor HamiltonianPath exist as problems in the codebase. Running pred show HamiltonianCircuit and pred show HamiltonianPath both fail. This means implementing this rule requires first adding both models as new problems. The rule itself would be novel (no existing path between these problems), but it cannot be implemented until both prerequisite models exist.

Verdict: Warning — novel reduction, but both source and target models are missing prerequisites.

Non-trivial

The described construction adds three new vertices and rewires edges, which is a genuine structural transformation (not a variable substitution, subtype coercion, or identity). However, this is a relatively minor modification (3 vertices, 2 new edges, edge replacement) that sits at the boundary of triviality.

Verdict: Warning — the construction is non-trivial but minimal.

Correctness

Reference verification: The reference to Garey & Johnson, Computers and Intractability, Section 3.1.4, p.60 is a real and well-known textbook (confirmed in the project bibliography as garey1979). The book does discuss the HC→HP reduction in that section.

Critical problem — reduction is not self-contained: The issue's "Reduction Algorithm" section directly quotes Garey & Johnson's text, which describes a modification to "the graph G' obtained at the end of the construction" — referring to the preceding VC→HC reduction in Section 3.1.4. The algorithm references:

• "selector vertices a_1, ..., a_K" from the VC→HC construction
• Edges of the form {a_1, (v, e_{v[deg(v)]}, 6)} — gadget-specific notation from the VC→HC proof
• "the construction just used for HC" — the VC→HC reduction

This means the described reduction is not a standalone HC→HP reduction. It is a shortcut that modifies the output of a specific VC→HC construction. A valid HC→HP reduction must work on any Hamiltonian Circuit instance, not just those produced by a particular prior reduction.

The standard standalone HC→HP reduction is much simpler: given graph G = (V, E) and an arbitrary vertex v in V, construct G' by adding a new vertex v' with edges to all neighbors of v. Then G has a Hamiltonian cycle iff G' has a Hamiltonian path from v to v'. This well-known construction is not what the issue describes.

Verdict: Fail — the reduction algorithm is not a valid standalone HC→HP reduction; it is coupled to a prior VC→HC construction.

Well-written

4a — Information completeness:

• Source/Target: Present but refer to problems not in the codebase
• Motivation: Present but generic ("NP-completeness of HAMILTONIAN PATH")
• Reference: Present (Garey & Johnson)
• Reduction Algorithm: Present but not self-contained (see Correctness)
• Size Overhead: Present with table
• Validation Method: Present
• Example: Present

4b — Algorithm completeness:
The algorithm is a copy of Garey & Johnson's text interleaved with an AI-generated summary. The summary (Step 1–4) is more readable but inherits the fundamental flaw of depending on the VC→HC construction's internal structure. A programmer cannot implement this as a standalone ReduceTo<HamiltonianPath> for HamiltonianCircuit because the algorithm requires knowledge of the VC→HC gadgets.

4c — Symbol and notation consistency:

• The symbols a_0, a_{K+1}, a_{K+2} are defined in the algorithm but K is only defined in the Size Overhead section as "cover size bound K" — which is a parameter of the VC problem, not the HC input.
• The notation (v, e_{v[deg(v)]}, 6) is gadget-internal notation from the VC→HC proof, not defined anywhere in this issue.
• The overhead table uses num_vertices and num_edges as code metric names, but since HamiltonianCircuit does not exist in the codebase, these cannot be verified against actual getter methods.

4d — Example quality:
The example starts from "G' produced by the VC→HC reduction from the example in R07" — it references an external "R07" without defining it. The example is not self-contained and cannot be verified independently. It uses a K_4 graph with 75 vertices as the source instance, which is far too large to be brute-force solvable or hand-verifiable.

Verdict: Fail — algorithm is not self-contained, symbols are inconsistently defined, and example references external constructions.

Recommendations

1. Rewrite as a standalone reduction. The standard HC→HP reduction is simple: given graph G = (V, E) and an arbitrary vertex v in V, construct G' by adding a new vertex v' with edges to all neighbors of v. Then G has a Hamiltonian cycle iff G' has a Hamiltonian path from v to v'. This is self-contained and does not depend on any prior reduction.

2. Add prerequisite model issues first. Before this rule can be implemented, issues for HamiltonianCircuit and HamiltonianPath models must be created and implemented.

3. Provide a small, self-contained example. Use a small graph (e.g., a cycle C_4 or C_5) as the HC instance and show the full HP construction step by step, with a hand-verifiable solution.

4. Remove AI-generated warnings. The issue body contains multiple <!-- Unverified: AI-generated ... --> markers, suggesting the content has not been human-reviewed.

[isPANN]

Issue Quality Check — Rule

Check	Result	Details
Usefulness	✅ Pass	No existing path between HC and HP; novel reduction
Non-trivial	✅ Pass	Structural graph modification (vertex addition, edge rewiring)
Correctness	❌ Fail	Algorithm is not a standalone HC→HP reduction; depends on VC→HC construction
Well-written	❌ Fail	Algorithm not self-contained; example too large; undefined symbols

Overall: 2 passed, 0 warnings, 2 failed

---

Usefulness

No reduction path exists between HamiltonianCircuit and HamiltonianPath in the codebase (pred path confirms). Both problems are currently isolated nodes with no reductions to or from any other problem. Adding this rule would connect them and contribute to the reduction graph. Motivation is present and reasonable ("path variant is no easier than the circuit variant"). Pass.

Non-trivial

The described construction involves genuine structural transformation: adding new vertices, creating pendant edges, and rewiring connections. This is not a variable substitution, subtype coercion, or identity mapping. Even the simpler standard HC→HP reduction (vertex duplication with pendants) involves non-trivial graph modification. Pass.

Correctness

Reference verification: Garey & Johnson, Computers and Intractability, Section 3.1.4, p.60 — confirmed in project bibliography as garey1979. The quoted passage is authentic.

Critical flaw — algorithm is not a standalone reduction:

The issue's algorithm directly quotes G&J's text: "We simply modify the graph G' obtained at the end of the construction as follows" — referring to the graph produced by the preceding VC→HC reduction. The algorithm references:

• Selector vertices a_1, ..., a_K from the VC→HC construction
• Gadget-internal edges {a_1, (v, e_{v[deg(v)]}, 6)} — notation specific to the VC→HC proof
• "The construction just used for HC" — the VC→HC reduction

This means the described algorithm is not a standalone HC→HP reduction. It is a shortcut for proving HP is NP-complete by modifying the VC→HC construction output. A valid ReduceTo<HamiltonianPath> for HamiltonianCircuit implementation must work on any Hamiltonian Circuit instance, not just those produced by a specific prior reduction.

The standard standalone HC→HP reduction (well-documented in textbooks and lecture notes):

1. Given graph G = (V, E) and an arbitrary vertex v ∈ V
2. Create a copy v' with the same neighborhood as v
3. Add pendant vertex s connected only to v
4. Add pendant vertex t connected only to v'
5. G has a Hamiltonian cycle ⟺ the new graph has a Hamiltonian path (from s to t)

This adds 3 vertices and deg(v) + 2 edges, works on any HC instance, and is self-contained.

Sources: Wikipedia: Hamiltonian path problem, HandWiki, U of Toronto CSC 463 notes, OWU NP-Complete Problems.

Overhead expressions: The issue's num_vertices + 3 and num_edges + 2 are internally consistent for the non-standalone construction but incorrect for the standard reduction. The standard reduction gives num_vertices + 3 vertices (still correct) but num_edges + degree_of_v + 2 edges (not num_edges + 2). Since the degree of v varies, the worst-case overhead is num_edges + num_vertices + 1 (when v has maximum degree n−1).

Verdict: Fail — the algorithm is coupled to VC→HC and cannot serve as a standalone HC→HP reduction rule.

Well-written

4a — Required sections: All present, but several have fundamental content issues (see below).

4b — Algorithm completeness: The algorithm is a copy of the G&J passage (which describes a VC→HC modification) interleaved with an AI-generated summary. A programmer cannot implement ReduceTo<HamiltonianPath> for HamiltonianCircuit from this because:

• The algorithm requires knowledge of VC→HC gadgets (selector vertices, gadget paths)
• It does not describe what to do with an arbitrary graph that has a Hamiltonian circuit

4c — Symbol and notation consistency:

• K (cover size bound) is a VC parameter, undefined in the HC→HP context
• (v, e_{v[deg(v)]}, 6) is gadget-internal notation from VC→HC, never defined in this issue
• a_1, ..., a_K are selector vertices from VC→HC, not elements of an arbitrary HC instance
• Overhead metric names (num_vertices, num_edges) do match actual getter methods on both HamiltonianCircuit and HamiltonianPath ✓

4d — Example quality:

• Size: 78 vertices → search space is 78^78 ≈ 10^148. Far too large for brute-force verification or hand-checking. Target: 4–8 vertices.
• Self-contained: No — references "G' produced by the VC→HC reduction from the example in R07" without defining it
• Fully worked: No — does not enumerate the actual vertices/edges of the 78-vertex graph; only summarizes dimensions
• Suboptimal solutions: No non-satisfying configurations are discussed
• Python verification: impossible on 78-vertex instance; standard reduction verified on C_4 (4-cycle) confirms the vertex-duplication construction works correctly

Verdict: Fail — algorithm not self-contained, example not verifiable.

Recommendations

1. Replace with the standard standalone HC→HP reduction. Pick vertex v, create v' with same neighbors, add pendants s (to v) and t (to v'). This is self-contained, simple, and well-documented.
2. Provide a small worked example. Use C_4 or C_5 as the HC instance and show the full construction step by step (list all vertices, edges, and the Hamiltonian path in the target).
3. Fix overhead expressions. The standard reduction has num_vertices + 3 vertices but num_edges + degree_of_v + 2 edges. Since degree_of_v is instance-dependent, the worst-case expression is num_edges + num_vertices + 1.
4. Remove VC→HC dependencies. All symbols, notation, and references to selector vertices and gadget paths should be eliminated.

[isPANN]

Fix-issue changelog

• Replaced non-standalone VC→HC-dependent algorithm with the standard textbook vertex-duplication reduction (pick v, create v' with same neighbors, add pendants s and t)
• Added complete correctness argument (both directions: ⇒ and ⟸)
• Added explicit solution extraction procedure
• Replaced 78-vertex example with C_4 (4-cycle) — fully worked with all 4 Hamiltonian paths enumerated and verified by exhaustive search
• Added negative test case (P_3 path graph → no Hamiltonian path in target)
• Added 2 non-satisfying configuration examples with explanations
• Fixed overhead expressions: num_vertices + 3 (exact), num_edges + num_vertices + 1 (worst-case, with derivation)
• Rewrote validation method as standalone (removed references to "R07" and VC→HC pipeline)
• Updated references: added Wikipedia and U of Toronto CSC 463 lecture notes
• Removed all undefined VC→HC symbols (selector vertices, gadget notation)
• Removed <!-- Unverified: AI-generated --> markers (all content now verified)

Applied by /fix-issue.