4
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 3
    $\begingroup$ 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$. $\endgroup$
    – David E Speyer
    Jan 9, 2013 at 14:57
  • $\begingroup$ @DavidSpeyer: Is there a smart way to exclude such counterexamples? $\endgroup$
    – Felix Goldberg
    Jan 9, 2013 at 16:40
  • 2
    $\begingroup$ Perhaps it would be useful to insist that $\psi(G-v)$ cannot have the same value for all $v$. $\endgroup$
    – Andrew D. King
    Jan 11, 2013 at 1:31
  • 1
    $\begingroup$ 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 $\endgroup$
    – Gerhard Paseman
    Jan 11, 2013 at 16:28

1 Answer 1

Reset to default
1
$\begingroup$

A natural graph invariant $\psi(G)$ for which the answer is negative is the number of perfect matchings $G$ possesses. In fact, $\psi(G)$ is NP-hard but deciding $\psi(G)=0$ is easy; now it suffices to note that $D_\psi$ has either denominator or nominator zero.

We can also avoid the possibility $D_\psi=\frac{0}{0}$ by taking $\psi_1=\psi+1+(-1)^{|V|}$ instead of $\psi$. Also, many graphs $G$ satisfy the condition from Edit but not all graphs; actually, this condition is violated by any vertex-transitive graph regardless of $\psi$.

I would propose the following way to repair the conjecture:

Let $\varphi(G)$ be a graph invariant which is NP-hard and takes only positive values. Then, $D_\varphi$ is NP-hard.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I don't understand your example $\phi_1$. If $G$ has an even number of vertices, then $\phi_1(G-v)=-1$, right? So the deck ratio is just minus $\phi_1$. So how can one be NP-hard and the other NP-easy? I think it might be sufficient to mandate nonzero values. $\endgroup$
    – Will Sawin
    Aug 5, 2014 at 3:49
  • $\begingroup$ @WillSawin Thanks for comment, I meant actually $\psi_1=\psi+1$ if $|V|$ is even and $\psi_1=\psi$ otherwise. Then, $D_\psi$ is either $0$ or $+\infty$, and it is easy to decide which. Corrected. $\endgroup$
    – user56203
    Aug 5, 2014 at 6:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.