<p>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.</p>

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

CC BY-SA 3.0
2017-05-28T10:01:01.997Z
Thank you. If each vertex has a constraint that its degree is $>=2$ is the problem still NP Complete?
Student
CC BY-SA 3.0
2017-05-28T11:27:12.957Z
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$.
Mikhail Rudoy
CC BY-SA 3.0
2017-05-28T08:25:53.493Z
2017-05-28T08:25:53.493Z
Mikhail Rudoy
<p>Given an undirected graph $G$. Each vertex has a weight 1.</p>

<p>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$.</p>

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

<ol>
<li>Each vertex has a weight 2.</li>
<li>The new graph is 2 color-able.</li>
</ol>

<p>How do we approach this problem?</p>

<cc.complexity-theory><ds.algorithms>
Merging Graph Edges to form a 2 color-able Graph (with weight constraints)?
Student
# Merging Graph Edges to form a 2 color-able Graph (with weight constraints)?

(Asked by: username_0 on 2017-05-28)

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?

**Tags:** cc.complexity-theory, ds.algorithms

---

## 1 answers

### Answer by username_1 on 2017-05-28. Score: 7

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.

> **Comments:**
> **username_0**: Thank you. If each vertex has a constraint that its degree is $>=2$ is the problem still NP Complete?  
> **username_1**: 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$.  

---

