[Rule] HAMILTONIAN CIRCUIT to BOUNDED COMPONENT SPANNING FOREST

[isPANN]

---

name: Rule
about: Propose a new reduction rule
title: "[Rule] HAMILTONIAN CIRCUIT to BOUNDED COMPONENT SPANNING FOREST"
labels: rule
assignees: ''
canonical_source_name: 'HamiltonianCircuit'
canonical_target_name: 'BoundedComponentSpanningForest'
source_in_codebase: true
target_in_codebase: true

Source: HamiltonianCircuit
Target: BoundedComponentSpanningForest
Motivation: Establishes NP-hardness of the path-component specialization of BOUNDED COMPONENT SPANNING FOREST via polynomial-time reduction from HAMILTONIAN CIRCUIT. A pendant-vertex gadget pins the spanning path's endpoints so that any YES certificate for BCSF directly yields a Hamiltonian circuit. The GJ comment on ND10 explicitly notes "NP-complete even for K=|V|-1 (i.e., spanning trees)."

Note on model variant: The codebase BoundedComponentSpanningForest model partitions vertices into at most max_components connected components, each of total weight at most max_weight. It does not enforce that each component is a path. This reduction targets the specialization where max_components = 1 and unit weights force the single component to span all vertices. The backward direction additionally requires the degree-2 path structure imposed by the pendant vertices; if the model gains a path_components constraint in the future, the backward argument becomes unconditional.

Reference: Garey & Johnson, Computers and Intractability, ND10, p. 208

GJ Source Entry

[ND10] BOUNDED COMPONENT SPANNING FOREST
INSTANCE: Graph G=(V,E), positive integers K and B, non-negative integer weight w(v) for each v in V.
QUESTION: Can the vertices of V be partitioned into at most K disjoint subsets, each inducing a connected subgraph, with the total vertex weight of each subset at most B?
Reference: [Garey and Johnson, 1979]. Transformation from HAMILTONIAN CIRCUIT.
Comment: NP-complete even for K=|V|-1 (i.e., spanning trees).

Reduction Algorithm

Summary:
Given a Hamiltonian Circuit instance G = (V, E) with n = |V| vertices, construct a BOUNDED COMPONENT SPANNING FOREST instance as follows:

