Largest common subgraph of two forests
<|reference_start|>Largest common subgraph of two forests: A common subgraph of two graphs $G_1$ and $G_2$ is a graph that is isomorphic to subgraphs of $G_1$ and $G_2$. In the largest common subgraph problem the task is to determine a common subgraph for two given graphs $G_1$ and $G_2$ that is of maximum possible size ${\rm lcs}(G_1,G_2)$. 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 $\epsilon\in (0,1)$, we show that, for two given forests $F_1$ and $F_2$ of order at most $n$, one can determine in polynomial time a common subgraph $F$ of $F_1$ and $F_2$ with at least ${\rm lcs}(F_1,F_2)-\epsilon n$ edges. Restricted to instances with ${\rm lcs}(F_1,F_2)\geq 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.<|reference_end|>
@article{rautenbach2024largest,
    title={Largest common subgraph of two forests},
    author={Dieter Rautenbach and Florian Werner},
    journal={arXiv preprint arXiv:2403.03696},
    year={2024},
    archivePrefix={arXiv},
    eprint={2403.03696},
    primaryClass={cs.DS cs.DM math.CO}
}