Are there any good digraph width measures?

Investor logo

Warning

This publication doesn't include Faculty of Arts. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

GANIAN Robert HLINĚNÝ Petr OBDRŽÁLEK Jan KNEIS Joachim MEISTER Daniel SIKDAR Somnath ROSSMANITH Peter

Year of publication 2010
Type Article in Proceedings
Conference Parameterized and exact computation, IPEC 2010
MU Faculty or unit

Faculty of Informatics

Citation
Web DOI
Doi http://dx.doi.org/10.1007/978-3-642-17493-3_14
Field Informatics
Keywords directed graphs; width measures; monadic second order logic; directed graph minors
Description Several different measures for digraph width have appeared in the last few years. However, none of them shares all the ``nice'' properties of treewidth: First, being algorithmically useful - say, admitting polynomial-time algorithms for all MSO1-definable problems on digraphs of bounded width. And, second, having nice structural properties such as being monotone under taking subdigraphs and some form of arc contractions. Our main result then is that any reasonable algorithmically useful and structurally nice digraph measure cannot be substantially different from the treewidth of the underlying undirected graph
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.