تقرير
Largest common subgraph of two forests
| العنوان: | Largest common subgraph of two forests |
|---|---|
| المؤلفون: | Rautenbach, Dieter, Werner, Florian |
| سنة النشر: | 2024 |
| المجموعة: | Computer Science Mathematics |
| مصطلحات موضوعية: | Computer Science - Data Structures and Algorithms, Computer Science - Discrete Mathematics, 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 $\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. |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2403.03696 |
| رقم الأكسشن: | edsarx.2403.03696 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |