Three-in-a-Tree in Near Linear Time

Abstract

The three-in-a-tree problem is to determine if a simple undirected graph contains an induced subgraph which is a tree connecting three given vertices. Based on a beautiful characterization that is proved in more than twenty pages, Chudnovsky and Seymour [Combinatorica 2010] gave the previously only known polynomial-time algorithm, running in $O(m{n}^2)$ time, to solve the three-in-a-tree problem on an $n$-vertex $m$-edge graph. Their three-in-a-tree algorithm has become a critical subroutine in several state-of-the-art graph recognition and detection algorithms. In this paper we solve the three-in-a-tree problem in $\tilde{O}(m)$ time, leading to improved algorithms for recognizing perfect graphs and detecting thetas, pyramids, beetles, and odd and even holes. Our result is based on a new and more constructive characterization than that of Chudnovsky and Seymour. Our new characterization is stronger than the original, and our proof implies a new simpler proof for the original characterization. The improved characterization gains the first factor $n$ in speed. The remaining improvement is based on dynamic graph algorithms.

arXiv comment46 pages, 12 figures, accepted to STOC 2020

References in corpus (12)

• A structure theorem for graphs with no cycle with a unique chord and its consequences
• Detecting induced subgraphs
• Algorithms for perfectly contractile graphs
• The k-in-a-path problem for claw-free graphs
• Combinatorial optimization with 2-joins
• Detecting 2-joins faster
• Decomposing Berge graphs and detecting balanced skew partitions
• A Faster Algorithm to Recognize Even-Hole-Free Graphs
• The $k$-in-a-tree problem for graphs of girth at least~$k$
• The four-in-a-tree problem in triangle-free graphs
• Finding an induced subdivision of a digraph
• Detecting an induced net subdivision

Cited by in corpus (2)

• Finding a Shortest Even Hole in Polynomial Time
• Blazing a Trail via Matrix Multiplications: A Faster Algorithm for Non-shortest Induced Paths