[Rule] PARTITION INTO PATHS to BOUNDED COMPONENT SPANNING FOREST

[isPANN]

---

name: Rule
about: Propose a new reduction rule
title: "[Rule] PARTITION INTO PATHS OF LENGTH 2 to BOUNDED COMPONENT SPANNING FOREST"
labels: rule
assignees: ''
canonical_source_name: 'PARTITION INTO PATHS OF LENGTH 2'
canonical_target_name: 'BOUNDED COMPONENT SPANNING FOREST'
source_in_codebase: false
target_in_codebase: false

Source: PARTITION INTO PATHS OF LENGTH 2
Target: BOUNDED COMPONENT SPANNING FOREST

Motivation: Establishes NP-completeness of BOUNDED COMPONENT SPANNING FOREST via polynomial-time reduction from PARTITION INTO PATHS OF LENGTH 2. This is the original reduction by Hadlock (1974) showing that partitioning a graph into small connected components of bounded weight is intractable. The key insight is that a path of length 2 (P3) on 3 vertices is a connected subgraph, so a P3-partition of vertices is exactly a partition into connected components of size 3 with unit weights.
Reference: Garey & Johnson, Computers and Intractability, ND10, p.208

GJ Source Entry

[ND10] BOUNDED COMPONENT SPANNING FOREST
INSTANCE: Graph G=(V,E), weight w(v)∈Z_0^+ for each v∈V, positive integers K≤|V| and B.
QUESTION: Can the vertices in V be partitioned into k≤K disjoint sets V_1,V_2,...,V_k such that, for 1≤i≤k, the subgraph of G induced by V_i is connected and the sum of the weights of the vertices in V_i does not exceed B?
Reference: [Hadlock, 1974]. Transformation from PARTITION INTO PATHS OF LENGTH 2.
Comment: Remains NP-complete even if all weights equal 1 and B is any fixed integer larger than 2 [Garey and Johnson, ——]. Can be solved in polynomial time if G is a tree or if all weights equal 1 and B=2 [Hadlock, 1974].

Reduction Algorithm

Summary:
Given a PARTITION INTO PATHS OF LENGTH 2 instance with graph G = (V, E) where |V| = 3q, construct a BOUNDED COMPONENT SPANNING FOREST instance as follows:

1. Graph: Use the same graph G = (V, E).
2. Vertex weights: Set w(v) = 1 for all v in V (unit weights).
3. Parameters: Set K = q = |V|/3 (exactly q components) and B = 3 (each component has at most 3 vertices).

Correctness argument:

Forward direction: Suppose G has a partition into paths of length 2: V_1, V_2, ..., V_q where each V_t = {v_{t[1]}, v_{t[2]}, v_{t[3]}} has at least 2 of the 3 possible edges. With at least 2 edges among 3 vertices, the induced subgraph is connected (a path of length 2, i.e., P3, or a triangle). Each component has 3 vertices with unit weights, so the total weight is 3 = B. There are q = K components. Thus the BOUNDED COMPONENT SPANNING FOREST instance is satisfied.

Backward direction: Suppose G has a partition into k <= K = q connected components, each with total weight at most B = 3. Since all weights are 1, each component has at most 3 vertices. The total number of vertices is 3q and there are at most q components, so each component has exactly 3 vertices (by pigeonhole). A connected graph on 3 vertices must have at least 2 edges (a path P3 or a triangle K3). For P3: the path itself provides 2 of the 3 possible edges. For K3: all 3 edges are present. Either way, the partition condition for PARTITION INTO PATHS OF LENGTH 2 is satisfied.

Key invariant: A connected subgraph on exactly 3 vertices has at least 2 edges, which is precisely the PARTITION INTO PATHS OF LENGTH 2 requirement.

Size Overhead

Symbols:

• n = num_vertices of source graph G (must satisfy n = 3q)
• m = num_edges of source graph G

Target metric (code name)	Polynomial (using symbols above)
num_vertices	num_vertices
num_edges	num_edges
max_components (K)	num_vertices / 3
max_weight (B)	3

Derivation: The graph is used as-is with unit vertex weights. The parameters K and B 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 G with |V| = 3q that has a known P3-partition, reduce to BOUNDED COMPONENT SPANNING FOREST with unit weights, K = q, B = 3, solve the target with BruteForce, extract the partition, verify each component is connected with exactly 3 vertices and at least 2 internal edges.
• Negative test: construct a graph with no valid P3-partition (e.g., a star graph K_{1,3q-1} where the center has too high degree to be covered by paths), verify the target instance also has no solution.
• Check parameter values: K = |V|/3, B = 3, all weights = 1.

