Take the 2-minute tour ×
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|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 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 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

Your Answer


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

Browse other questions tagged or ask your own question.