Tree Independence Number IV. Even-hole-free graphs∗

Maria Chudnovsky; Peter Gartland; Sepehr Hajebi; Daniel Lokshtanov; Sophie Spirkl

Tree Independence Number IV. Even-hole-free graphs^∗

Maria Chudnovsky, Peter Gartland, Sepehr Hajebi, Daniel Lokshtanov, Sophie Spirkl

Mathematics

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

We prove that the tree independence number of every even-hole-free graph is at most polylogarithmic in its number of vertices. More explicitly, we prove that there exists a constant c > 0 such that for every integer n > 1 every n-vertex even-hole-free graph has a tree decomposition where each bag has stability (independence) number at most c log¹⁰ n. This implies that the Maximum Weight Independent Set problem, as well as several other natural algorithmic problems that are known to be NP-hard in general, can be solved in quasi-polynomial time if the input graph is even-hole-free. The quasi-polynomial complexity will remain the same even if the exponent of the logarithm is reduced to 1 (which would be asymptotically best possible).

Original language	English (US)
Title of host publication	Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025
Publisher	Association for Computing Machinery
Pages	4444-4461
Number of pages	18
ISBN (Electronic)	9798331312008
State	Published - 2025
Event	36th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025 - New Orleans, United States Duration: Jan 12 2025 → Jan 15 2025

Publication series

Name	Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Volume	7
ISSN (Print)	1071-9040
ISSN (Electronic)	1557-9468

Conference

Conference	36th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025
Country/Territory	United States
City	New Orleans
Period	1/12/25 → 1/15/25

All Science Journal Classification (ASJC) codes

Software
General Mathematics

Cite this

@inproceedings{1f13ac6b22e74b8cbe578083f3683634,

title = "Tree Independence Number IV. Even-hole-free graphs∗",

abstract = "We prove that the tree independence number of every even-hole-free graph is at most polylogarithmic in its number of vertices. More explicitly, we prove that there exists a constant c > 0 such that for every integer n > 1 every n-vertex even-hole-free graph has a tree decomposition where each bag has stability (independence) number at most c log10 n. This implies that the Maximum Weight Independent Set problem, as well as several other natural algorithmic problems that are known to be NP-hard in general, can be solved in quasi-polynomial time if the input graph is even-hole-free. The quasi-polynomial complexity will remain the same even if the exponent of the logarithm is reduced to 1 (which would be asymptotically best possible).",

author = "Maria Chudnovsky and Peter Gartland and Sepehr Hajebi and Daniel Lokshtanov and Sophie Spirkl",

note = "Publisher Copyright: Copyright {\textcopyright} 2025.; 36th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025 ; Conference date: 12-01-2025 Through 15-01-2025",

year = "2025",

language = "English (US)",

series = "Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms",

publisher = "Association for Computing Machinery",

pages = "4444--4461",

booktitle = "Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025",

}

Chudnovsky, M, Gartland, P, Hajebi, S, Lokshtanov, D & Spirkl, S 2025, Tree Independence Number IV. Even-hole-free graphs^∗. in Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, vol. 7, Association for Computing Machinery, pp. 4444-4461, 36th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025, New Orleans, United States, 1/12/25.

Tree Independence Number IV. Even-hole-free graphs^∗. / Chudnovsky, Maria; Gartland, Peter; Hajebi, Sepehr et al.
Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025. Association for Computing Machinery, 2025. p. 4444-4461 (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; Vol. 7).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Tree Independence Number IV. Even-hole-free graphs∗

AU - Chudnovsky, Maria

AU - Gartland, Peter

AU - Hajebi, Sepehr

AU - Lokshtanov, Daniel

AU - Spirkl, Sophie

PY - 2025

Y1 - 2025

N2 - We prove that the tree independence number of every even-hole-free graph is at most polylogarithmic in its number of vertices. More explicitly, we prove that there exists a constant c > 0 such that for every integer n > 1 every n-vertex even-hole-free graph has a tree decomposition where each bag has stability (independence) number at most c log10 n. This implies that the Maximum Weight Independent Set problem, as well as several other natural algorithmic problems that are known to be NP-hard in general, can be solved in quasi-polynomial time if the input graph is even-hole-free. The quasi-polynomial complexity will remain the same even if the exponent of the logarithm is reduced to 1 (which would be asymptotically best possible).

AB - We prove that the tree independence number of every even-hole-free graph is at most polylogarithmic in its number of vertices. More explicitly, we prove that there exists a constant c > 0 such that for every integer n > 1 every n-vertex even-hole-free graph has a tree decomposition where each bag has stability (independence) number at most c log10 n. This implies that the Maximum Weight Independent Set problem, as well as several other natural algorithmic problems that are known to be NP-hard in general, can be solved in quasi-polynomial time if the input graph is even-hole-free. The quasi-polynomial complexity will remain the same even if the exponent of the logarithm is reduced to 1 (which would be asymptotically best possible).

UR - http://www.scopus.com/inward/record.url?scp=85217698227&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85217698227&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:85217698227

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 4444

EP - 4461

BT - Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025

PB - Association for Computing Machinery

T2 - 36th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025

Y2 - 12 January 2025 through 15 January 2025

ER -