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

Your Answer


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

Browse other questions tagged or ask your own question.