Vertex Deletion on Chordal Graphs and Their Subclasses

Abstract

Numerous computational problems on graphs remain computationally intractable and are termed NP-complete problems. In this thesis, we study one of the ways to tackle this issue: we restrict the input graphs by specifying certain properties and exploit these to build efficient algorithms on these classes. We focus on the vital class of chordal graphs, which have rich structural properties with varied algorithmic applications. A major class of graph problems are termed vertex deletion problems, which involve eliminating a certain set of vertices so that the resultant graph satisfies some properties. We study vertex deletion problems on the chordal graph class, as well as their subclasses. We first review the relevant properties of these graph classes and study the status of vertex deletion problems on these graphs. We then move to design efficient algorithms for some unresolved problems.