Skip to main content
2 of 3
edited title
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?

Felix Goldberg
  • 7k
  • 4
  • 31
  • 55