<p>The problem is NP-complete. We'll make a series of reductions from max-cut to show this.</p>

<p><strong>Problem 0</strong> (your problem): Given a graph <span class="math-container">$G$</span>, does G have an induced subgraph with at least k vertices, such that all vertices have even degree within the subgraph?</p>

<p><strong>Problem 1</strong>: Given a graph <span class="math-container">$G$</span> and subset <span class="math-container">$A$</span> of vertices, does <span class="math-container">$G$</span> have an induced subgraph with at least <span class="math-container">$k$</span> vertices in <span class="math-container">$A$</span>, such that all vertices have even degree within the subgraph?</p>

<p><strong>Problem 2</strong>: Given a graph <span class="math-container">$G$</span> and subsets <span class="math-container">$A, B$</span> of vertices, does <span class="math-container">$G$</span> have an induced subgraph with at least <span class="math-container">$k$</span> vertices in <span class="math-container">$A$</span>, such that all vertices in <span class="math-container">$B$</span> have even degree within the subgraph?</p>

<p><strong>Max-cut</strong>: Given a graph <span class="math-container">$G$</span>, does there exist a cut <span class="math-container">$C \subset V$</span> of size <span class="math-container">$|\delta(C)|$</span> at least <span class="math-container">$k$</span>? (where <span class="math-container">$\delta(C)$</span> is the set of edges in <span class="math-container">$E$</span> with exactly one endpoint in <span class="math-container">$C$</span>)</p>

<p>We'll reduce max-cut to problem 2, problem 2 to problem 1, and finally problem 1 to problem 0, proving that your problem is NP-complete.</p>

<hr>

<p>First we reduce the max-cut problem to problem 2. Given graph <span class="math-container">$G = (V, E)$</span> and <span class="math-container">$k$</span>, we'll construct <span class="math-container">$G' = (V', E')$</span> and <span class="math-container">$A, B$</span> such that <span class="math-container">$G$</span> has a cut of size at least <span class="math-container">$k$</span> if and only if <span class="math-container">$G'$</span> has an induced subgraph with at least <span class="math-container">$k + |E|$</span> vertices in <span class="math-container">$A$</span>, where every vertex in <span class="math-container">$B$</span> has even degree.</p>

<p>For every <span class="math-container">$v_{i} \in V$</span> we'll have a node <span class="math-container">$v_{i}'$</span> in <span class="math-container">$V'$</span>. For every edge <span class="math-container">$e_{i} = (v_{x_{i}}, v_{y_{i}}) \in E$</span> we'll have nodes <span class="math-container">$e'_{i, 0}, e'_{i, 1}$</span> in <span class="math-container">$V'$</span>, and edges <span class="math-container">$(e'_{i, 0}, e'_{i, 1}), (e'_{i, 0}, v'_{x_{i}}), (e'_{i, 0}, v'_{y_{i}}), (e'_{i, 1}, v'_{x_{i}}), (e'_{i, 1}, v'_{y_{i}})$</span>. We'll set <span class="math-container">$A = B = \bigcup_{i = 1}^{|E|} \{e'_{i, 0}, e'_{i, 1}\}$</span>.</p>

<p><a href="https://i.sstatic.net/8yGyK.jpg" rel="noreferrer"><img src="https://i.sstatic.net/8yGyK.jpg" alt="visualisation of what is added for each edge in E"></a></p>

<p>Now, note that if we have exactly one of <span class="math-container">$v'_{x_{i}}$</span> or <span class="math-container">$v'_{y_{i}}$</span> in our subgraph, we can have both of <span class="math-container">$e'_{i, 0}$</span> and <span class="math-container">$e'_{i, 1}$</span>. However, due to the degree constraint, if we have both or neither of <span class="math-container">$v'_{x_{i}}, v'_{y_{i}}$</span>, we can have at most one of <span class="math-container">$e'_{i, 0}$</span> and <span class="math-container">$e'_{i, 1}$</span>.</p>

<p>Take a cut <span class="math-container">$C \subset V$</span> in <span class="math-container">$G$</span> of size <span class="math-container">$k = |\delta(C)|$</span>. We'll build <span class="math-container">$C' \subset V'$</span> s.t. <span class="math-container">$|C' \cap A| = |E| + k$</span>, and every vertex in <span class="math-container">$B$</span> has even degree in the subgraph induced on <span class="math-container">$C'$</span>. We set <span class="math-container">$v'_{i} \in C'$</span> iff <span class="math-container">$v_{i} \in C$</span>, <span class="math-container">$e'_{i, 0} \in C'$</span> for all <span class="math-container">$i$</span>, and <span class="math-container">$e'_{i, 1} \in C'$</span> for <span class="math-container">$e_{i} \in \delta(C)$</span>. This construction has the claimed properties.</p>

