<p>Such a cut exists if and only if the graph has an even number of spanning trees, which can be checked in polynomial time by using the matrix-tree theorem. See <a href="http://www.ics.uci.edu/~eppstein/pubs/Epp-TR-96-14.pdf">http://www.ics.uci.edu/~eppstein/pubs/Epp-TR-96-14.pdf</a></p>

CC BY-SA 3.0
2014-10-04T16:52:12.847Z
2014-10-04T16:52:12.847Z
David Eppstein
<p><em>Edit: As Sasho and Joe pointed out in comments, the reduction in revision 1 was incorrect.</em></p>

<p>Here is an observation which is too long for a comment.</p>

<p>The stated problem for a graph with <i>n</i>+1 vertices is equivalent to the problem of deciding whether a given <i>n</i>×<i>n</i> symmetric matrix whose entries are in GF(2) is singular or not.</p>

<p>Here is a reduction from the problem in question to the problem of deciding singularity of a symmetric matrix in GF(2).  Given a graph with <i>n</i>+1 vertices, label the vertices from 1 to <i>n</i>+1, and let <i>A</i> be the adjacency matrix ignoring vertex <i>n</i>+1, except that each diagonal entry <i>A</i><sub><i>ii</i></sub> is set to 1 if and only if the degree of the corresponding vertex i is odd.</p>

<p>Consider the one-to-one correspondence between the 2<sup><i>n</i></sup> partitions of <i>n</i>+1 vertices into two sets and the 2<sup><i>n</i></sup> vectors in GF(2)<sup><i>n</i></sup> defined by setting <i>x</i><sub><i>i</i></sub>=1 if and only if vertices <i>i</i> and <i>n</i>+1 belong to the opposite sets.  Then it is not hard to see that this partition is a solution to the problem in question if and only if the corresponding vector <i>x</i> is a solution of the linear equation <i>A</i><i>x</i>=0.  Clearly the trivial partition corresponds to the trivial solution <i>x</i>=0 of the linear equation.  This shows that the reduction above is a correct reduction.</p>

<p>The reduction in the other direction should be easy to see from the reduction above.</p>

CC BY-SA 3.0
2014-10-04T14:40:37.510Z
I must be missing something. Let $S$ be the side of the cut containing $n+1$, and $T$ the other side. If $i \in S$, $(Ax)_i = 0$ does imply that $i$ has an even number of neighbors in $T$. But if $i \in T$, then $(Ax)_i = 0$ means that the number of neighbors of $i$ in $T$ is odd if $i$ is a neighbor of $n+1$, and even otherwise. What am I missing?
Sasho Nikolov
CC BY-SA 3.0
2014-10-04T15:31:43.960Z
Hi Tsuyoshi, thanks for your response. It is really interesting to me that you came up with this procedure, since I had a reduction to almost exactly the same procedure on an entirely different set of equations. However, like Sasho, I am slightly confused by why this should work.
Joe Fitzsimons
CC BY-SA 3.0
2014-10-04T15:42:03.430Z
Basically, it is clear to me that, for such an $x$ and $A$, if $x_i = 0$ then this amounts to checking that $i$ has an even number of neighbours which are in the $1$ partition. However, if $x_i = 1$, this seems to imply that $i$ has an odd number of neighbours in the $1$ partition, and does not specify the number in the $0$ partition.
Joe Fitzsimons
CC BY-SA 3.0
2014-10-04T16:25:23.333Z
Sasho and Joe: You are right, the reduction was incorrect.  I am sorry, I made a mistake while trying to simplifying the reduction.  I hope I corrected the error in revision 2.
Tsuyoshi Ito
CC BY-SA 3.0
2014-10-04T16:47:53.930Z
Thanks for the revision. I see your reasoning now. Nice answer.
Joe Fitzsimons
CC BY-SA 3.0
2014-10-04T17:17:39.550Z
So in that case it would seem to be in NC2.
Joe Fitzsimons
CC BY-SA 3.0
2014-10-04T14:09:45.607Z
2014-10-04T16:22:46.767Z
2014-10-04T16:22:46.767Z
Tsuyoshi Ito
<p>Given a graph $G=(V,E)$, what is known about the classical computational complexity of finding a non-trivial cut which partitions the vertices into two sets $V_a$ and $V_b$ such that every vertex in $V_a$ has an even number of neighbours in $V_b$ and every vertex in $V_b$ has an even number of neighbours in $V_a$? In particular I am interested in the time and depth complexity of solving this problem, or the corresponding decision problem. </p>

<p>I realise that this may correspond to a well studied problem, and if so I would appreciate a pointer to the relevant literature. It seems closely related to a number of SAT problems, but I have not yet managed to find an exact correspondence.</p>

CC BY-SA 3.0
2014-10-04T11:24:24.790Z
I'm afraid that the problem is not well-defined.  First, the trivial partition (with either $V_a$ or $V_b$ being empty) is a trivial solution.  Even you require the cut to be nontrivial, it's still trivial to solve.  If the graph has an even-degree vertex, take it as $V_a$; otherwise, (every vertex has an odd degree), take any edge and let its two vertices to be $V_a$.  In short, for the decision problem, every instance is "YES."
Yixin Cao
CC BY-SA 3.0
2014-10-04T11:31:17.293Z
A possibly related problem is "Even Set" defined as follows. Input: A bipartite graph $G = (L,R,E)$. Task: Is there a set $X$ of k vertices from $R$, such that each vertex of $L$ has an even number of neighbors in $X$? See http://dx.doi.org/10.1109/18.641542.  This is NP-hard and W[1]-hard.
Yixin Cao
CC BY-SA 3.0
2014-10-04T12:06:41.350Z
@YixinCao Indeed you are correct. I misphrased my question. I am interested in non-trivial solutions when vertices in both sets are required to have an even number of neighbours in the other set.
Joe Fitzsimons
CC BY-SA 3.0
2014-10-04T17:12:37.387Z
@YixinCao: Are you sure that specific version of the even vertex set problem in NP-hard (it differs slightly form the version in the paper)?
Joe Fitzsimons
<cc.complexity-theory><graph-theory><graph-algorithms><circuit-complexity><time-complexity>
Complexity of finding even cuts for a graph
Joe Fitzsimons
# Complexity of finding even cuts for a graph

