0
$\begingroup$

The partition a graph into forests problem is defined as:

Given a Graph $G=(V,A)$, and a positive integer $K \le |V|$, can the vertices $V$ be partitioned into disjoint sets $V_1$, ..., $V_k$, $k \le K$, such that, for $1 \le i \le k$, the subgraph induced by $V_i$ contains no circuits?

I am trying to prove it is NP-Complete the following way:

Given an instance of the clique problem consisting of a graph $G'=(V', A')$ and a number $m$, where $m$ is odd, I will build an instance for my problem in the following way: $G=G'$, and $k = \frac{m-1}{2}$. If there is a clique with size at least $m$ in $G$, then there will be no partition of the vertices $V$ into $k$ disjoint sets such that the subgraph induced by each $V_i$ contains no circuits. And if there is no partition of the vertices $V$ into $k$ disjoint sets such that the subgraph induced by each $V_i$ contains no circuits, then there will be a clique of size at least $m$ in $G'$.

Is this proof correct?

If not, how can I prove that the partition a graph into forests problem is NP-Complete?

$\endgroup$
2
$\begingroup$

First, let me address what is wrong with your proof. The general idea you give for how to prove your reduction correct seems reasonable. The problem is that your reduction is not actually correct. In particular, the statement "if there is no partition of the vertices $V$ into $k$ disjoint sets such that the subgraph induced by each $V_i$ contains no circuits, then there will be a clique of size at least $m$ in $G′$" is false. Consider the following counterexample:

graph counterexample

This graph has no 5-cliques, but also cannot be partitioned into 2 forests.

Reduction alternative

You can instead reduce from graph 3-coloring. Given a graph $G = (V, E)$, you can modify this graph by adding three new vertices $u_1, u_2, u_3$ and adding every possible edge with any of these vertices as an endpoint. Let $G'$ be this new graph. Then we claim that $G$ is 3-colorable if and only if $G'$ can be partitioned into 3 forests.

First direction:

Suppose $G$ is 3-colorable. Let $A$, $B$, and $C$ be the sets of vertices in $G$ with each of the three colors. Let $A' = A \cup \{u_1\}$, $B' = B \cup \{u_2\}$, and $C' = C \cup \{u_3\}$. Notice that by the properties of a 3-coloring, no two vertices in $A$ are adjacent. Therefore the only edges induced by $A'$ are of the form $(u_1, v)$ with $v \in V$. Clearly, the graph induced by $A'$ has no cycles. The same logic applies to show that $B'$ and $C'$ also induce forests. Thus, $A'$, $B'$, and $C'$ is a partition of $G'$ into three forests.

Second direction:

Now suppose $G'$ can be partitioned into three forests. Since $u_1, u_2, u_3, u_1$ is a cycle, the three vertices $u_1, u_2, u_3$ cannot all be in the same part of the partition. Then there are two cases.

Case 1: each vertex $u_1, u_2, u_3$ is in a different part of the partition. Then consider any two vertices $v_1, v_2$ from the same part of $G'$ other than $u_1, u_2, u_3$. If $(v_1, v_2)$ were an edge, then there would be a cycle $u_i, v_1, v_2, u_i$ in the part containing $v_1$ and $v_2$. Since that is not the case, we see that no two adjacent vertices of $G$ are in the same part of the partition. In other words, the partition of $G'$ directly induces a 3-coloring of $G$.

Case 2: some two vertices among $u_1, u_2, u_3$ are in the same part. WLOG, suppose $u_1$ and $u_2$ are in the same part of the partition, call it $A$. Let the part of the partition containing $u_3$ be $B$ and let the final part be $C$. Note that $A$ contains no vertices from $G$ since if any $v \in V$ were in $A$ then the cycle $v, u_1, u_2, v$ would be present in one of the parts. Thus, every vertex from $G$ is either in $B$ or in $C$. Since $C$ induces a forest, it is possible to 2-color the vertices in $C$ (such that no two vertices of the same color are adjacent). If we then color the vertices of $B$ with a third color, we will have an assignment of three colors to the vertices of $G$. We already know that two of those colors have no adjacent monochromatic pairs of vertices. Using the same logic as in case 1, we can also conclude that $B$ contains no two adjacent vertices in $G$, and therefore that the third color also has no adjacent monochromatic pairs of vertices. We can conclude then that the described coloring is a valid 3-coloring of $G$.

$\endgroup$
  • $\begingroup$ Thanks for the proof. I realized the statement was wrong a few hours after my post. I proved it was wrong the following way: To prove the statement is correct, it would be sufficient to prove the contrapositive. But by Turán's theorem, if I have a graph without a clique of size $m$, I can create a $K_m−free$ graph with $m-1$ sets, each set having any amount of vertices, where each pair of vertices has an edge between them if they are in different sets. Using this, I created a graph that can not be partitioned into $2$ forests. $\endgroup$ – M. Almeida Jun 22 '17 at 12:31

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.