<p>As the OP pointed out in an update above, the second question about computing $\Delta_{|V|}$ is answered in <a href="https://cstheory.stackexchange.com/questions/12475/the-odd-even-delta-problem/12476#12476">this question</a>.</p>

<p>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 <a href="http://pages.cs.wisc.edu/~hguo/Papers/ParityHP.pdf" rel="nofollow noreferrer">this paper</a> (particularly Corollary 4.2).</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2013-01-09T15:20:46.617Z
2013-01-09T15:20:46.617Z
2017-04-13T12:32:28.117Z
Tyson Williams
<p>Let $G=(V,E)$ be a graph. Let $\Delta_k$ be the quantity defined in <a href="https://cstheory.stackexchange.com/questions/12475/the-odd-even-delta-problem">this question</a>. Let $\mathcal{C}$ be the set of vertex covers of $G$. The following holds:</p>

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

<p>Let us focus on $\Delta_{|V|}$.</p>

<hr>

<h2>Question</h2>

<p>How hard is to compute $\Delta_{|V|}$?</p>

<hr>

<h2>Motivation</h2>

<p>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.</p>

<p>Therefore (forgive me if I'm wrong):</p>

<ol>
<li>Being able to compute $\Delta_{|V|}$ in polynomial time implies $\mathbin{\oplus}$P = P.</li>
<li>$\Delta_{|V|}$ being $\#$P-hard to compute implies $\mathbin{\oplus}$P = PP. </li>
</ol>

<p>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.</p>

<h2>Update 08/01/2013 21:50</h2>

<p>After reading again and more carefully T. Williams' answer to <a href="https://cstheory.stackexchange.com/questions/12475/the-odd-even-delta-problem">this question</a>, 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).</p>

<p>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.</p>

<p>Only a more vague and harmless conclusion can be drawn, more or less along these lines: something which appear to be false from a <em>practical</em> 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).</p>

CC BY-SA 3.0
2013-01-09T05:36:48.880Z
So do you still have a question ? I'm confused now.
Suresh Venkat
CC BY-SA 3.0
2013-01-09T08:44:15.870Z
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.
Giorgio Camerani
<cc.complexity-theory><complexity-classes><counting-complexity><graph-isomorphism>
How hard is to compute $\Delta_{|V|}$?
Giorgio Camerani
# How hard is to compute $\Delta_{|V|}$?

(Asked by: username_0 on 2013-01-08)

Let $G=(V,E)$ be a graph. Let $\Delta\_k$ be the quantity defined in [this question](https://cstheory.stackexchange.com/questions/12475/the-odd-even-delta-problem). 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](https://cstheory.stackexchange.com/questions/12475/the-odd-even-delta-problem), 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).

**Tags:** cc.complexity-theory, complexity-classes, counting-complexity, graph-isomorphism
> **Comments:**
> **username_1**: So do you still have a question ? I'm confused now.  
> **username_0**: 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.  

---

## 1 answers

### Answer by username_2 on 2013-01-09. Score: 3 | Accepted answer

As the OP pointed out in an update above, the second question about computing $\Delta\_{|V|}$ is answered in [this question](https://cstheory.stackexchange.com/questions/12475/the-odd-even-delta-problem/12476#12476).

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](http://pages.cs.wisc.edu/~hguo/Papers/ParityHP.pdf) (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.


---

