Beyond Bidimensionality: Parameterized Subexponential Algorithms on Directed Graphs

Date Added: Jan 2010
Format: PDF

In 2000 Alber et al. obtained the first parameterized subexponential algorithm on undirected planar graphs by showing that k-DOMINATING SET is solvable in time 2O(pk)nO(1), where n is the input size. This result triggered an extensive study of parameterized problems on planar and more general classes of sparse graphs and culminated in the creation of Bidimensionality Theory by Demaine et al. The theory utilizes deep theorems from GraphMinor Theory of Robertson and Seymour, and provides a simple criteria for checking whether a parameterized problem is solvable in subexponential time on sparse graphs.