2

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.

flag
2 
 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 at 14:57
@DavidSpeyer: Is there a smart way to exclude such counterexamples? – Felix Goldberg Jan 9 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 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 at 16:28

Your Answer

Get an OpenID
or

Browse other questions tagged or ask your own question.