# Complexity of $\oplus$ 3-REGULAR BIPARTITE PLANAR VERTEX COVER

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

• 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
• 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 '15 at 14:11