Largest chordal and interval subgraphs faster than 2^n

Ivan Bliznets, Fedor V. Fomin, Michał Pilipczuk +1

We prove that in an n-vertex graph, induced chordal and interval subgraphs with the maximum number of vertices can be found in time $O(2^{\lambda n})$ for some $\lambda <1$. These are the first…