Are there any good digraph width measures?

DOI10.1007/978-3-642-17493-3_14zbMATH Open1309.68150arXiv1004.1485OpenAlexW3099288604MaRDI QIDQ3058698FDOQ3058698

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

Publication date: 7 December 2010

Published in: Parameterized and Exact Computation (Search for Journal in Brave)

Abstract: 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 emph{algorithmically useful} i.e. admitting polynomial-time algorithms for all $MS1$-definable problems on digraphs of bounded width. And, second, having nice emph{structural properties} i.e. being monotone under taking subdigraphs and some form of arc contractions. As for the former, (undirected) $MS1$ seems to be the least common denominator of all reasonably expressive logical languages on digraphs that can speak about the edge/arc relation on the vertex set.The latter property is a necessary condition for a width measure to be characterizable by some version of the cops-and-robber game characterizing the ordinary treewidth. Our main result is that emph{any reasonable} algorithmically useful and structurally nice digraph measure cannot be substantially different from the treewidth of the underlying undirected graph. Moreover, we introduce emph{directed topological minors} and argue that they are the weakest useful notion of minors for digraphs.

Full work available at URL: https://arxiv.org/abs/1004.1485

Recommendations

• Are there any good digraph width measures?
• On digraph width measures in parameterized algorithmics
• Digraph width measures in parameterized algorithmics
• Digraphs of bounded width
• How to compute digraph width measures on directed co-graphs

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph minors (05C83)

Cites Work

• Graph minors. X: Obstructions to tree-decomposition
• Directed tree-width
• Linear time solvable optimization problems on graphs of bounded clique-width
• Upper bounds to the clique width of graphs
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Easy problems for tree-decomposable graphs
• Mathematical Foundations of Computer Science 2005
• Digraph measures: Kelly decompositions, games, and orderings
• Quickly excluding a planar graph
• Graph minors. II. Algorithmic aspects of tree-width
• Treewidth: Characterizations, Applications, and Computations
• DAG-Width and Parity Games
• DAG-width
• On digraph width measures in parameterized algorithmics
• On the Algorithmic Effectiveness of Digraph Decompositions and Complexity Measures

Cited In (22)

• Lower bounds on the complexity of \(\mathsf{MSO}_1\) model-checking
• Directed NLC-width
• An algorithmic metatheorem for directed treewidth
• Are there any good digraph width measures?
• DAG-width and circumference of digraphs
• Mathematical Foundations of Computer Science 2005
• What's next? Future directions in parameterized complexity
• On the monotonicity of process number
• Subgraphs satisfying MSO properties on \(z\)-topologically orderable digraphs
• On width measures and topological problems on semi-complete digraphs
• An extended tree-width notion for directed graphs related to the computation of permanents
• Digraph width measures in parameterized algorithmics
• On digraph width measures in parameterized algorithmics
• Directed elimination games
• Dualities in graphs and digraphs
• Approximation algorithms for digraph width parameters
• Digraph decompositions and monotonicity in digraph searching
• How to compute digraph width measures on directed co-graphs
• Directed nowhere dense classes of graphs
• The rank-width of edge-coloured graphs
• Digraphs of bounded width
• Digraphs of bounded elimination width

This page was built for publication: Are there any good digraph width measures?

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3058698)