Induced Subforests and Superforests
<|reference_start|>Induced Subforests and Superforests: Graph isomorphism, subgraph isomorphism, and maximum common subgraphs are classical well-investigated objects. Their (parameterized) complexity and efficiently tractable cases have been studied. In the present paper, for a given set of forests, we study maximum common induced subforests and minimum common induced superforests. We show that finding a maximum subforest is NP-hard already for two subdivided stars while finding a minimum superforest is tractable for two trees but NP-hard for three trees. For a given set of $k$ trees, we present an efficient greedy $\left(\frac{k}{2}-\frac{1}{2}+\frac{1}{k}\right)$-approximation algorithm for the minimum superforest problem. Finally, we present a polynomial time approximation scheme for the maximum subforest problem for any given set of forests.<|reference_end|>
@article{rautenbach2024induced,
    title={Induced Subforests and Superforests},
    author={Dieter Rautenbach and Florian Werner},
    journal={arXiv preprint arXiv:2403.14492},
    year={2024},
    archivePrefix={arXiv},
    eprint={2403.14492},
    primaryClass={cs.DS math.CO}
}