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?