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~(λn)) for some λ ＞ 1. These are the first algorithms breaking the trivial 2~nn~(O(1)) bound of the brute-force search for these problems.
展开▼
