Strukturelle Graphtheorie und parametrisierte Komplexität
Final Report Abstract
The broad objective of this project was to study how graph width measures affect the design and performance of fixed-parameter algorithms and, in particular, to design good width measures for digraphs. Our study commenced with a review of the digraph width measures that had been known thus far. These included directed treewidth, DAG-width, Kellywidth, birankwidth among others. As had been observed by several researchers, most of the known digraph width measures were not useful from an algorithmic point of view in the sense that many natural problems remained hard to solve on digraphs of bounded width. A notable exception is birankwidth in that all digraph problems expressible in MSO1 can be solved in linear time on classes of bounded birankwidth. In particular, digraph width measures that attained small values for DAGs fared badly when it came to designing efficient algorithms. We strengthened this evidence by introducing two very restrictive width measures, K-width and DAG-depth, and showing that many well-known problems remained NP-hard on DAGs of small K-width and DAG-depth. This strongly suggested that DAG-based width measures were not the way forward as far as digraph width measures are concerned. Our next set of results not only proved that DAG-based width measures cannot be algorithmically useful but that, if the width measure is closed under directed topological minors, then it must be essentially the same as treewidth (of the underlying undirected graphs). In other words, if we require that the directed width measure be different from treewidth then it cannot be algorithmically useful (in a certain sense). This result is the highlight of our project as it runs contrary to popular expectations of being able to design a directed width measure that could compete with treewidth. Our third set of results was concerned with a lower bound for Courcelle’s celebrated theorem, that all graph problems expressible in Monadic Second Order Logic can be solved in linear time on classes of bounded treewidth. Extending on previous work by Kreutzer and Tazari, we showed that on graph classes with poly-logarithmically unbounded treewidth, MSO1 model-checking is not in XP-time (wrt. the formula size as parameter) under a certain complexity-theoretic assumption. Our result has an implication for digraph width measures too. If the width measure is closed under subdigraphs and is algorithmically useful that it must be within a poly-logarithmic factor away from the treewidth of the underlying undirected graph. In addition to establishing a lower bound for one of the most important algorithmic metatheorems in computer science, we feel that our work paved the way for an understanding of how structural properties of digraph width measures affect their algorithmic utility.
Publications
- On Digraph Width Measures in Parameterized Algorithmics. In Proceedings of the 4th International Workshop on Parameterized and Exact Computation (IWPEC ’09), Springer LNCS, Vol. 5917, pages 185–197, 2009
R. Ganian, P. Hlinený, J. Kneis, A. Langer, J. Obdrzálek, P. Rossmanith
- Are There Any Good Digraph Width Measures? In Proceedings of the 5th International Symposium on Parameterized Computation (IPEC ’10), Springer LNCS, Vol. 6478, Pages 135–146, 2010
R. Ganian, P. Hlinený, J. Kneis, D. Meister, J. Obdrzálek, P. Rossmanith, S. Sikdar
- Lower Bounds on the Complexity of MSO1 Model-Checking. In Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science (STACS ’12), Pages 326–337, 2012
R. Ganian, P. Hlinený, A. Langer, J. Obdrzálek, P. Rossmanith, S. Sikdar
