[Model] BoundedComponentSpanningForest

[isPANN]

---

name: Problem
about: Propose a new problem type
title: "[Model] BoundedComponentSpanningForest"
labels: model
assignees: ''

Motivation

BOUNDED COMPONENT SPANNING FOREST from Garey & Johnson, A2 ND10. An NP-complete graph partitioning problem that asks whether the vertices of a weighted graph can be grouped into at most K connected components, each with total weight at most B. This problem generalizes both Hamiltonian circuit (when K=1 and the spanning subgraph must be a cycle) and balanced graph partitioning problems. It has direct applications to political redistricting (partitioning precincts into contiguous districts of bounded population).

Associated reduction rules:

• As target: R31a (HAMILTONIAN CIRCUIT -> BOUNDED COMPONENT SPANNING FOREST) via Garey and Johnson, 1979
• As target: R31b (PARTITION INTO PATHS OF LENGTH 2 -> BOUNDED COMPONENT SPANNING FOREST) via Hadlock, 1974

Definition

Name: BoundedComponentSpanningForest
Canonical name: BOUNDED COMPONENT SPANNING FOREST
Reference: Garey & Johnson, Computers and Intractability, A2 ND10

Mathematical definition:

INSTANCE: Graph G = (V,E), weight w(v) ∈ Z⁺₀ for each v ∈ V, positive integers K ≤ |V| and B.
QUESTION: Can the vertices in V be partitioned into k ≤ K disjoint sets V₁, V₂, ..., Vₖ such that, for 1 ≤ i ≤ k, the subgraph of G induced by Vᵢ is connected and the sum of the weights of the vertices in Vᵢ does not exceed B?

Variables

• Count: n = |V| variables (one per vertex), encoding the component assignment
• Per-variable domain: {0, 1, ..., K-1}, indicating which partition set the vertex is assigned to
• dims() specification: vec![K; n] — n variables each with domain size K
• Meaning: Variable i = j means vertex i is assigned to component V_j. A valid assignment must ensure: (1) each non-empty component induces a connected subgraph, (2) the total weight in each component is at most B, and (3) at most K components are used.

Schema (data type)

Type name: BoundedComponentSpanningForest
Variants: graph topology (graph type parameter G), weight type (W)

Field	Type	Description
graph	SimpleGraph	The undirected graph G = (V, E)
weights	Vec<W>	Non-negative integer weight w(v) for each vertex v
max_components	usize	Upper bound K on the number of components
max_weight	W	Upper bound B on the total weight of each component

Size fields (getter methods): num_vertices() (= |V|), num_edges() (= |E|), max_components() (= K), max_weight() (= B).

Notes:

• This is a satisfaction (decision) problem: Metric = bool, implementing SatisfactionProblem.
• Weight type W should support non-negative integers (i32 or u32).
• Special case: when all weights equal 1, B controls the maximum component size.

Complexity

• Best known exact algorithm: General case requires exponential time. A brute-force approach enumerates all partitions and checks connectivity + weight constraints, giving O(K^n · poly(n)) time. Subset DP approaches yield O(3^n · poly(n)) for the partition step (Björklund, Husfeldt, Koivisto, "Set Partitioning via Inclusion-Exclusion", SIAM J. Computing, 2009).
• NP-completeness: NP-complete (Hadlock, 1974, as referenced in Garey & Johnson, 1979). Transformation from PARTITION INTO PATHS OF LENGTH 2. Also NP-complete via reduction from HAMILTONIAN CIRCUIT when K = |V| - 1 (spanning trees).
• Special cases:
  • Polynomial time if G is a tree (Hadlock, 1974, as referenced in Garey & Johnson).
  • Polynomial time if all weights equal 1 and B = 2 (Hadlock, 1974) — reduces to finding a perfect matching.
  • Remains NP-complete if all weights equal 1 and B is any fixed integer > 2 (Garey and Johnson).
