7
$\begingroup$

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

Improve this question
$\endgroup$
5
  • $\begingroup$ 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? $\endgroup$
    – Tsuyoshi Ito
    Jan 20, 2013 at 23:39
  • $\begingroup$ @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]". $\endgroup$
    – Giorgio Camerani
    Jan 25, 2013 at 9:02
  • $\begingroup$ 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. $\endgroup$
    – Tsuyoshi Ito
    Jan 25, 2013 at 9:18
  • $\begingroup$ @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. $\endgroup$
    – Giorgio Camerani
    Jan 25, 2013 at 13:11
  • $\begingroup$ 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. $\endgroup$
    – Maciej1983
    Aug 25, 2015 at 14:11

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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