Given an undirected graph $G$. Each vertex has a weight 1.

We define shrinking an edge as merging and replacing 2 adjacent vertices $(A, B)$ with a new vertex $C$ such that all the vertices that were connected to $A$ or $B$ are now connected to $C$. Moreover the weight of the new vertex $C$ is sum of weight of $A$ and $B$.

Question: Determine if for a given graph $G$, we can merge vertices such that in the new Graph:

  1. Each vertex has a weight 2.
  2. The new graph is 2 color-able.

How do we approach this problem?


Your problem is exactly equivalent to the 2-colorable perfect matching problem: On input a graph, color the vertices of the graph with two colors such that each vertex has exactly one neighbor of the same color.

The 2-colorable perfect matching problem was introduced in "The complexity of satisfiability problems" by T. J. Schaefer and is NP-complete.

  • $\begingroup$ Thank you. If each vertex has a constraint that its degree is $>=2$ is the problem still NP Complete? $\endgroup$
    – Student
    May 28 '17 at 10:01
  • $\begingroup$ Sure. If any vertex has degree $0$ then the answer is trivially no, so we don't need to consider that case. If some vertex $v$ has degree $1$ then we can add two vertices $u_1$ and $u_2$ and three edges $(v, u_1)$, $(v, u_2)$, and $(u_1, u_2)$ without changing the answer to the problem. This works because every perfect matching in the resulting graph includes edge $(u_1, u_2)$. Notice that applying this transformation for every degree-$1$ vertex increases the minimum degree to $2$. $\endgroup$ May 28 '17 at 11:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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