• declare_variants! guidance: Use "3^num_vertices" as the complexity string for the default SimpleGraph variant. This reflects the O(3^n) subset DP bound. Example: declare_variants! { BoundedComponentSpanningForest, { SimpleGraph, i32 } => "3^num_vertices" }.
• References:
  • F. O. Hadlock (1974). "Minimum spanning forests of bounded trees." Proceedings of the 5th Southeastern Conference on Combinatorics, Graph Theory, and Computing, pp. 449–460. (Title as cited in Garey & Johnson; exact title unverified.)
  • A. Björklund, T. Husfeldt, M. Koivisto (2009). "Set Partitioning via Inclusion-Exclusion." SIAM Journal on Computing, 39(2), pp. 546–563.

Extra Remark

Full book text:

INSTANCE: Graph G = (V,E), weight w(v) ∈ Z⁺₀ for each v ∈ V, positive integers K ≤ |V| and B.
QUESTION: Can the vertices in V be partitioned into k ≤ K disjoint sets V₁, V₂, ..., Vₖ such that, for 1 ≤ i ≤ k, the subgraph of G induced by Vᵢ is connected and the sum of the weights of the vertices in Vᵢ 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].

How to solve

• It can be solved by (existing) bruteforce — enumerate all partitions of V into at most K groups, check connectivity and weight constraints.
• It can be solved by reducing to integer programming — binary variables x_{v,j} for vertex v in component j, with connectivity and weight constraints.
• Other: Subset DP over connected subsets; tree decomposition-based algorithms for bounded treewidth graphs.

Example Instance

Instance 1 (YES — valid partition exists):
Graph G with 8 vertices {0, 1, 2, 3, 4, 5, 6, 7}, edges: {0,1}, {1,2}, {2,3}, {3,4}, {4,5}, {5,6}, {6,7}, {0,7}, {1,5}, {2,6}

• Weights: w(0)=2, w(1)=3, w(2)=1, w(3)=2, w(4)=3, w(5)=1, w(6)=2, w(7)=1
• K = 3, B = 6
• Total weight = 15
• Partition: V_1 = {0, 1, 7} (connected via edges {0,1}, {0,7}; weight = 2+3+1 = 6 ≤ B)
  V_2 = {2, 3, 4} (connected via edges {2,3}, {3,4}; weight = 1+2+3 = 6 ≤ B)
  V_3 = {5, 6} (connected via edge {5,6}; weight = 1+2 = 3 ≤ B)
• 3 components ≤ K=3, all connected, all weights ≤ B=6
• Answer: YES

Instance 2 (NO — no valid partition):
Graph G with 6 vertices {0, 1, 2, 3, 4, 5}, edges: {0,1}, {1,2}, {3,4}, {4,5}

• Weights: all w(v) = 1
• K = 2, B = 2
• The graph has two connected components: {0,1,2} and {3,4,5}. Each must be partitioned into subsets of size ≤ 2 that induce connected subgraphs, using a total of at most K=2 components overall.
• Component {0,1,2} is a path 0-1-2. Connected subsets of size ≤ 2 are: {0}, {1}, {2}, {0,1}, {1,2}. To cover all 3 vertices requires at least 2 parts (e.g., {0,1} and {2}, or {0} and {1,2}).
• Component {3,4,5} is a path 3-4-5. Similarly requires at least 2 connected parts.
• Total parts needed ≥ 2 + 2 = 4 > K = 2.
• Answer: NO

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem not yet in reduction graph; concrete applications cited
Non-trivial	✅ Pass	Distinct feasibility constraints from all 24 existing problems
Correctness	⚠️ Warn	Hadlock 1974 paper not independently verified online; Garey & Johnson ND10 reference is correct
Well-written	⚠️ Warn	Example Instance 2 is confusingly written; minor notation issues

Overall: 2 passed, 0 failed, 2 warnings

---

Usefulness

Pass. The problem BoundedComponentSpanningForest does not exist in the current codebase (24 problems registered, none matching). The issue identifies concrete applications (political redistricting, balanced graph partitioning) and lists two associated reduction rules as future targets. The motivation section is substantive and explains why this problem matters in the reduction graph — it generalizes Hamiltonian circuit and connects to partition problems.

