Are there any good digraph width measures?
From MaRDI portal
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 -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) 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.
Recommendations
Cites work
- DAG-width
- DAG-Width and Parity Games
- Digraph measures: Kelly decompositions, games, and orderings
- Directed tree-width
- Easy problems for tree-decomposable graphs
- Graph minors. II. Algorithmic aspects of tree-width
- Graph minors. X: Obstructions to tree-decomposition
- Linear time solvable optimization problems on graphs of bounded clique-width
- Mathematical Foundations of Computer Science 2005
- On digraph width measures in parameterized algorithmics
- On the Algorithmic Effectiveness of Digraph Decompositions and Complexity Measures
- Quickly excluding a planar graph
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Treewidth: Characterizations, Applications, and Computations
- Upper bounds to the clique width of graphs
Cited in
(22)- How to compute digraph width measures on directed co-graphs
- An extended tree-width notion for directed graphs related to the computation of permanents
- On width measures and topological problems on semi-complete digraphs
- The rank-width of edge-coloured graphs
- Digraphs of bounded elimination width
- Digraph width measures in parameterized algorithmics
- An algorithmic metatheorem for directed treewidth
- DAG-width and circumference of digraphs
- Subgraphs satisfying MSO properties on z-topologically orderable digraphs
- What's next? Future directions in parameterized complexity
- On the monotonicity of process number
- Digraphs of bounded width
- On digraph width measures in parameterized algorithmics
- Lower bounds on the complexity of \(\mathsf{MSO}_1\) model-checking
- Approximation algorithms for digraph width parameters
- Mathematical Foundations of Computer Science 2005
- Directed nowhere dense classes of graphs
- Digraph decompositions and monotonicity in digraph searching
- Dualities in graphs and digraphs
- Are there any good digraph width measures?
- Directed elimination games
- Directed NLC-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)
