Skip to main content
Top

2010 | OriginalPaper | Chapter

Are There Any Good Digraph Width Measures?

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

Published in: Parameterized and Exact Computation

Publisher: Springer Berlin Heidelberg

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Several width measures for digraphs have been proposed in the last few years. However, none of them possess all the “nice” properties of treewidth, namely, (1) being

algorithmically useful

, that is, admitting polynomial-time algorithms for a large class of problems on digraphs of bounded width; and (2) having nice

structural properties

such as being monotone under taking subdigraphs and some form of arc contractions. As for (1), MSO

1

is the least common denominator of all reasonably expressive logical languages that can speak about the edge/arc relation on the vertex set, and so it is quite natural to demand efficient solvability of all MSO

1

-definable problems in this context. (2) is a necessary condition for a width measure to be characterizable by some version of the cops-and-robber game characterizing treewidth. More specifically, we introduce a notion of a

directed topological minor

and argue that it is the weakest useful notion of minors for digraphs in this context. Our main result states that any

reasonable

digraph measure that is algorithmically useful and structurally nice cannot be substantially different from the treewidth of the underlying undirected graph.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Metadata
Title
Are There Any Good Digraph Width Measures?
Authors
Robert Ganian
Petr Hliněný
Joachim Kneis
Daniel Meister
Jan Obdržálek
Peter Rossmanith
Somnath Sikdar
Copyright Year
2010
Publisher
Springer Berlin Heidelberg
DOI
https://doi.org/10.1007/978-3-642-17493-3_14

Premium Partner