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
    Commented Jan 9, 2013 at 14:57
  • $\begingroup$ @DavidSpeyer: Is there a smart way to exclude such counterexamples? $\endgroup$
    – Felix Goldberg
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented Aug 5, 2014 at 6:39

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .