$Forest$ is in $P$. Given a finite undirected graph $G$ one can in polynomial time decide whether the input is a forest. The class of all finite forests is a minor-closed property and by the Robertson–Seymour theorem, there are finitely many forbidden minors. We can in $O(n^3)$ time test whether $G$ contains a forbidden minor and if not, output yes.
|
1 | [made Community Wiki] | ||
|
|
||||
