# Complexity of finding even cuts for a graph

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.

• 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 Oct 4 '14 at 11:24
• 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 dx.doi.org/10.1109/18.641542. This is NP-hard and W-hard. – Yixin Cao Oct 4 '14 at 11:31
• @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 Oct 4 '14 at 12:06
• @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 Oct 4 '14 at 17:12

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 Aii 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 2n partitions of n+1 vertices into two sets and the 2n vectors in GF(2)n defined by setting xi=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 Ax=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.

• 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 Oct 4 '14 at 14:40
• 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 Oct 4 '14 at 15:31
• 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 Oct 4 '14 at 15:42
• 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 Oct 4 '14 at 16:25
• So in that case it would seem to be in NC2. – Joe Fitzsimons Oct 4 '14 at 17:17

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