Are there any good digraph width measures?

Details Are there any good digraph width measures? Are there any good digraph width measures?

2010-04-09

arxiv.org/abs/1004.1485v1

Computer Science

Discrete Mathematics

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Are there any good digraph width measures? does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Are there any good digraph width measures?, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Are there any good digraph width measures? will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-220837