Largest common subgraph of two forests
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916148862255104 |
|---|---|
| author | Rautenbach, Dieter Werner, Florian |
| author_facet | Rautenbach, Dieter Werner, Florian |
| contents | 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 $ε\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)-ε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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_03696 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Largest common subgraph of two forests Rautenbach, Dieter Werner, Florian Data Structures and Algorithms Discrete Mathematics Combinatorics 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 $ε\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)-ε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. |
| title | Largest common subgraph of two forests |
| topic | Data Structures and Algorithms Discrete Mathematics Combinatorics |
| url | https://arxiv.org/abs/2403.03696 |