Skip to main content
3 of 3
added 113 characters in body
Felix Goldberg
  • 7k
  • 4
  • 31
  • 55

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.

Felix Goldberg
  • 7k
  • 4
  • 31
  • 55