most recent 30 from http://mathoverflow.net 2013-05-22T14:55:03Z http://mathoverflow.net/feeds/question/118439 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/118439/if-a-graph-invariant-is-np-hard-is-its-deck-ratio-np-hard-as-well Felix Goldberg 2013-01-09T11:38:57Z 2013-01-11T14:45:06Z

<p>This question is inspired by the <a href="http://en.wikipedia.org/wiki/Reconstruction_conjecture" rel="nofollow">Graph Reconstruction Conjecture</a>. 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$.</p> <blockquote> <p>Is $D_{\psi}$ NP-Hard?</p> </blockquote> <p>EDIT: Per Andrew King's suggestion, let us stipulate that is $\psi(G-v)$ takes at least two distinct values.</p>