Non-trivial

Pass. This problem has genuinely distinct feasibility constraints from all existing problems in the codebase. The combination of (1) partitioning into at most K groups, (2) each group inducing a connected subgraph, and (3) each group having bounded total weight is not captured by any existing model. The closest existing problems are:

• BinPacking — partitions items by weight but has no graph connectivity constraint
• KColoring — partitions vertices with adjacency constraints but does not require connected components or weight bounds
• MinimumDominatingSet / MinimumVertexCover — select vertex subsets with coverage constraints, not partition into connected components

This is a distinct problem requiring new implementation.

Correctness

Warn. The primary reference is well-established:

• Garey & Johnson (1979), ND10 — This is the canonical reference for this problem. The problem definition in the issue matches the standard ND10 formulation exactly. ✅
• Hadlock (1974), "Minimum spanning forests of bounded trees" — The 5th Southeastern Conference on Combinatorics, Graph Theory, and Computing (Florida Atlantic University, Boca Raton, 1974) is confirmed to exist. However, the specific Hadlock paper could not be independently located in online databases — this is expected for a 1974 conference proceedings paper from the pre-digital era. The claims attributed to Hadlock (NP-completeness via transformation from Partition into Paths of Length 2, polynomial solvability on trees and for unit weights with B=2) are consistent with what Garey & Johnson report in their book. ⚠️ Cannot independently verify the exact paper title.

Complexity claims:

• O(K^n * poly(n)) brute force — correct, this is the naive enumeration of all K-colorings.
• O(3^n * poly(n)) via subset DP — reasonable. The standard subset convolution / inclusion-exclusion approach for partition-into-connected-subsets problems yields this bound (each vertex can be in subset A, subset B, or unassigned during enumeration). However, no specific paper or algorithm name is cited for this bound. A concrete citation would strengthen this claim.
• NP-completeness claims match Garey & Johnson. ✅

Well-written

Warn. The issue is generally well-structured and follows the template, but has several issues:

Strengths:

• All required template sections are present and substantive
• Mathematical definition is precise and matches the canonical formulation
• Variables section correctly identifies the K-ary domain
• Schema is reasonable with appropriate fields
• Solver methods are identified (brute-force, ILP, subset DP)

Issues to address:

1. Example Instance 2 is confusing. The NO instance starts by proposing K=2, B=3, then realizes that is actually feasible, then mid-paragraph revises to K=2, B=2. This self-correction makes the example hard to follow. It should be rewritten as a clean NO instance from the start without the false start.

2. Hadlock paper title may be inaccurate. The issue cites "Minimum spanning forests of bounded trees" — but the actual title could not be verified. Garey & Johnson's reference format typically uses abbreviated citations; the exact paper title should be confirmed if possible.

3. Complexity section lacks a concrete best-known algorithm citation. The O(3^n) subset DP claim is stated without citing a specific paper or algorithm. For the declare_variants! macro, a concrete complexity string with a specific citation is needed (per project conventions).

4. Symbol Z_0^+ is non-standard. The conventional notation for non-negative integers is Z+ or Z>=0. This is minor but should be consistent with standard notation.

5. The "Size Overhead" table is missing. While this is a Model issue (not a Rule issue), the Schema section would benefit from listing the getter methods that will be available (e.g., num_vertices(), num_edges(), num_components(), max_weight()), since reduction rules targeting this problem will need to reference them in overhead expressions.

Recommendations

• Rewrite Example Instance 2 as a clean NO instance without the mid-paragraph self-correction
• Search for a concrete citation for the O(3^n) subset DP approach (e.g., Bjorklund, Husfeldt, Koivisto "Set Partitioning via Inclusion-Exclusion" or similar)
• Verify the exact title of the Hadlock 1974 paper if possible, or cite it as "Hadlock (1974) as referenced in Garey & Johnson (1979)"
• Add getter method names to the Schema section for future reduction rule compatibility

[isPANN]

Updated.