# If a graph invariant is NP-Hard, is its “deck ratio” NP-Hard as well?

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.

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

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$.
Let $\varphi(G)$ be a graph invariant which is NP-hard and takes only positive values. Then, $D_\varphi$ is NP-hard.
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 '14 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. – user56203 Aug 5 '14 at 6:39