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$
  • 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 '14 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 '14 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$ – Joe Fitzsimons Oct 4 '14 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$ – Joe Fitzsimons Oct 4 '14 at 17:12
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$
  • 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$ – Sasho Nikolov Oct 4 '14 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$ – Joe Fitzsimons Oct 4 '14 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$ – Joe Fitzsimons Oct 4 '14 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$ – Tsuyoshi Ito Oct 4 '14 at 16:25
  • 1
    $\begingroup$ So in that case it would seem to be in NC2. $\endgroup$ – Joe Fitzsimons Oct 4 '14 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, privacy policy and cookie policy

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