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

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|}$.

## Question

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

## Motivation

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

• So do you still have a question ? I'm confused now. Jan 9, 2013 at 5:36
• 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. Jan 9, 2013 at 8:44

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.