Tree Containment Above Minimum Degree is FPT

2023/10/14 by Fedor V. Fomin, Petr A. Golovach, Fomin, Fedor V. +5
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2310.09678

openalex publication_date 2023/10/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

According to the classic Chvátal's Lemma from 1977, a graph of minimum degree δ(G) contains every tree on δ(G)+1 vertices. Our main result is the following algorithmic "extension" of Chvátal's Lemma: For any n-vertex graph G, integer k, and a tree T on at most δ(G)+k vertices, deciding whether G contains a subgraph isomorphic to T, can be done in time f(k)⋅ n^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.

Related

• Structure Theorem and Isomorphism Test for Graphs with Excluded\n Topological Subgraphs
• Subtree Isomorphism Revisited
• Conditional Lower Bound for Subgraph Isomorphism with a Tree Pattern
• An improved isomorphism test for bounded-tree-width graphs
• Maximum and minimum degree conditions for embedding trees