Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

This question is inspired by the Graph Reconstruction Conjecture. Suppose that $\psi$ is some graph invariant and that it is NP-Hard. There is a plethora of examples, of course. Now define $D_{\psi}(G)=\frac{\psi(G)}{\sum_{v \in V(G)}{\psi(G-v)}}$. Let's call this the "deck ratio" of $\psi$.

Is $D_{\psi}$ NP-Hard?

EDIT: Per Andrew King's suggestion, let us stipulate that is $\psi(G-v)$ takes at least two distinct values.

share|improve this question
3  
There are stupid counterexamples. Let $\psi(G)$ be $1$ if $G$ has an odd number of vertices and is $3$-colorable, and otherwise $\psi(G)=0$. Then $D_{\psi}$ is always $0$ or $\infty$. –  David Speyer Jan 9 '13 at 14:57
    
@DavidSpeyer: Is there a smart way to exclude such counterexamples? –  Felix Goldberg Jan 9 '13 at 16:40
2  
Perhaps it would be useful to insist that $\psi(G-v)$ cannot have the same value for all $v$. –  Andrew D. King Jan 11 '13 at 1:31
1  
OK. It's been a couple of days and I still don't get it. Is David's D_psi NP-easy? How do you quickly tell it is nonzero? Gerhard "Ask Me About Complexity Confusion" Paseman, 2013.01.11 –  Gerhard Paseman Jan 11 '13 at 16:28

1 Answer 1

A natural graph invariant $\psi(G)$ for which the answer is negative is the number of perfect matchings $G$ possesses. In fact, $\psi(G)$ is NP-hard but deciding $\psi(G)=0$ is easy; now it suffices to note that $D_\psi$ has either denominator or nominator zero.

We can also avoid the possibility $D_\psi=\frac{0}{0}$ by taking $\psi_1=\psi+1+(-1)^{|V|}$ instead of $\psi$. Also, many graphs $G$ satisfy the condition from Edit but not all graphs; actually, this condition is violated by any vertex-transitive graph regardless of $\psi$.

I would propose the following way to repair the conjecture:

Let $\varphi(G)$ be a graph invariant which is NP-hard and takes only positive values. Then, $D_\varphi$ is NP-hard.

share|improve this answer
    
I don't understand your example $\phi_1$. If $G$ has an even number of vertices, then $\phi_1(G-v)=-1$, right? So the deck ratio is just minus $\phi_1$. So how can one be NP-hard and the other NP-easy? I think it might be sufficient to mandate nonzero values. –  Will Sawin Aug 5 at 3:49
    
@WillSawin Thanks for comment, I meant actually $\psi_1=\psi+1$ if $|V|$ is even and $\psi_1=\psi$ otherwise. Then, $D_\psi$ is either $0$ or $+\infty$, and it is easy to decide which. Corrected. –  user2097 Aug 5 at 6:39

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.