Example

Source instance (PartitionIntoPathsOfLength2):
Graph G with 9 vertices {0, 1, 2, 3, 4, 5, 6, 7, 8} and 11 edges:

• Edges: {0,1}, {1,2}, {0,2}, {3,4}, {4,5}, {6,7}, {7,8}, {1,3}, {2,6}, {5,8}, {0,5}
• |V| = 9 = 3 * 3, so q = 3
• Known P3-partition: V_1 = {0, 1, 2}, V_2 = {3, 4, 5}, V_3 = {6, 7, 8}
  • V_1: edges {0,1}, {1,2}, {0,2} -- 3 edges (triangle), >= 2 required
  • V_2: edges {3,4}, {4,5} -- 2 edges (path 3-4-5), >= 2 required
  • V_3: edges {6,7}, {7,8} -- 2 edges (path 6-7-8), >= 2 required
• Note: edges {1,3}, {2,6}, {5,8}, {0,5} cross between groups (these are "greedy traps" -- choosing a group like {1,3,4} might seem appealing due to edges {1,3} and {3,4}, but then vertex 0 and 2 would need to form groups with remaining vertices)

Constructed target instance (BoundedComponentSpanningForest):

• Same graph G with 9 vertices and 11 edges
• Vertex weights: all w(v) = 1
• K = 3 (at most 3 components)
• B = 3 (each component weight at most 3)

Solution mapping:

• Partition: V_1 = {0, 1, 2}, V_2 = {3, 4, 5}, V_3 = {6, 7, 8}
  • V_1: connected (triangle {0,1,2}), weight = 1+1+1 = 3 <= B
  • V_2: connected (path 3-4-5), weight = 1+1+1 = 3 <= B
  • V_3: connected (path 6-7-8), weight = 1+1+1 = 3 <= B
  • 3 components <= K = 3
• Reverse verification: each component has exactly 3 vertices and is connected, so each triple has >= 2 internal edges, confirming a valid P3-partition.

Greedy trap: Starting with the cross-edge {1,3}, one might try V_1 = {1, 3, 4} (edges {1,3}, {3,4} -- valid path). But then remaining vertices {0, 2, 5, 6, 7, 8} must partition into two connected triples. V_2 = {0, 2, 6}: edges {0,2} and {2,6} -- path, OK. V_3 = {5, 7, 8}: edge {7,8} present, need edge {5,7} or {5,8} -- {5,8} present! Path 5-8-7, OK. So this is also a valid partition, showing the instance has multiple solutions.

References

• [Hadlock, 1974]: [Hadlock1974] F. O. Hadlock (1974). "Minimum spanning forests of bounded trees". In: Proceedings of the 5th Southeastern Conference on Combinatorics, Graph Theory, and Computing, pp. 449–460. Utilitas Mathematica Publishing.
• [Garey and Johnson, ——]: (not found in bibliography)

[zazabap]

Issue Quality Check — Rule

Check	Result	Details
Usefulness	⚠️ Warn	Neither source nor target problem exists in the codebase
Non-trivial	⚠️ Warn	Parameter-setting reduction with no structural transformation, but correctness argument is non-trivial
Correctness	⚠️ Warn	Hadlock 1974 paper cannot be independently verified online; GJ reference is plausible but unverifiable
Well-written	❌ Fail	Multiple issues with completeness and consistency (see details)

Overall: 0 passed, 3 warnings, 1 failed

---

Usefulness

Neither "PARTITION INTO PATHS OF LENGTH 2" nor "BOUNDED COMPONENT SPANNING FOREST" exists in the codebase. Running pred show on both problem names confirms they are unknown. This means implementing this rule first requires implementing both models. Without either model in place, this rule is an orphan — it cannot be implemented or tested.

Since no path exists between these problems (neither exists), the reduction is technically novel. However, its practical value is limited until both models are added. The motivation section adequately explains the historical significance (Hadlock 1974, GJ ND10).

Result: Warn — novel reduction but both problems are missing from the codebase. File model issues first.

Non-trivial

This is a parameter-setting reduction — the graph is used as-is with no structural modification. The construction sets w(v) = 1, K = |V|/3, and B = 3. The issue itself acknowledges this: "This is a parameter-setting reduction with no graph modification, so the overhead is O(1) beyond reading the input."

However, the correctness argument is non-trivial: proving that the bijection between PPL2 solutions and BCSF solutions holds requires the pigeonhole argument (exactly 3 vertices per component) and the fact that a connected graph on 3 vertices has at least 2 edges. The backward direction reasoning is sound.

