I recently read that the following problem is NP-Complete:

Given a tree $T$, and a forest $F$, is there a subgraph of $T$ isomorphic to $F$?

The reference provide was to the textbook “Computers and Intractability: A Guide to the Theory of NP-Completeness”, which I don’t own. I was wondering what is the best known algorithm for this problem, and if there are any families of forests which have polynomial algorithms. (Polynomial in terms of the number of nodes in $T$) It is known that if $F$ is a tree, there is a polynomial algorithm.

Obviously, if the family has a bounded number of components, at most $C$, then there exists a polynomial solution, as there are then there are polynomially many ways we can remove $C-1$ edges from $T$, then for each component $t$ of $T$ we tabulate which components of $F$ are subtrees of $t$, and then we can check for a list coloring of a complete graph where $L(t)$ is the subtrees of $t$ in $F$. (since we can list color a complete graph in polynomial time)

Meanwhile, if $F$ is a forest whose components must all be a copies of some fixed tree $t$, then we can reduce the problem to fitting the most copies of $t$ into rooted trees of depth $diam(t)$. (with some extra complication concerning the remaining component containing the root) I believe when $t$ is a path graph, this is not too difficult to handle.

However, when my attention to the components of $F$ being arbitrary path graphs, I feel quite stumped. Is there a clever solution to this one?

Edit 1: on second thought, one should be able to make a reduction to 3-partitioning for this family of forests, so I guess it’s strongly NP-Complete.

  • 1
    $\begingroup$ Yes, G&J reduction is from 3-partition. You can check this paper arxiv.org/abs/1307.2187 for some results depending of the structure of the graphs. $\endgroup$ – Olf Jan 10 '20 at 14:03

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.