<p>Ok, according to the paper <a href="http://people.seas.harvard.edu/~valiant/focs06.pdf" rel="nofollow">Accidental algorithms</a> by Valiant, the  problem ⊕Pl-3/2Bip-Mon-2CNF is ⊕P-complete. So ⊕ 3-REGULAR PLANAR VERTEX COVER would also have to be ⊕P-complete. So it's not in P (unless P = ⊕P-complete).
But I still don't know if ⊕ 3-REGULAR BIPARTITE PLANAR VERTEX COVER is ⊕P-complete.</p>

CC BY-SA 3.0
2015-08-27T06:58:31.590Z
2015-08-31T11:23:28.483Z
2015-08-31T11:23:28.483Z
Maciej1983
<p>The $\oplus$3-REGULAR BIPARTITE PLANAR VERTEX COVER problem consists in computing the parity of the number of vertex covers of a 3-regular bipartite planar graph.</p>

<blockquote>
  <p><strong>Question</strong></p>
  
  <ol>
  <li><p>Which is the complexity of such problem? Is it $\oplus$P-hard, or is it in P?</p></li>
  <li><p>What if we remove the planarity restriction (i.e. $\oplus$3-REGULAR BIPARTITE VERTEX COVER)?</p></li>
  </ol>
</blockquote>

<p>The closest I was able to find is that $\oplus$3/2 BIPARTITE PLANAR VERTEX COVER is $\oplus$P-complete (see Theorem 2.2 in <a href="http://people.seas.harvard.edu/~valiant/focs06.pdf">this paper</a>).</p>

CC BY-SA 3.0
2013-01-20T23:39:27.960Z
Right now, I do not have the access to the paper by Xia and Zhao which Colin McQuillan and András Salamon cited in [this answer](http://cstheory.stackexchange.com/questions/5563/trees-complexity-of-counting-the-number-of-vertex-covers/5567#5567) to one of your previous questions, but it seems very relevant.  Can you explain why it does not answer this question?
Tsuyoshi Ito
CC BY-SA 3.0
2013-01-25T09:02:42.550Z
@TsuyoshiIto: I know that paper. However, such paper is about the #P-hardness of counting vertex covers on 3-regular bipartite planar graphs. Here I'm interested in computing just the parity of the number of vertex covers. It is not obvious that counting them being #P-hard implies computing their parity being $\oplus$P-hard. For instance, see http://pages.cs.wisc.edu/~hguo/Papers/ParityHP.pdf: in the very first lines of the introduction they say _"...including graph matchings and some coloring problems, for which the parity
problem is in P but exact counting is #P-complete [Val10]"_.
Giorgio Camerani
CC BY-SA 3.0
2013-01-25T09:18:14.113Z
Of course #P-hardness of counting does not automatically imply ⊕P-hardness of deciding the parity.  What I am wondering is whether the proof of the #P-hardness of #3-regular bipartite planar vertex cover by Xia and Zhao also shows the ⊕P-hardness of ⊕3-regular bipartite planar vertex cover.  I cannot check whether it does or not because I (still) do not have access to the paper, but I assume that you have read their proof.
Tsuyoshi Ito
CC BY-SA 3.0
2013-01-25T13:11:35.533Z
@TsuyoshiIto: Your assumption is flawed (unfortunately for me). As I do not have access to their paper (neither now nor previously), I did not read it (although I would have liked to). I'm only aware of the title and the abstract.
Giorgio Camerani
CC BY-SA 3.0
2015-08-25T14:11:21.730Z
Unfortunalety old subject.
This problem is very interesting and I'm also looking for answer on this question.
For general graphs (probably even for 5-regular graphs) problem parity vertex cover is as hard as breaking RSA, factorization and many other NP-hard problems. I don't know if this NP-hard problems can be transformed in poly time to ⊕ 3-REGULAR BIPARTITE PLANAR VERTEX COVER, but it is still an interesting problem.
Maciej1983
<cc.complexity-theory><graph-theory><complexity-classes><counting-complexity>
Complexity of $\oplus$ 3-REGULAR BIPARTITE PLANAR VERTEX COVER
Giorgio Camerani
# Complexity of $\oplus$ 3-REGULAR BIPARTITE PLANAR VERTEX COVER

(Asked by: username_0 on 2013-01-15)

The $\oplus$3-REGULAR BIPARTITE PLANAR VERTEX COVER problem consists in computing the parity of the number of vertex covers of a 3-regular bipartite planar graph.

> **Question**
>
> 1. Which is the complexity of such problem? Is it $\oplus$P-hard, or is it in P?
> 2. What if we remove the planarity restriction (i.e. $\oplus$3-REGULAR BIPARTITE VERTEX COVER)?

The closest I was able to find is that $\oplus$3/2 BIPARTITE PLANAR VERTEX COVER is $\oplus$P-complete (see Theorem 2.2 in [this paper](http://people.seas.harvard.edu/~valiant/focs06.pdf)).

**Tags:** cc.complexity-theory, graph-theory, complexity-classes, counting-complexity

> **Comments:**
> **username_1**: Right now, I do not have the access to the paper by Xia and Zhao which Colin McQuillan and András Salamon cited in [this answer](http://cstheory.stackexchange.com/questions/5563/trees-complexity-of-counting-the-number-of-vertex-covers/5567#5567) to one of your previous questions, but it seems very relevant.  Can you explain why it does not answer this question?  
> **username_0**: @TsuyoshiIto: I know that paper. However, such paper is about the #P-hardness of counting vertex covers on 3-regular bipartite planar graphs. Here I'm interested in computing just the parity of the number of vertex covers. It is not obvious that counting them being #P-hard implies computing their parity being $\oplus$P-hard. For instance, see http://pages.cs.wisc.edu/~hguo/Papers/ParityHP.pdf: in the very first lines of the introduction they say _"...including graph matchings and some coloring problems, for which the parity problem is in P but exact counting is #P-complete [Val10]"_.  
> **username_1**: Of course #P-hardness of counting does not automatically imply ⊕P-hardness of deciding the parity.  What I am wondering is whether the proof of the #P-hardness of #3-regular bipartite planar vertex cover by Xia and Zhao also shows the ⊕P-hardness of ⊕3-regular bipartite planar vertex cover.  I cannot check whether it does or not because I (still) do not have access to the paper, but I assume that you have read their proof.  
> **username_0**: @TsuyoshiIto: Your assumption is flawed (unfortunately for me). As I do not have access to their paper (neither now nor previously), I did not read it (although I would have liked to). I'm only aware of the title and the abstract.  
> **username_2**: Unfortunalety old subject. This problem is very interesting and I'm also looking for answer on this question. For general graphs (probably even for 5-regular graphs) problem parity vertex cover is as hard as breaking RSA, factorization and many other NP-hard problems. I don't know if this NP-hard problems can be transformed in poly time to ⊕ 3-REGULAR BIPARTITE PLANAR VERTEX COVER, but it is still an interesting problem.  

---

## 1 answers

### Answer by username_2 on 2015-08-27. Score: 1

Ok, according to the paper [Accidental algorithms](http://people.seas.harvard.edu/~valiant/focs06.pdf) by Valiant, the problem ⊕Pl-3/2Bip-Mon-2CNF is ⊕P-complete. So ⊕ 3-REGULAR PLANAR VERTEX COVER would also have to be ⊕P-complete. So it's not in P (unless P = ⊕P-complete).
But I still don't know if ⊕ 3-REGULAR BIPARTITE PLANAR VERTEX COVER is ⊕P-complete.


---

