Three-in-a-tree in near linear time
Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
Dokumenter
- Three-in-a-Tree in Near Linear Time∗
Forlagets udgivne version, 2,63 MB, PDF-dokument
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(mn2) 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 O(mlog2 n) 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.
Originalsprog | Engelsk |
---|---|
Titel | STOC 2020 - Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing |
Redaktører | Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, Julia Chuzhoy |
Forlag | Association for Computing Machinery |
Publikationsdato | 2020 |
Sider | 1279-1292 |
ISBN (Elektronisk) | 9781450369794 |
DOI | |
Status | Udgivet - 2020 |
Begivenhed | 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020 - Chicago, USA Varighed: 22 jun. 2020 → 26 jun. 2020 |
Konference
Konference | 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020 |
---|---|
Land | USA |
By | Chicago |
Periode | 22/06/2020 → 26/06/2020 |
Sponsor | ACM Special Interest Group on Algorithms and Computation Theory (SIGACT) |
Navn | Proceedings of the Annual ACM Symposium on Theory of Computing |
---|---|
ISSN | 0737-8017 |
Antal downloads er baseret på statistik fra Google Scholar og www.ku.dk
ID: 258497711