Largest common subgraph of two forests

A common subgraph of two graphs G₁ and G₂ is a graph that is isomorphic to subgraphs of G₁ and G₂. In the largest common subgraph problem the task is to determine a common subgraph for two given graphs G₁ and G₂ that is of maximum possible size lcs(G₁,G₂). This natural problem generalizes the well-studied graph isomorphism problem, has many applications, and remains NP-hard even restricted to unions of paths. We present a simple $4$-approximation algorithm for forests, and, for every fixed ε∈ (0,1), we show that, for two given forests F₁ and F₂ of order at most n, one can determine in polynomial time a common subgraph F of F₁ and F₂ with at least lcs(F₁,F₂)-ε n edges. Restricted to instances with lcs(F₁,F₂)≥ cn for some fixed positive c, this yields a polynomial time approximation scheme. Our approach relies on the approximation of the given forests by structurally simpler forests that are composed of copies of only O(log (n)) different starlike rooted trees and iterative quantizations of the options for the solutions.