Sign up ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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.


  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).

share|cite|improve this question
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 to one of your previous questions, but it seems very relevant. Can you explain why it does not answer this question? – Tsuyoshi Ito Jan 20 '13 at 23:39
@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 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 Jan 25 '13 at 9:02
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 Jan 25 '13 at 9:18
@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 Jan 25 '13 at 13:11
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 Aug 25 at 14:11

1 Answer 1

Ok, according to the paper Accidental algorithms 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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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