6
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ 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." $\endgroup$
    – Yixin Cao
    Oct 4, 2014 at 11:24
  • 2
    $\begingroup$ 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[1]-hard. $\endgroup$
    – Yixin Cao
    Oct 4, 2014 at 11:31
  • $\begingroup$ @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. $\endgroup$ Oct 4, 2014 at 12:06
  • $\begingroup$ @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)? $\endgroup$ Oct 4, 2014 at 17:12

2 Answers 2

6
$\begingroup$

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.

$\endgroup$
6
  • 1
    $\begingroup$ 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? $\endgroup$ Oct 4, 2014 at 14:40
  • $\begingroup$ 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. $\endgroup$ Oct 4, 2014 at 15:31
  • 1
    $\begingroup$ 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. $\endgroup$ Oct 4, 2014 at 15:42
  • $\begingroup$ 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. $\endgroup$ Oct 4, 2014 at 16:25
  • 1
    $\begingroup$ So in that case it would seem to be in NC2. $\endgroup$ Oct 4, 2014 at 17:17
9
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.