Let $G=(V,E)$ be a graph. Let $\Delta_k$ be the quantity defined in this question. Let $\mathcal{C}$ be the set of vertex covers of $G$. The following holds:

$$ |\mathcal{C}| = 2^{|V|} - \sum_{k = 2}^{|V|} \Delta_k \cdot 2^{|V|-k} $$

Let us focus on $\Delta_{|V|}$.


How hard is to compute $\Delta_{|V|}$?


The quantity $$\Delta_{|V|}\ \ mod\ \ 2$$ is the parity of the number of vertex covers of $G$. If such quantity is $0$ then $|\mathcal{C}|$ is even, otherwise $|\mathcal{C}|$ is odd.

Therefore (forgive me if I'm wrong):

  1. Being able to compute $\Delta_{|V|}$ in polynomial time implies $\mathbin{\oplus}$P = P.
  2. $\Delta_{|V|}$ being $\#$P-hard to compute implies $\mathbin{\oplus}$P = PP.

It seems that in both cases we would get an important result. Clearly there is a third option: computing $\Delta_{|V|}$ may be of intermediate counting complexity, strictly harder than FP but strictly easier than $\#$P-hard.

Update 08/01/2013 21:50

After reading again and more carefully T. Williams' answer to this question, my understanding is that such answer precisely proves that computing $\Delta_{|V|}$ is $\#$P-hard (because the constraint $[0,1,1,1]$ forces every node of $G$ to be present).

However, my second conclusion above does not hold: to conclude $\mathbin{\oplus}$P = PP, computing $\Delta_{|V|}\ \ mod\ \ 2$ should be $\#$P-hard. But the $\#$P-hardness of computing $\Delta_{|V|}$ is not known to imply that computing $\Delta_{|V|}\ \ mod\ \ 2$ is $\#$P-hard as well.

Only a more vague and harmless conclusion can be drawn, more or less along these lines: something which appear to be false from a practical point of view (i.e. Graph Isomorphism $\not\in$ P) would imply something already formally known to be true (i.e. computing $\Delta_{|V|}$ is $\#$P-hard).

  • $\begingroup$ So do you still have a question ? I'm confused now. $\endgroup$ Commented Jan 9, 2013 at 5:36
  • $\begingroup$ You are right, there is no question any more... It may be deleted, or it may be rephrased. I'm less willing to delete it, because $\Delta_{|V|}\ \ mod\ \ 2$ being the parity of $|C|$ is for me an interesting fact, I don't know if it was already known previously. $\endgroup$ Commented Jan 9, 2013 at 8:44

1 Answer 1


As the OP pointed out in an update above, the second question about computing $\Delta_{|V|}$ is answered in this question.

The first question is about computing the parity of the number of vertex covers. This problem is $\bigoplus$P-hard even for planar 3-regular graphs. See Section 4.1 of this paper (particularly Corollary 4.2).

First, the notation for the corresponding Holant problem is Pl-$\bigoplus$Holant$([0,1,1]|[1,0,0,1])$. Since there is a 1-to-1 correspondence between vertex covers and independent sets, sometimes people also refer to the Holant expression for independent set (in this case, $\bigoplus$Holant$([1,1,0]|[1,0,0,1])$) as though it were the vertex cover problem.

Second, I don't know why they called this problem $\bigoplus$3/2-Bip-VC (that is, why "3/2-Bip"). As I said above, this Holant expression is for the counting of vertex covers (equivalently, independent sets) in 3-regular graphs.


Your Answer

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

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