Result: Warn — while the construction itself is trivial (parameter setting only), the correctness argument has genuine content. This is borderline; a stricter reading would flag it as trivial since the implementation's reduce_to() would just copy the graph and set constants.

Correctness

Reference verification:

1. Garey & Johnson, ND10, p.208: This is a plausible reference. The ND10 problem "BOUNDED COMPONENT SPANNING FOREST" is confirmed to exist in the GJ appendix via multiple secondary sources (Wikipedia List of NP-complete Problems, OWU NP-complete Problems discussion site). The problem definition quoted in the issue matches the standard GJ formulation. Verified via secondary sources.

2. Hadlock, 1974, "Minimum spanning forests of bounded trees", Proceedings of the 5th Southeastern Conference on Combinatorics, Graph Theory, and Computing, pp. 449-460: The 5th Southeastern Conference did take place at Florida Atlantic University in February-March 1974. However, the specific Hadlock paper could not be found online — no digitized version exists in arxiv, Semantic Scholar, or standard academic databases. The GJ entry for ND10 does cite "[Hadlock, 1974]" as the source of the reduction from PPL2, which is consistent. Not independently verified; relying on GJ attribution.

3. Correctness of the reduction argument: The forward direction is straightforward. The backward direction uses a valid pigeonhole argument. The key invariant — that a connected graph on exactly 3 vertices must have at least 2 edges — is correct (minimum connected graph on 3 vertices is a path P3 with 2 edges). The claim that PPL2 requires "at least 2 of the 3 possible edges" matches the standard definition found in homework problem descriptions. Mathematically sound.

Result: Warn — the reduction argument is correct, but the primary reference (Hadlock 1974) cannot be independently verified beyond the GJ attribution.

Well-written

Several issues found:

4a — Information Completeness:

• All required sections are present and substantive. The GJ Source Entry is a helpful addition.

4b — Algorithm Completeness:

• The "Reduction Algorithm" is presented as a summary rather than a numbered step-by-step procedure. While the steps are clear enough to implement (copy graph, set unit weights, set K and B), the format should follow the template's expectation of a numbered algorithm.

4c — Symbol and Notation Consistency:

• The overhead table references num_vertices and num_edges as both "symbols" and "code names." These are fine.
• Issue: The overhead table lists max_components and max_weight as target metric code names, but since the target problem (BoundedComponentSpanningForest) does not exist in the codebase, these getter names are unverifiable. They are plausible but speculative.
• The overhead formula num_vertices / 3 for max_components uses integer division, which is only valid when num_vertices is divisible by 3. The issue mentions this constraint (n = 3q) but the overhead system does not enforce preconditions.

4d — Example Quality:

• The example is well-constructed with 9 vertices and multiple valid partitions.
• The "greedy trap" showing an alternative valid partition is a nice touch for illustrating non-uniqueness.
• However, a negative example (graph with no valid partition) is only mentioned in the Validation Method section, not fully worked out.

4e — Additional Issues:

• The issue title says "PARTITION INTO PATHS" but the body says "PARTITION INTO PATHS OF LENGTH 2" — the title is truncated and inconsistent.
• Multiple sections are marked with "Unverified: AI-generated" warnings, which is honest but suggests the content has not been human-reviewed.
• The "Garey and Johnson, ——" reference in the References section is listed as "not found in bibliography" — this is an incomplete citation (refers to a result where GJ prove the problem remains NP-complete for unit weights and fixed B > 2, but no specific publication is cited even in the original GJ book).

Result: Fail — title inconsistency with body, speculative target metric code names (max_components, max_weight) that cannot be verified against a non-existent target model, and algorithm presented as summary rather than numbered steps.

Recommendations

1. File model issues first: Both source and target problems need to be added to the codebase before this rule can be implemented. Create [Model] issues for both "PartitionIntoPathsOfLength2" and "BoundedComponentSpanningForest."
2. Fix the title: Change to [Rule] PARTITION INTO PATHS OF LENGTH 2 to BOUNDED COMPONENT SPANNING FOREST to match the body.
3. Number the algorithm steps: Convert the summary into explicit numbered steps (1. Copy graph G, 2. Set w(v) = 1 for all v, 3. Set K = |V|/3, 4. Set B = 3).
4. Clarify overhead metric names: Note that max_components and max_weight are proposed names, pending the target model's actual implementation. The target model will determine the actual getter method names.
5. Consider whether this reduction is worth implementing: Given that it is purely a parameter-setting reduction with no graph transformation, evaluate whether the engineering effort of implementing two new models plus this rule is justified by the theoretical value.