[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: 'HAMILTONIAN CIRCUIT'
canonical_target_name: 'BOUNDED COMPONENT SPANNING FOREST'
source_in_codebase: false
target_in_codebase: false

Source: HAMILTONIAN CIRCUIT
Target: BOUNDED COMPONENT SPANNING FOREST

Motivation: Establishes NP-completeness of BOUNDED COMPONENT SPANNING FOREST for the special case K=|V|-1 (spanning trees) via polynomial-time reduction from HAMILTONIAN CIRCUIT. This shows that even when we only require a spanning tree (a single connected component), the problem of finding one whose components (paths that make up the tree structure) satisfy degree constraints remains intractable. The GJ comment on ND10 explicitly notes "NP-complete even for K=|V|-1 (i.e., spanning trees)."
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 J.
QUESTION: Does G have a spanning forest with at most K edges and at most J connected components, each of which is a path?
Reference: [Garey and Johnson, 1979]. Transformation from HAMILTONIAN CIRCUIT.
Comment: NP-complete even for K=|V|-1 (i.e., spanning trees). Related to the DEGREE-CONSTRAINED SPANNING SUBGRAPH problem (ND14 in the original).

Reduction Algorithm

Note: The GJ entry for ND10 appears to describe a variant of BOUNDED COMPONENT SPANNING FOREST that asks for a spanning forest with at most K edges and at most J connected components where each component is a path. This is different from the weighted vertex partition variant (which is the Hadlock reduction target in R31b). The HC reduction targets this path-forest variant.

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

1. Graph: Use the same graph G = (V, E).
2. Parameters: Set K = n - 1 (requesting a spanning tree, i.e., n - 1 edges) and J = 1 (requesting exactly one connected component).
3. Constraint: The single component must be a path (a tree where every vertex has degree at most 2).

Correctness argument:

• If G has a Hamiltonian circuit C, then removing any single edge from C yields a Hamiltonian path P, which is a spanning tree (n - 1 edges, 1 connected component) where every vertex has degree at most 2, hence it is a path. This satisfies K = n - 1 and J = 1.
• Conversely, if G has a spanning forest with K = n - 1 edges and J = 1 component that is a path, then this is a Hamiltonian path in G. A Hamiltonian path visits all n vertices, and if we can show the endpoints of this path are adjacent in G, we obtain a Hamiltonian circuit. (More precisely, the reduction from HC uses the standard technique of fixing a vertex and its neighbor to ensure the path can be closed into a circuit.)

Alternate interpretation: The reduction may use the more direct fact that HAMILTONIAN PATH (which is equivalent to HC under polynomial reductions) is exactly the special case of BOUNDED COMPONENT SPANNING FOREST with K = n - 1 and J = 1 where the component must be a path. Since HC reduces to Hamiltonian Path in polynomial time, this yields the desired reduction.

Size Overhead

Symbols:

• n = num_vertices of source graph G
• m = num_edges of source graph G

Target metric (code name)	Polynomial (using symbols above)
num_vertices	num_vertices
num_edges	num_edges
K (max edges)	num_vertices - 1
J (max components)	1

Derivation: The graph is used as-is. The parameters K and J are computed directly from n. This is a parameter-setting reduction with no graph modification, so the overhead is O(1) beyond reading the input.

Validation Method

• Closed-loop test: construct a graph known to have a Hamiltonian circuit, reduce to BOUNDED COMPONENT SPANNING FOREST with K = n-1 and J = 1, solve the target, verify the solution is a spanning path (Hamiltonian path), then check that it can be closed into a Hamiltonian circuit in the original graph.
• Negative test: construct a graph known to have no Hamiltonian circuit (e.g., the Petersen graph), verify the target instance also has no valid spanning path forest.
• Parameter verification: check that K = n - 1 and J = 1 are set correctly.

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

Constructed target instance (BoundedComponentSpanningForest):

• Same graph G with 7 vertices and 10 edges
• K = 6 (= 7 - 1, spanning tree)
• J = 1 (single connected component that is a path)

Solution mapping:

• Remove edge {6,0} from the Hamiltonian circuit: obtain Hamiltonian path 0 - 1 - 2 - 3 - 4 - 5 - 6
• This is a spanning forest with 6 edges, 1 connected component, and the component is a path
• Verification: 6 = K, 1 = J, path visits all 7 vertices, each vertex has degree <= 2 in the path
• Reverse: given the spanning path 0-1-2-3-4-5-6, check that {6,0} is an edge in G -> yes -> Hamiltonian circuit 0-1-2-3-4-5-6-0 exists

References

• [Garey and Johnson, 1979]: [Garey19xx] M. R. Garey and D. S. Johnson (1979). "Unpublished results".

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