تقرير
Tree Containment Above Minimum Degree is FPT
| العنوان: | Tree Containment Above Minimum Degree is FPT |
|---|---|
| المؤلفون: | Fomin, Fedor V., Golovach, Petr A., Sagunov, Danil, Simonov, Kirill |
| سنة النشر: | 2023 |
| المجموعة: | Computer Science |
| مصطلحات موضوعية: | Computer Science - Data Structures and Algorithms, Computer Science - Discrete Mathematics |
| الوصف: | According to the classic Chv{\'{a}}tal's Lemma from 1977, a graph of minimum degree $\delta(G)$ contains every tree on $\delta(G)+1$ vertices. Our main result is the following algorithmic "extension" of Chv\'{a}tal's Lemma: For any $n$-vertex graph $G$, integer $k$, and a tree $T$ on at most $\delta(G)+k$ vertices, deciding whether $G$ contains a subgraph isomorphic to $T$, can be done in time $f(k)\cdot n^{\mathcal{O}(1)}$ for some function $f$ of $k$ only. The proof of our main result is based on an interplay between extremal graph theory and parameterized algorithms. Comment: Accepted to SODA 2024 |
| نوع الوثيقة: | Working Paper |
| الوصول الحر: | http://arxiv.org/abs/2310.09678Test |
| رقم الانضمام: | edsarx.2310.09678 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |