Partition into Forests

Input

Graph $G = (V, E)$, positive integer $K \leq |V|$.

Question

Can the vertices of $G$ be partitioned into $k \leq K$ disjoint sets $V_1, V_2, \dots, V_k$ such that, for $1 \leq i \leq k$, the subgraph induced by $V_i$ contains no circuits?

Classes

• NP-complete

Proofs

NP-complete

Transformation from [problem:graph-3-colorability] (Garey & Johnson, 1979).

Reducible from

• [graph-3-colorability]

References

• Garey, M. R., & Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co.