6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Did you look at the reduction for Max Eulerian Subgraph? $\endgroup$ – Chandra Chekuri Nov 19 at 1:47
  • $\begingroup$ @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. $\endgroup$ – Andras Farago Nov 19 at 20:05
4
$\begingroup$

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

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.

$\endgroup$

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.