Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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

share|improve this question
    
So do you still have a question ? I'm confused now. –  Suresh Venkat Jan 9 '13 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. –  Giorgio Camerani Jan 9 '13 at 8:44

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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