Is there any graph problem that, when restricted to trees, has $\Omega(n^2)$ time complexity?

Question

Trees are pretty linear in nature, since the number of edges is always one less than the number of vertices. Furthermore, the absence of cycles can sometimes drastically reduce the computational complexity of otherwise pretty hard problems. For example, the longest path problem is NP-hard for general graphs, but is easily solved in linear time for trees. Many other examples exists, where a graph problem magically becomes doable in constant- or linear-time, just because of the restriction to trees (an example for the constant case being the minimum spanning tree problem). I guess sometimes you could be forced to a linearithmic lower bound, although I'm not completely sure at the time of writing this (but my main question for now lies in the next paragraph).

However, I have struggled for a few weeks to come up with an example of a problem that has to have an $\Omega(n^2)$ bound even when restricting to trees. I suspect these problems may exist, but can't come up with any. Can anyone give me an example, or alternatively give me a proof that all decision problems on trees are decidable in less than quadratic time?

Of course, I assume we are not representing the tree using the adjacency matrix, but rather an adjacency-list or other timesaving data structure.

I also suspect that I might need to explicitly state to consider only tractable problems, since I guess you could come up with halting-type problems for trees otherwise.

Answer 1

Yes. By the time hierarchy theorem, there is a (tractable, solvable in $O(n^2 \log n)$ time) problem $X$ that (on an $n$-bit instance) can not be solved in less than $\Omega(N^2)$ time.

Given an $n$-bit string, I can encode it as a tree, for instance by taking a path $p_1,\ldots, p_n$ of length $n$ and adding an additional leaf vertex to vertex $p_i$ if the corresponding bit $i$ in the string is $1$ (and perhaps adding some constant-size gadget to mark the beginning of the string).

Now I will define problem $Y$ to be to recognize the trees that encode a bitstring that is a (valid) instance of $X$. Clearly this problem requires at least quadratic time (or otherwise we would have a faster algorithm for $X$).

This is of course a rather contrived and artificial example, but there are some natural problems that are hard for trees as well. See e.g. NP-hard problems on trees.