Are there any good digraph width measures - Computer Science > Discrete MathematicsReport as inadecuate




Are there any good digraph width measures - Computer Science > Discrete Mathematics - Download this document for free, or read online. Document in PDF available to download.

Abstract: Several different measures for digraph width have appeared in the last fewyears. However, none of them shares all the -nice- properties of treewidth:First, being \emph{algorithmically useful} i.e. admitting polynomial-timealgorithms for all $\MS1$-definable problems on digraphs of bounded width. And,second, having nice \emph{structural properties} i.e. being monotone undertaking subdigraphs and some form of arc contractions. As for the former,undirected $\MS1$ seems to be the least common denominator of all reasonablyexpressive logical languages on digraphs that can speak about the edge-arcrelation on the vertex set.The latter property is a necessary condition for awidth measure to be characterizable by some version of the cops-and-robber gamecharacterizing the ordinary treewidth. Our main result is that \emph{anyreasonable} algorithmically useful and structurally nice digraph measure cannotbe substantially different from the treewidth of the underlying undirectedgraph. Moreover, we introduce \emph{directed topological minors} and argue thatthey are the weakest useful notion of minors for digraphs.



Author: Robert Ganian, Petr Hliněný, Joachim Kneis, Daniel Meister, Jan Obdržálek, Peter Rossmanith, Somnath Sikdar

Source: https://arxiv.org/







Related documents