<p>Next take <span class="math-container">$C' \subset V'$</span> s.t. <span class="math-container">$|C' \cap A| = |E| + k$</span>, and and every vertex in <span class="math-container">$B$</span> has even degree in the subgraph induced on <span class="math-container">$C'$</span>. Then we'll build a cut <span class="math-container">$C \subset V$</span> of size at least <span class="math-container">$k$</span>. To do this, just set again <span class="math-container">$v_{i} \in C$</span> iff <span class="math-container">$v'_{i} \in C'$</span>. Now since <span class="math-container">$|C' \cap A| = |E| + k$</span>, there are at least <span class="math-container">$k$</span> edges <span class="math-container">$e_{i}$</span> s.t. both <span class="math-container">$e'_{i, 0}$</span> and <span class="math-container">$e'_{i, 1}$</span> are in <span class="math-container">$C'$</span>. But for those <span class="math-container">$i$</span> we have <span class="math-container">$e_{i} \in \delta(C)$</span>, hence <span class="math-container">$|\delta(C)| \geq k$</span> as desired.</p>

<hr>

<p>Next we reduce problem 2 to problem 1. Given graph <span class="math-container">$G = (V, E), A, B$</span> and <span class="math-container">$k$</span>, we'll construct <span class="math-container">$G' = (V', E')$</span> and <span class="math-container">$A'$</span> s.t. <span class="math-container">$G'$</span> has an induced subgraph with at least <span class="math-container">$2k$</span> vertices in <span class="math-container">$A'$</span> where every node has even degree in the induced subgraph if and only if <span class="math-container">$G$</span> has an induced subgraph with at least <span class="math-container">$k$</span> vertices in <span class="math-container">$A$</span> where every node in <span class="math-container">$B$</span> has even degree in the induced subgraph.</p>

<p>To build <span class="math-container">$G'$</span>, We'll make two copies of <span class="math-container">$G$</span>: for every node <span class="math-container">$v_{i} \in V$</span> we'll have nodes <span class="math-container">$v'_{i, 0}$</span> and <span class="math-container">$v'_{i, 1}$</span> in <span class="math-container">$G'$</span>, and for every edge <span class="math-container">$e_{i} = (v_{x_{i}}, v_{y_{i}})$</span> in <span class="math-container">$E$</span> we'll have edges <span class="math-container">$e'_{i, 0} = (v'_{x_{i}, 0}, v'_{y_{i}, 0})$</span> and <span class="math-container">$e'_{i, 1} = (v'_{x_{i}, 1}, v'_{y_{i}, 1})$</span> in <span class="math-container">$E'$</span>. Additionally, for every <span class="math-container">$v_{i} \in B^{c}$</span>, we'll add a new vertex <span class="math-container">$m'_{i}$</span>, and the edges <span class="math-container">$(v'_{i, 0}, m'_{i})$</span> and <span class="math-container">$(v'_{i, 1}, m'_{i})$</span>. We set <span class="math-container">$A' = \{v'_{i, 0}, v'_{i, 1} \mid v_{i} \in A\}$</span>.</p>

<p>Take a subgraph <span class="math-container">$C \subset V$</span> such that <span class="math-container">$|C \cap A| = k$</span> and vertices in <span class="math-container">$B$</span> have even degree in the graph induced on <span class="math-container">$C$</span>. We'll build <span class="math-container">$C'$</span> s.t. <span class="math-container">$|C' \cap A'| = 2k$</span> and every vertex has even degree in the graph induced on <span class="math-container">$C'$</span>. To do this, set <span class="math-container">$v'_{i, 0}, v'_{i, 1} \in C'$</span> if and only if <span class="math-container">$v_{i} \in C$</span>. Then, for <span class="math-container">$v_{i} \in B^{c}$</span> with odd degree in the graph induced on <span class="math-container">$C$</span>, we add <span class="math-container">$m'_{i}$</span> to <span class="math-container">$C'$</span>. Now every vertex has even degree in the graph induced on <span class="math-container">$C'$</span>, since vertices in <span class="math-container">$B$</span> 
have the same degree as in the graph induced on <span class="math-container">$C$</span> (hence even degree), we made vertices in <span class="math-container">$B^{c}$</span> have even degree, and since <span class="math-container">$C'$</span> is the same in both copies of the graph, every vertex <span class="math-container">$m'_{i}$</span> has degree <span class="math-container">$2$</span> or <span class="math-container">$0$</span>. Clearly <span class="math-container">$|C' \cap A| = 2k$</span>.</p>

