3
$\begingroup$

It seems intuitive that any natural problem that is NP-hard on trees, should be hard on graphs that are not trees. But perhaps this is wrong?

Question: Is there some natural decision problem on graphs that is NP-hard when we are promised the graph is a tree, but in $P$ when the graph is promised to not be a tree.

Thoughts:

  • Here's a list of problems that are NP-hard on trees: https://cstheory.stackexchange.com/questions/1215/np-hard-problems-on-trees The ones I saw were all also hard on non-trees.

  • Given any NP-complete language $M$ that is NP-complete on trees, you can obtain a tautological example via the decision problem $L$ where $x \in L$ iff $x \in M$ and $x$ is a tree. This is pretty unnatural though.

  • Is there some object that trees have a lot of of, but non-trees only have a few of?

$\endgroup$
  • $\begingroup$ Any question like this will likely have to be an existential question: i.e. does there exists a tree $T$ for input $x$ such that $T$ has property $P(x)$. So there may be problems where some cyclic graph always trivially solves $P$, but searching only in the space of trees is much harder. But the question "does a given tree $T$ have property $P$" will always be at least as easy for trees as graphs, provided we use the same $P$ for them. $\endgroup$ – jmite May 2 at 21:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.