(Asked by: username_0 on 2014-10-04)

Given a graph $G=(V,E)$, what is known about the classical computational complexity of finding a non-trivial cut which partitions the vertices into two sets $V\_a$ and $V\_b$ such that every vertex in $V\_a$ has an even number of neighbours in $V\_b$ and every vertex in $V\_b$ has an even number of neighbours in $V\_a$? In particular I am interested in the time and depth complexity of solving this problem, or the corresponding decision problem.

I realise that this may correspond to a well studied problem, and if so I would appreciate a pointer to the relevant literature. It seems closely related to a number of SAT problems, but I have not yet managed to find an exact correspondence.

**Tags:** cc.complexity-theory, graph-theory, graph-algorithms, circuit-complexity, time-complexity

> **Comments:**
> **username_1**: I'm afraid that the problem is not well-defined.  First, the trivial partition (with either $V_a$ or $V_b$ being empty) is a trivial solution.  Even you require the cut to be nontrivial, it's still trivial to solve.  If the graph has an even-degree vertex, take it as $V_a$; otherwise, (every vertex has an odd degree), take any edge and let its two vertices to be $V_a$.  In short, for the decision problem, every instance is "YES."  
> **username_1**: A possibly related problem is "Even Set" defined as follows. Input: A bipartite graph $G = (L,R,E)$. Task: Is there a set $X$ of k vertices from $R$, such that each vertex of $L$ has an even number of neighbors in $X$? See http://dx.doi.org/10.1109/18.641542.  This is NP-hard and W[1]-hard.  
> **username_0**: @YixinCao Indeed you are correct. I misphrased my question. I am interested in non-trivial solutions when vertices in both sets are required to have an even number of neighbours in the other set.  
> **username_0**: @YixinCao: Are you sure that specific version of the even vertex set problem in NP-hard (it differs slightly form the version in the paper)?  

---

## 2 answers

### Answer by username_3 on 2014-10-04. Score: 6 | Accepted answer

*Edit: As Sasho and Joe pointed out in comments, the reduction in revision 1 was incorrect.*

Here is an observation which is too long for a comment.

The stated problem for a graph with *n*+1 vertices is equivalent to the problem of deciding whether a given *n*×*n* symmetric matrix whose entries are in GF(2) is singular or not.

Here is a reduction from the problem in question to the problem of deciding singularity of a symmetric matrix in GF(2). Given a graph with *n*+1 vertices, label the vertices from 1 to *n*+1, and let *A* be the adjacency matrix ignoring vertex *n*+1, except that each diagonal entry *A**ii* is set to 1 if and only if the degree of the corresponding vertex i is odd.

Consider the one-to-one correspondence between the 2*n* partitions of *n*+1 vertices into two sets and the 2*n* vectors in GF(2)*n* defined by setting *x**i*=1 if and only if vertices *i* and *n*+1 belong to the opposite sets. Then it is not hard to see that this partition is a solution to the problem in question if and only if the corresponding vector *x* is a solution of the linear equation *A**x*=0. Clearly the trivial partition corresponds to the trivial solution *x*=0 of the linear equation. This shows that the reduction above is a correct reduction.

The reduction in the other direction should be easy to see from the reduction above.

> **Comments:**
> **username_4**: I must be missing something. Let $S$ be the side of the cut containing $n+1$, and $T$ the other side. If $i \in S$, $(Ax)_i = 0$ does imply that $i$ has an even number of neighbors in $T$. But if $i \in T$, then $(Ax)_i = 0$ means that the number of neighbors of $i$ in $T$ is odd if $i$ is a neighbor of $n+1$, and even otherwise. What am I missing?  
> **username_0**: Hi Tsuyoshi, thanks for your response. It is really interesting to me that you came up with this procedure, since I had a reduction to almost exactly the same procedure on an entirely different set of equations. However, like Sasho, I am slightly confused by why this should work.  
> **username_0**: Basically, it is clear to me that, for such an $x$ and $A$, if $x_i = 0$ then this amounts to checking that $i$ has an even number of neighbours which are in the $1$ partition. However, if $x_i = 1$, this seems to imply that $i$ has an odd number of neighbours in the $1$ partition, and does not specify the number in the $0$ partition.  
> **username_3**: Sasho and Joe: You are right, the reduction was incorrect.  I am sorry, I made a mistake while trying to simplifying the reduction.  I hope I corrected the error in revision 2.  
> **username_0**: Thanks for the revision. I see your reasoning now. Nice answer.  
> **username_0**: So in that case it would seem to be in NC2.  

---

### Answer by username_2 on 2014-10-04. Score: 9

Such a cut exists if and only if the graph has an even number of spanning trees, which can be checked in polynomial time by using the matrix-tree theorem. See <http://www.ics.uci.edu/~eppstein/pubs/Epp-TR-96-14.pdf>


---