<p>Now take any subgraph <span class="math-container">$C' \subset V'$</span> s.t. <span class="math-container">$|C' \cap A'| \geq 2k$</span>, and every vertex has even degree in the graph induced on <span class="math-container">$C'$</span>. We'll construct <span class="math-container">$C$</span> s.t. <span class="math-container">$|C \cap A| \geq k$</span>, and every vertex in <span class="math-container">$B$</span> has even degree in the graph induced on <span class="math-container">$C$</span>. To do this, we first build <span class="math-container">$C_{0}, C_{1}$</span>, where <span class="math-container">$v_{i} \in C_{0}$</span> iff <span class="math-container">$v'_{i, 0} \in C'$</span>, and <span class="math-container">$v_{i} \in C_{1}$</span> iff <span class="math-container">$v'_{i, 1} \in C'$</span>. Note that <span class="math-container">$|C_{0} \cap A| + |C_{1} \cap A| = |C' \cap A'| \geq 2k$</span>, hence WLOG <span class="math-container">$|C_{0} \cap A| \geq k$</span>, and we set <span class="math-container">$C = C_{0}$</span>. If some vertex <span class="math-container">$v_{i}$</span> in <span class="math-container">$B$</span> had odd degree in the graph induced on <span class="math-container">$C$</span>, then <span class="math-container">$v'_{i, 0}$</span> would have odd degree in the graph induced on <span class="math-container">$C'$</span>, hence <span class="math-container">$C$</span> has the claimed properties.</p>

<hr>

