2010 | OriginalPaper | Buchkapitel
Are There Any Good Digraph Width Measures?
verfasst von : Robert Ganian, Petr Hliněný, Joachim Kneis, Daniel Meister, Jan Obdržálek, Peter Rossmanith, Somnath Sikdar
Erschienen in: Parameterized and Exact Computation
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Several width measures for digraphs have been proposed in the last few years. However, none of them possess all the “nice” properties of treewidth, namely, (1) being
algorithmically useful
, that is, admitting polynomial-time algorithms for a large class of problems on digraphs of bounded width; and (2) having nice
structural properties
such as being monotone under taking subdigraphs and some form of arc contractions. As for (1), MSO
1
is the least common denominator of all reasonably expressive logical languages that can speak about the edge/arc relation on the vertex set, and so it is quite natural to demand efficient solvability of all MSO
1
-definable problems in this context. (2) is a necessary condition for a width measure to be characterizable by some version of the cops-and-robber game characterizing treewidth. More specifically, we introduce a notion of a
directed topological minor
and argue that it is the weakest useful notion of minors for digraphs in this context. Our main result states that any
reasonable
digraph measure that is algorithmically useful and structurally nice cannot be substantially different from the treewidth of the underlying undirected graph.