Are there any good digraph width measures?
From MaRDI portal
Publication:3058698
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 and Parity Games
- DAG-width
- 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)- 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
- Directed elimination games
- Digraph width measures in parameterized algorithmics
- On digraph width measures in parameterized algorithmics
- Approximation algorithms for digraph width parameters
- Dualities in graphs and digraphs
- 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)
