[Rule] GRAPH 3-COLORABILITY to PARTITION INTO FORESTS

[isPANN]

Source: GRAPH 3-COLORABILITY
Target: PARTITION INTO FORESTS
Motivation: Establishes NP-completeness of PARTITION INTO FORESTS (vertex arboricity decision problem) by showing that any proper 3-coloring of a graph is also a valid partition into 3 forests, and conversely, when the graph is dense enough the only way to partition vertices into few acyclic induced subgraphs is via a proper coloring.

Reference: Garey & Johnson, Computers and Intractability, A1.1 GT14

GJ Source Entry

[GT14] PARTITION INTO FORESTS
INSTANCE: Graph G = (V,E), positive integer K ≤ |V|.
QUESTION: Can the vertices of G be partitioned into k ≤ K disjoint sets V_1, V_2, . . . , V_k such that, for 1 ≤ i ≤ k, the subgraph induced by V_i contains no circuits?
Reference: [Garey and Johnson, ——]. Transformation from GRAPH 3-COLORABILITY.

Reduction Algorithm

Given an instance G = (V, E) of GRAPH 3-COLORABILITY, construct the following instance of PARTITION INTO FORESTS:

1. Graph construction: Build a new graph G' = (V', E') as follows. Start with the original graph G. For each edge {u, v} in E, add a new "edge gadget" vertex w_{uv} and connect it to both u and v, forming a triangle {u, v, w_{uv}}. This ensures that u and v cannot be in the same partition class (since any induced subgraph containing both endpoints of a triangle edge plus the apex vertex would contain a cycle — specifically the triangle itself).

   Formally:

   • V' = V union {w_{uv} : {u,v} in E}. So |V'| = |V| + |E| = n + m.
   • E' = E union {{u, w_{uv}} : {u,v} in E} union {{v, w_{uv}} : {u,v} in E}. So |E'| = |E| + 2|E| = 3m.

2. Bound: Set K = 3.

Correctness:

• Forward (3-coloring -> partition into 3 forests): Given a proper 3-coloring c: V -> {0,1,2} of G, assign each gadget vertex w_{uv} to any color class different from both c(u) and c(v) (possible since c(u) != c(v) and there are 3 classes). Each color class induces an independent set on the original vertices V (since c is a proper coloring). Each gadget vertex w_{uv} is adjacent to at most one vertex in its own class. The induced subgraph on each class is therefore a forest (a collection of stars with gadget vertices as potential leaves).

• Backward (partition into 3 forests -> 3-coloring): Given a partition V'_0, V'_1, V'2 of V' into 3 acyclic induced subgraphs, consider any edge {u,v} in E. The triangle {u, v, w{uv}} means all three vertices must be in different classes (if two were in the same class, say u and v in V'_i, then the induced subgraph G'[V'i] would contain the edge {u,v}, and w{uv} must be in some V'j. If j = i, we get a triangle = cycle, contradiction. If j != i, we still have u and v in the same class with edge {u,v} between them. This is allowed for a forest only if it doesn't create a cycle. However, consider the broader structure: for any triangle, at most one edge can appear within a single acyclic partition class.) In fact, since each original edge {u,v} is part of a triangle with w{uv}, and a triangle is a 3-cycle, no two vertices of any triangle can be in the same class (each class must be acyclic, and two triangle vertices in the same class would leave the third forced to create a cycle with the remaining two edges). Thus the restriction of the partition to V gives a proper 3-coloring.

Alternative (simpler) reduction:
A proper 3-coloring is trivially a partition into 3 independent sets. Each independent set is trivially a forest (no edges at all). So the identity reduction G' = G, K = 3 works for the direction "3-colorable implies partitionable into 3 forests." The reverse does not hold in general (a forest partition allows edges within classes). The gadget construction above forces the reverse direction.

Size Overhead

Target metric (code name)	Polynomial (using symbols above)
num_vertices	num_vertices + num_edges
num_edges	3 * num_edges
num_forests	3

Derivation:

• Vertices: n original + m gadget vertices = n + m
• Edges: m original edges + 2m gadget edges = 3m
• K = 3 (fixed constant)

Validation Method

• Closed-loop test: construct a graph G; apply the reduction to get a PartitionIntoForests instance (G', K=3); solve G' with BruteForce; verify the answer matches whether G is 3-colorable.
• Verify vertex count: |V'| = |V| + |E|.
• Verify edge count: |E'| = 3|E|.
• Test with K_4 (not 3-colorable, partition should fail) and a bipartite graph (always 2-colorable hence 3-colorable, partition should succeed).

Example

Source instance (Graph3Colorability):
Graph G with 4 vertices {0, 1, 2, 3} and 4 edges:

• Edges: {0,1}, {1,2}, {2,3}, {3,0} (the 4-cycle C_4)
• G is 3-colorable: c(0)=0, c(1)=1, c(2)=0, c(3)=1 (in fact 2-colorable)

Constructed target instance (PartitionIntoForests):

• Add 4 gadget vertices: w_{01}=4, w_{12}=5, w_{23}=6, w_{30}=7
• V' = {0,1,2,3,4,5,6,7}, |V'| = 8
• E' = original 4 edges + 8 gadget edges:
  {0,1}, {1,2}, {2,3}, {3,0}, {0,4}, {1,4}, {1,5}, {2,5}, {2,6}, {3,6}, {3,7}, {0,7}
• |E'| = 12 = 3 * 4
• K = 3

Solution mapping:

• 3-coloring: c(0)=0, c(1)=1, c(2)=0, c(3)=1
• Gadget assignments: w_{01}=4 -> class 2, w_{12}=5 -> class 2, w_{23}=6 -> class 2, w_{30}=7 -> class 2
• Partition: V'_0 = {0, 2}, V'_1 = {1, 3}, V'_2 = {4, 5, 6, 7}
  • G'[V'_0] = edges between {0,2}? No edge {0,2}. So G'[V'_0] has no edges -> forest.
  • G'[V'_1] = edges between {1,3}? No edge {1,3}. So G'[V'_1] has no edges -> forest.
  • G'[V'_2] = edges among {4,5,6,7}? No original or gadget edges connect gadget vertices to each other -> forest (isolated vertices).
• Answer: YES

References

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