Largest Chordal and Interval Subgraphs Faster than $$2^n$$ 2 n
Ivan Bliznets, Fedor V. Fomin, Michał Pilipczuk, Yngve Villanger · Algorithmica · 2015
We prove that in a graph with n vertices, induced chordal and interval subgraphs with the maximum number of vertices can be found in time $$\mathcal {O}(2^{\lambda n})$$ for some $$\lambda <1$$ . These are the first algorithms breaking the trivial $$2^n n^{\mathcal {O}(1)}$$ bound of the brute-force search for these problems.