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 ( (n) ) different starlike rooted trees and iterative quantizations of the options for the solutions.