# Is there a *natural* problem that is NP-hard on trees, but in P on non-trees?

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?

• 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. – jmite May 2 at 21:38