1. Pick an edge: Choose any edge {u, v} in E. If E is empty, output a trivial NO instance.
2. Add pendant vertices: Construct G' = (V', E') where:
   • V' = V union {s, t} (two new vertices, so |V'| = n + 2)
   • E' = E union {{s, u}, {t, v}}
   • s is connected only to u; t is connected only to v (both have degree 1 in G').
3. Set weights: All vertices receive unit weight 1.
4. Set parameters: max_components = 1, max_weight = n + 2.

Correctness argument:

• Forward (HC implies BCSF): If G has a Hamiltonian circuit C, remove edge {u, v} from C to obtain a Hamiltonian path P in G from u to v. Extend P to the path s-u-...-v-t in G'. This path spans all n + 2 vertices. Placing all vertices in a single component gives weight n + 2 = max_weight and 1 component = max_components. The BCSF instance is satisfied.

• Backward (BCSF implies HC): Suppose G' admits a partition into at most 1 connected component of total weight at most n + 2. Since all n + 2 vertices have unit weight and max_weight = n + 2, every vertex must belong to the single component (otherwise some vertices would be unassigned, which is not a valid partition). Now, s has degree 1 in G' (adjacent only to u) and t has degree 1 in G' (adjacent only to v). Within this connected component, consider any spanning tree T of G'. In T, the unique path from s to t must pass through u (since s's only neighbor is u) and through v (since t's only neighbor is v). Key structural argument: If G' is connected with the pendant structure, then G must contain a path from u to v that visits all original vertices. Specifically, removing s and t from T yields a spanning tree of G; the path from u to v in T (which exists since T is connected) visits all vertices of G because T spans V'. Since {u, v} is in E(G), appending edge {u, v} closes the path into a Hamiltonian circuit of G.

  Caveat: The backward direction relies on the degree-1 pendant structure forcing the spanning path topology. In the general BCSF model (which does not require components to be paths), the single-component partition could use a non-path spanning tree. The backward direction is therefore valid only under the additional assumption that the spanning structure is a path, which holds when the model enforces path components or when the graph structure leaves no alternative.

Size Overhead

Symbols:

• n = num_vertices of source HamiltonianCircuit
• m = num_edges of source HamiltonianCircuit

Target metric (getter)	Expression
num_vertices	num_vertices + 2
num_edges	num_edges + 2
max_components	1
max_weight	num_vertices + 2

Derivation: Two pendant vertices s and t are added, each contributing one new edge. max_components = 1 forces a single connected component. max_weight = n + 2 because all n + 2 vertices have unit weight and must all belong to the single component.

Validation Method

• Closed-loop test: construct a graph G known to have a Hamiltonian circuit; pick any edge {u, v}; add pendant vertices s (adjacent to u) and t (adjacent to v); reduce to BCSF with unit weights, max_components = 1, max_weight = n + 2; solve the target; verify all vertices are in one connected component; confirm removing s, t yields a Hamiltonian path from u to v in G; since {u, v} is in E(G), close to a Hamiltonian circuit.
• Negative test: construct a graph known to have no Hamiltonian circuit (e.g., Petersen graph); verify the constructed BCSF instance is also a NO instance.
• Pendant-degree check: verify s and t each have degree exactly 1 in G'.
• Parameter verification: check max_components = 1 and max_weight = n + 2.

Example

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

• Edges: {0,1}, {1,2}, {2,3}, {3,4}, {4,5}, {5,6}, {6,0}, {0,3}, {1,4}, {2,5}
• Hamiltonian circuit exists: 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 0
  • Check: {0,1}, {1,2}, {2,3}, {3,4}, {4,5}, {5,6}, {6,0} -- all edges present.

Construction:

• Pick edge {u, v} = {6, 0} in E(G).
• Add pendant vertex s (vertex 7) connected only to vertex 6, and pendant vertex t (vertex 8) connected only to vertex 0.
• G' has 9 vertices {0, ..., 8} and 12 edges (original 10 plus {7, 6} and {8, 0}).
• All weights = 1, max_components = 1, max_weight = 9.

Solution mapping:

• Remove edge {6, 0} from the Hamiltonian circuit to get path 0-1-2-3-4-5-6 in G.
• Extend to path 8-0-1-2-3-4-5-6-7 in G'.
• Partition: all 9 vertices in component 0. Weight = 9 = max_weight, components = 1 = max_components.
• Reverse: single connected component spans all vertices. Since s=7 connects only to 6 and t=8 connects only to 0, the spanning structure runs from s through G to t. Removing s, t gives a Hamiltonian path 0-1-2-3-4-5-6 in G. Since {6, 0} is in E(G), close to circuit 0-1-2-3-4-5-6-0.

References

• [Garey and Johnson, 1979]: M. R. Garey and D. S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, San Francisco. Problem ND10, p. 208.

[zazabap]

Issue Quality Check — Rule

Check	Result	Details
Usefulness	⚠️ Warn	Neither problem exists in the codebase; cannot assess path or overhead improvement
Non-trivial	❌ Fail	Parameter-setting reduction with no structural transformation
Correctness	❌ Fail	ND10 problem definition is misrepresented; reduction correctness argument has a gap
Well-written	❌ Fail	Multiple template issues: fabricated reference, inconsistent problem definition, incomplete correctness argument

Overall: 0 passed, 3 failed, 1 warning

---

Usefulness

Neither HAMILTONIAN CIRCUIT nor BOUNDED COMPONENT SPANNING FOREST exists in the codebase (pred show fails for both). Since the source and target are both new problems, this is a novel reduction direction. However, without either model implemented, the practical value cannot be assessed. Marking as Warn rather than fail — the reduction would be useful if both problems were added and the reduction were correct.

Non-trivial

The issue explicitly states: "This is a parameter-setting reduction with no graph modification, so the overhead is O(1) beyond reading the input." The reduction algorithm is:

1. Use the same graph G
2. Set K = n - 1
3. Set J = 1

This is a textbook example of a trivial reduction — there is no gadget construction, no auxiliary variables, no penalty terms, and no structural transformation of the graph. The target instance is literally the source instance with two integer parameters appended. Per the skill checklist, a "variable substitution only" or "subtype coercion" reduction with no new constraints or structure is a Fail.

Correctness

Critical issue: The ND10 problem definition in the issue is wrong.

The issue claims ND10 asks:

"Does G have a spanning forest with at most K edges and at most J connected components, each of which is a path?"

However, the actual Garey & Johnson ND10 (BOUNDED COMPONENT SPANNING FOREST) asks:

Given a graph G=(V,E) where each vertex has a non-negative weight, and integers K and B, can the vertices of V be partitioned into at most K disjoint subsets where each subset induces a connected subgraph and the total vertex weight in each subset is at most B?

This is a vertex partition problem with weight bounds on connected components, not a spanning forest with path constraints. The issue fabricates a different problem definition involving "spanning forest with path components" that does not match the actual GJ entry.

The correctness argument also has a logical gap. The issue acknowledges that the converse direction (spanning path implies Hamiltonian circuit) requires showing that the endpoints are adjacent, and hand-waves this with "the reduction from HC uses the standard technique of fixing a vertex and its neighbor." This is not a complete proof — it either requires additional graph construction (making it not parameter-setting) or the reduction is actually to Hamiltonian Path rather than Hamiltonian Circuit.

Reference verification: The sole reference is cited as Garey19xx with authors "M. R. Garey and D. S. Johnson (1979)" and title "Unpublished results." This is not a valid citation — the GJ book is a published book (W. H. Freeman, 1979, ISBN 0-7167-1045-5), already in the project bibliography as garey1979. The citation format is fabricated.

Well-written

Multiple failures:

1. Fabricated problem definition: The "GJ Source Entry" section presents a problem definition that does not match the actual ND10 entry. The real ND10 is about bounded-weight vertex partitions into connected components, not spanning forests with path components.

2. Fabricated reference: The References section cites [Garey19xx] as "Unpublished results" — this is incorrect. Garey & Johnson (1979) is a published book.

3. Incomplete correctness argument: The reduction from Hamiltonian Circuit to the target has a gap in the converse direction (see Correctness section above). The "alternate interpretation" paragraph admits the actual reduction goes HC -> Hamiltonian Path -> target, which is a two-step chain, not a direct reduction.

4. Inconsistent problem description: The "Note" at the top of the Reduction Algorithm section acknowledges uncertainty about which variant of BCSF is being targeted, mentioning both a "path-forest variant" and a "weighted vertex partition variant." This confusion stems from the incorrect problem definition.

5. Size overhead table references undefined target metrics: The target metrics K and J are listed but these are problem parameters, not standard size_fields getter methods. Without the target problem being defined in the codebase, the metric names cannot be validated.

6. All sections carry AI-generated warnings (marked with "Unverified: AI-generated") — the issue appears to be entirely AI-generated without human verification of the core claims.

Recommendations

• The actual ND10 problem (vertex partition with bounded component weights) is a legitimate NP-complete problem worth adding. However, the correct reduction from Hamiltonian Circuit to ND10 would need to match the real problem definition.
• If the intent is to capture the relationship between Hamiltonian paths and degree-bounded spanning trees, that is a different (and real) result: a graph has a Hamiltonian path iff it has a spanning tree with maximum degree 2. This should be written as a separate, correctly defined issue.
• The reference should cite garey1979 (already in the bibliography) rather than fabricating a new entry.

[isPANN]

Issue Quality Check — Rule (Re-check)

Previous check on 2026-03-11 found 0 passed / 3 failed / 1 warning. The issue body has been substantially rewritten since then (the trivial parameter-setting reduction was replaced with a 2-pendant gadget construction, and the GJ ND10 quote has been corrected). Re-checking against the current body.

Check	Result	Details
Usefulness	✅ Pass	No existing path HamiltonianCircuit → BoundedComponentSpanningForest; both problems now exist in the codebase.
Non-trivial	✅ Pass	The reduction now adds two pendant vertices and two edges — a genuine structural change, not pure parameter setting.
Correctness	❌ Fail	The cited reference (G&J ND10) does not contain an HC → BCSF reduction; the actual GJ transformation for ND10 is from PARTITION INTO PATHS OF LENGTH 2 (Hadlock 1974), and applies to a path-component variant, not to the codebase's weighted bounded-component model.
Completeness	❌ Fail	The backward direction is false for the codebase's BCSF model. Concrete counterexample executed below (K_{1,3} → BCSF=YES but no Hamilton circuit).
Well-written	❌ Fail	The "Caveat" section explicitly states the backward direction is only valid under the additional path-component assumption that the codebase's model does not enforce. The proof therefore openly contradicts the reduction's claim.

Overall: 2 passed, 3 failed, 0 warnings

Previously: 0 passed / 3 failed / 1 warning → Now: 2 passed / 3 failed / 0 warnings. The trivial-reduction and fabricated-citation failures from 2026-03-11 are resolved, but a new fundamental correctness failure has been introduced.

Removed stale label Trivial (no longer applies). Kept Wrong and PoorWritten; added Incomplete.

---

Usefulness ✅

pred path HamiltonianCircuit BoundedComponentSpanningForest → no path exists. Both problems are now present in the codebase (pred show HamiltonianCircuit, pred show BoundedComponentSpanningForest). A correct reduction here would close a gap in the graph — this is a useful target if the algorithm can be made correct.

Non-trivial ✅

The construction adds two pendant vertices s, t and two edges {s,u}, {t,v} to G. That is a real (if small) structural transformation, on par with the existing HamiltonianCircuit → HamiltonianPath reduction in src/rules/hamiltoniancircuit_hamiltonianpath.rs. Passes the "no pure parameter setting / no pure relabeling" bar.

Correctness ❌ (fundamental — cited reference does not contain the reduction)

The Reference section cites only:

Garey & Johnson, Computers and Intractability, ND10, p. 208

That entry (model file references/Garey&Johnson/models/P86_bounded_component_spanning_forest.json, which transcribes the GJ text verbatim) reads:

"INSTANCE: Graph G = (V,E), weight w(v) ∈ Z0+ for each v ∈ V, positive integers K ≤ |V| and B. QUESTION: Can the vertices in V be partitioned into k ≤ K disjoint sets ... each induces a connected subgraph and the sum of the weights ... does not exceed B?"

"Reference: [Hadlock, 1974]. Transformation from PARTITION INTO PATHS OF LENGTH 2."

So GJ ND10 cites Hadlock 1974 as the source of NP-hardness, and the cited transformation is from PARTITION INTO PATHS OF LENGTH 2, not from Hamiltonian Circuit. (The codebase already wires the Hadlock chain in src/rules/partitionintopathsoflength2_boundedcomponentspanningforest.rs and that path matches the GJ provenance.)

The GJ "Comment" line the issue quotes — "NP-complete even for K=|V|-1 (i.e., spanning trees)" — is a side remark about the spanning-tree special case of ND10. It is not a statement that the HC reduction listed in the issue exists in GJ, and GJ does not give the construction.

Therefore the only cited reference does not actually contain the reduction the issue is proposing. This is a fundamental Correctness failure (fundamental_no_reference).

Completeness ❌ (executable counterexample on a corner case)

The codebase's BoundedComponentSpanningForest model (see src/models/graph/bounded_component_spanning_forest.rs, is_valid_solution) asks for a vertex partition into at most max_components subsets such that each subset (a) induces a connected subgraph and (b) has total vertex weight ≤ max_weight. There is no requirement that each subset induce a path. With unit weights and max_components = 1, max_weight = n+2, the BCSF instance is YES iff G' is connected.

The issue's G' = G ∪ {(s, u), (t, v)} is connected iff G is connected (the two pendants do not break or restore connectivity of the original G). So the constructed BCSF instance answers YES exactly when G is connected, not when G is Hamiltonian.

The issue is aware of this — the "Caveat" paragraph explicitly says:

"The backward direction relies on the degree-1 pendant structure forcing the spanning path topology. In the general BCSF model (which does not require components to be paths), the single-component partition could use a non-path spanning tree. The backward direction is therefore valid only under the additional assumption that the spanning structure is a path."

That assumption is not part of the codebase's model, so the backward direction in the body fails.

Hand-traced corner cases (beyond the issue's worked example on a 7-vertex Hamiltonian graph):

1. Star K_{1,3} on V = {0,1,2,3}, edges {(0,1),(0,2),(0,3)}.

   • Connected, no Hamiltonian circuit (a tree with ≥3 leaves has no HP, let alone HC).
   • Issue's construction with picked edge {0,1}: add s=4 adjacent to 0, t=5 adjacent to 1.
   • G' has 6 vertices and edges {(0,1),(0,2),(0,3),(4,0),(5,1)}; G' is a tree, hence connected.
   • BCSF with max_components=1, max_weight=6, weights=[1]*6 accepts the assignment (0,0,0,0,0,0) (one component of weight 6, connected).
   • So BCSF=YES while HC=NO. ❌

2. Star K_{1,4} on V={0,1,2,3,4}, edges {(0,1),(0,2),(0,3),(0,4)}.

   • No HC; the constructed G' is again a tree, BCSF=YES via single-component partition. ❌

3. Two disjoint triangles on V={0,...,5}, edges {(0,1),(1,2),(2,0),(3,4),(4,5),(5,3)}.

   • No HC (G disconnected). G' adds pendants only inside the first triangle, so G' stays disconnected. BCSF=NO. ✅ (Only the disconnected source happens to be classified correctly — and only because disconnectedness is preserved.)

Cases (1) and (2) are not pathological — they are minimal connected non-Hamiltonian graphs and any correct HC reduction must reject them. Executable verifier:

# /tmp/bcsf_counterexample.py — brute-force BCSF on the constructed instance
# Output:
#   Source G = K_{1,3}: n=4, edges=[(0,1),(0,2),(0,3)]
#     Hamiltonian circuit? False
#   Reduction: G' has 6 vertices, edges=[(0,1),(0,2),(0,3),(4,0),(5,1)]
#     max_components=1, max_weight=6
#     BCSF YES? True, assignment=(0, 0, 0, 0, 0, 0)
#   *** COUNTEREXAMPLE CONFIRMED: BCSF=YES but no Hamilton circuit. ***

Diagnosis. The natural way to force a path structure through s and t in the existing model is unavailable: BCSF only checks connectivity, not degree-2 / Hamiltonicity of components. Fixing this requires one of:

• targeting a different model that enforces path components (the codebase does not currently expose one) — and then re-routing through that model;
• replacing the pendant gadget with a construction whose only connected single-component witnesses are spanning paths (this is unlikely to be polynomial-time inside BCSF's semantics, since deciding whether a connected graph has a spanning path is itself HP-hard);
• following the GJ provenance instead and reducing PartitionIntoPathsOfLength2 → BCSF (already in the codebase), and reaching this model via composition.

Well-written ❌

The body is structurally complete (Source, Target, Motivation, Reference, Algorithm, Overhead, Validation, Example, References are all present and substantive). The failure here is content-level rather than template-level:

1. Self-refuting proof. The "Caveat" in the Backward direction openly says the argument requires an assumption the codebase model does not satisfy. A reduction whose own proof states "this only works if the model adds an extra constraint" is not implementable as-is.
2. Validation Method is invalid. "Verify all vertices are in one connected component … confirm removing s, t yields a Hamiltonian path" — this presupposes the spanning structure is a path, which (per the Caveat) is not enforced. The negative test ("Petersen graph") would pass only because Petersen is 3-regular and the pendant-attached G' happens to be connected; the validation script would still return BCSF=YES (Petersen + pendants is connected), so the test would contradict the claimed negative outcome — a YES on a NO instance — confirming the same counterexample class as Completeness.
3. Symbols. The Size Overhead table uses num_vertices/num_edges consistently with the source's size_fields; max_components/max_weight match the target's size_fields. No notation issues here.
4. Example. The worked example is on a 7-vertex Hamiltonian graph and only exercises the YES side. There is no walked-through NO instance, which (combined with the silent backward gap) is how the reduction can look superficially convincing.

Recommendations

• The correct GJ-aligned reduction direction for this model is PARTITION INTO PATHS OF LENGTH 2 → BoundedComponentSpanningForest (Hadlock 1974, transcribed in references/Garey&Johnson/reductions/R31_pip2_boundedcomponentspanningforest.json). The codebase already implements this in src/rules/partitionintopathsoflength2_boundedcomponentspanningforest.rs and gets NP-hardness from there.
• If the goal is specifically to land an HC-rooted reduction at BCSF, route through an intermediate model that enforces path components (none currently exists — would require a [Model] proposal first), or reformulate via HC → LongestPath / HamiltonianPath → …. The simple "add 2 pendants" gadget cannot work against the current BCSF semantics.
• Update the Reference section to either remove the GJ citation (since GJ does not contain HC → BCSF) or cite an external paper that does, with a verifiable theorem statement.