Tree Independence Number IV Even-hole-free Graphs
<|reference_start|>Tree Independence Number IV Even-hole-free Graphs: 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^10 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.<|reference_end|>
@article{chudnovsky2024tree,
    title={Tree Independence Number IV. Even-hole-free Graphs},
    author={Maria Chudnovsky, Peter Gartland, Sepehr Hajebi, Daniel Lokshtanov,
  Sophie Spirkl},
    journal={arXiv preprint arXiv:2407.08927},
    year={2024},
    archivePrefix={arXiv},
    eprint={2407.08927},
    primaryClass={math.CO cs.DM cs.DS}
}