Efficient Algorithms on Cocomparability Graphs via Vertex Orderings

Abstract

In this thesis, we give new structural and algorithmic results on cocomparability (ccp) graphs; particularly, by connecting structural properties of graph searching to those of ver- tex ordering characterizations and linear extensions of posets. To do so, we present new tools that we hope will prove useful on other applications – especially a new graph parti- tion refinement technique, and a new graph parameter that captures the linear structure exhibited by certain graph classes. The thesis consists of two main parts. In the first half, we give the first linear time algorithm to compute a LexDFS ordering of ccp graphs. Doing so, we overcome a bottleneck to achieving certifying linear time Hamilton path, max independent set and max matching algorithms on this graph class. Building on this result, we give a new simple and elegant algorithm to the classical minimum bump problem on posets. Lastly, we introduce a new graph invariant, LexCycle, which measures how linearly structured certain graph classes are, this linear structure has been a driving factor to a number of efficient algorithms. In the second half of the thesis, we lift our results to weighted ccp graphs. In particular, we give the first linear time robust algorithm for the weighted max independent set problem on this graph class; we then build on this result to give the fastest (O(mn) time) algorithm for the weighted induced matching problem on ccp graphs. In this latter work, we also give a unifying framework that captures graphs, characterized by forbidden orderings, which are closed under L2(·), the operation of computing the square of the line graph. We conclude by presenting structural properties on AT-free graphs, a superclass of ccp graphs, that we hope can be used to lift some of these results to this larger graph class.