Three-in-a-Tree in Near Linear Time

DOI10.1145/3357713.3384235MaRDI QIDQ6325423arXivFDO

Authors Kai-Yuan Lai, Hsueh-I Lu, Mikkel Thorup

Publication date 16 September 2019

Published in arXiv

Full work available at URL https://doi.org/10.1145/3357713.3384235

Mathematics Subject Classification ID

Theory of computing (68Qxx)

arXiv classification

cs.DMcs.DSmath.CO

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 $ildeO(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.

This page was built for publication: Three-in-a-Tree in Near Linear Time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6325423)