<p>The reduction of problem 1 to problem 0 is by far the easiest, and I won't write a detailed proof here. The idea is to add for every vertex <span class="math-container">$v_{i}$</span> in <span class="math-container">$A^{c}$</span> the vertex <span class="math-container">$v'_{i}$</span> and the edge <span class="math-container">$(v_{i}, v'_{i})$</span>, and finally subtract <span class="math-container">$|A^{c}|$</span> from <span class="math-container">$k$</span>. Now every maximal solution includes one of <span class="math-container">$v_{i}$</span> and <span class="math-container">$v'_{i}$</span>, but cannot include both, since then <span class="math-container">$v'_{i}$</span> would have odd degree, hence including <span class="math-container">$v_{i}$</span> no longer increases the size of the graph we're inducing on.</p>

CC BY-SA 4.0
2019-12-01T01:06:53.617Z
2019-12-01T01:06:53.617Z
Antti Röyskö
<p>What is the complexity of the following problem?</p>

<p><strong>Instance:</strong> Simple, undirected graph <span class="math-container">$G$</span>, and a positive integer <span class="math-container">$k$</span>.</p>

<p><strong>Question:</strong> Does <span class="math-container">$G$</span> have an induced subgraph on at least <span class="math-container">$k$</span> vertices, such that all vertices have even degree within the subgraph?</p>

<p><strong>Remark.</strong> It is similar to the problem known as Maximum Eulerian Subgraph, which is is NP-complete. However, in Maximum Eulerian Subgraph, beyond the even degrees, it is also required that the subgraph is connected. It is not clear whether dropping the connectivity requirement makes the task easier, or it still remains NP-complete.</p>

CC BY-SA 4.0
2019-11-19T01:47:16.747Z
Did you look at the reduction for Max Eulerian Subgraph?
Chandra Chekuri
CC BY-SA 4.0
2019-11-19T20:05:50.990Z
@ChandraChekuri The reduction uses the NP-complete problem Hamiltonian cycle in cubic graphs. If in an $n$-vertex cubic graph each edge is subdivided by a new vertex, then the resulting graph has a $\geq 2n$-vertex Eulerian subgraph if and only if the original graph has a Hamiltonian cycle. Without the connectivity of the Euclidean subgraph, however, the existence of the Hamiltonian cycle is not guaranteed. Therefore, the reduction makes essential use of connectivity.
Andras Farago
<graph-theory><graph-algorithms><np-complete>
Complexity of finding the largest induced subgraph with all even degrees
Andras Farago
# Complexity of finding the largest induced subgraph with all even degrees

(Asked by: username_0 on 2019-11-18)

What is the complexity of the following problem?

**Instance:** Simple, undirected graph $G$, and a positive integer $k$.

**Question:** Does $G$ have an induced subgraph on at least $k$ vertices, such that all vertices have even degree within the subgraph?

**Remark.** It is similar to the problem known as Maximum Eulerian Subgraph, which is is NP-complete. However, in Maximum Eulerian Subgraph, beyond the even degrees, it is also required that the subgraph is connected. It is not clear whether dropping the connectivity requirement makes the task easier, or it still remains NP-complete.

**Tags:** graph-theory, graph-algorithms, np-complete

> **Comments:**
> **username_1**: Did you look at the reduction for Max Eulerian Subgraph?  
> **username_0**: @ChandraChekuri The reduction uses the NP-complete problem Hamiltonian cycle in cubic graphs. If in an $n$-vertex cubic graph each edge is subdivided by a new vertex, then the resulting graph has a $\geq 2n$-vertex Eulerian subgraph if and only if the original graph has a Hamiltonian cycle. Without the connectivity of the Euclidean subgraph, however, the existence of the Hamiltonian cycle is not guaranteed. Therefore, the reduction makes essential use of connectivity.  

---

## 1 answers

### Answer by username_2 on 2019-12-01. Score: 5 | Accepted answer

The problem is NP-complete. We'll make a series of reductions from max-cut to show this.

**Problem 0** (your problem): Given a graph $G$, does G have an induced subgraph with at least k vertices, such that all vertices have even degree within the subgraph?

**Problem 1**: Given a graph $G$ and subset $A$ of vertices, does $G$ have an induced subgraph with at least $k$ vertices in $A$, such that all vertices have even degree within the subgraph?

**Problem 2**: Given a graph $G$ and subsets $A, B$ of vertices, does $G$ have an induced subgraph with at least $k$ vertices in $A$, such that all vertices in $B$ have even degree within the subgraph?

**Max-cut**: Given a graph $G$, does there exist a cut $C \subset V$ of size $|\delta(C)|$ at least $k$? (where $\delta(C)$ is the set of edges in $E$ with exactly one endpoint in $C$)

We'll reduce max-cut to problem 2, problem 2 to problem 1, and finally problem 1 to problem 0, proving that your problem is NP-complete.

---

First we reduce the max-cut problem to problem 2. Given graph $G = (V, E)$ and $k$, we'll construct $G' = (V', E')$ and $A, B$ such that $G$ has a cut of size at least $k$ if and only if $G'$ has an induced subgraph with at least $k + |E|$ vertices in $A$, where every vertex in $B$ has even degree.

For every $v\_{i} \in V$ we'll have a node $v\_{i}'$ in $V'$. For every edge $e\_{i} = (v\_{x\_{i}}, v\_{y\_{i}}) \in E$ we'll have nodes $e'\_{i, 0}, e'\_{i, 1}$ in $V'$, and edges $(e'\_{i, 0}, e'\_{i, 1}), (e'\_{i, 0}, v'\_{x\_{i}}), (e'\_{i, 0}, v'\_{y\_{i}}), (e'\_{i, 1}, v'\_{x\_{i}}), (e'\_{i, 1}, v'\_{y\_{i}})$. We'll set $A = B = \bigcup\_{i = 1}^{|E|} \{e'\_{i, 0}, e'\_{i, 1}\}$.

[![visualisation of what is added for each edge in E](https://i.sstatic.net/8yGyK.jpg)](https://i.sstatic.net/8yGyK.jpg)

Now, note that if we have exactly one of $v'\_{x\_{i}}$ or $v'\_{y\_{i}}$ in our subgraph, we can have both of $e'\_{i, 0}$ and $e'\_{i, 1}$. However, due to the degree constraint, if we have both or neither of $v'\_{x\_{i}}, v'\_{y\_{i}}$, we can have at most one of $e'\_{i, 0}$ and $e'\_{i, 1}$.

Take a cut $C \subset V$ in $G$ of size $k = |\delta(C)|$. We'll build $C' \subset V'$ s.t. $|C' \cap A| = |E| + k$, and every vertex in $B$ has even degree in the subgraph induced on $C'$. We set $v'\_{i} \in C'$ iff $v\_{i} \in C$, $e'\_{i, 0} \in C'$ for all $i$, and $e'\_{i, 1} \in C'$ for $e\_{i} \in \delta(C)$. This construction has the claimed properties.

Next take $C' \subset V'$ s.t. $|C' \cap A| = |E| + k$, and and every vertex in $B$ has even degree in the subgraph induced on $C'$. Then we'll build a cut $C \subset V$ of size at least $k$. To do this, just set again $v\_{i} \in C$ iff $v'\_{i} \in C'$. Now since $|C' \cap A| = |E| + k$, there are at least $k$ edges $e\_{i}$ s.t. both $e'\_{i, 0}$ and $e'\_{i, 1}$ are in $C'$. But for those $i$ we have $e\_{i} \in \delta(C)$, hence $|\delta(C)| \geq k$ as desired.

---

Next we reduce problem 2 to problem 1. Given graph $G = (V, E), A, B$ and $k$, we'll construct $G' = (V', E')$ and $A'$ s.t. $G'$ has an induced subgraph with at least $2k$ vertices in $A'$ where every node has even degree in the induced subgraph if and only if $G$ has an induced subgraph with at least $k$ vertices in $A$ where every node in $B$ has even degree in the induced subgraph.

To build $G'$, We'll make two copies of $G$: for every node $v\_{i} \in V$ we'll have nodes $v'\_{i, 0}$ and $v'\_{i, 1}$ in $G'$, and for every edge $e\_{i} = (v\_{x\_{i}}, v\_{y\_{i}})$ in $E$ we'll have edges $e'\_{i, 0} = (v'\_{x\_{i}, 0}, v'\_{y\_{i}, 0})$ and $e'\_{i, 1} = (v'\_{x\_{i}, 1}, v'\_{y\_{i}, 1})$ in $E'$. Additionally, for every $v\_{i} \in B^{c}$, we'll add a new vertex $m'\_{i}$, and the edges $(v'\_{i, 0}, m'\_{i})$ and $(v'\_{i, 1}, m'\_{i})$. We set $A' = \{v'\_{i, 0}, v'\_{i, 1} \mid v\_{i} \in A\}$.

Take a subgraph $C \subset V$ such that $|C \cap A| = k$ and vertices in $B$ have even degree in the graph induced on $C$. We'll build $C'$ s.t. $|C' \cap A'| = 2k$ and every vertex has even degree in the graph induced on $C'$. To do this, set $v'\_{i, 0}, v'\_{i, 1} \in C'$ if and only if $v\_{i} \in C$. Then, for $v\_{i} \in B^{c}$ with odd degree in the graph induced on $C$, we add $m'\_{i}$ to $C'$. Now every vertex has even degree in the graph induced on $C'$, since vertices in $B$
have the same degree as in the graph induced on $C$ (hence even degree), we made vertices in $B^{c}$ have even degree, and since $C'$ is the same in both copies of the graph, every vertex $m'\_{i}$ has degree $2$ or $0$. Clearly $|C' \cap A| = 2k$.

Now take any subgraph $C' \subset V'$ s.t. $|C' \cap A'| \geq 2k$, and every vertex has even degree in the graph induced on $C'$. We'll construct $C$ s.t. $|C \cap A| \geq k$, and every vertex in $B$ has even degree in the graph induced on $C$. To do this, we first build $C\_{0}, C\_{1}$, where $v\_{i} \in C\_{0}$ iff $v'\_{i, 0} \in C'$, and $v\_{i} \in C\_{1}$ iff $v'\_{i, 1} \in C'$. Note that $|C\_{0} \cap A| + |C\_{1} \cap A| = |C' \cap A'| \geq 2k$, hence WLOG $|C\_{0} \cap A| \geq k$, and we set $C = C\_{0}$. If some vertex $v\_{i}$ in $B$ had odd degree in the graph induced on $C$, then $v'\_{i, 0}$ would have odd degree in the graph induced on $C'$, hence $C$ has the claimed properties.

---

The reduction of problem 1 to problem 0 is by far the easiest, and I won't write a detailed proof here. The idea is to add for every vertex $v\_{i}$ in $A^{c}$ the vertex $v'\_{i}$ and the edge $(v\_{i}, v'\_{i})$, and finally subtract $|A^{c}|$ from $k$. Now every maximal solution includes one of $v\_{i}$ and $v'\_{i}$, but cannot include both, since then $v'\_{i}$ would have odd degree, hence including $v\_{i}$ no longer increases the size of the graph we're inducing on.


---

