Induced Subforests and Superforests
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909145032032256 |
|---|---|
| author | Rautenbach, Dieter Werner, Florian |
| author_facet | Rautenbach, Dieter Werner, Florian |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_14492 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Induced Subforests and Superforests Rautenbach, Dieter Werner, Florian Data Structures and Algorithms Combinatorics 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. |
| title | Induced Subforests and Superforests |
| topic | Data Structures and Algorithms Combinatorics |
| url | https://arxiv.org/abs/2403.14492 |