×

zbMATH — the first resource for mathematics

Are there any good digraph width measures? (English) Zbl 1327.05136
Summary: Many width measures for directed graphs have been proposed in the last few years in pursuit of generalizing (the notion of) treewidth to directed graphs. However, none of these measures possesses, at the same time, the major 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 (e.g. the problems definable in \(\mathrm{MSO}_1\)); (2) having nice structural properties such as being (at least nearly) monotone under taking subdigraphs and some form of arc contractions (property closely related to characterizability by particular cops-and-robber games). We investigate the question whether the search for directed treewidth counterparts has been unsuccessful by accident, or whether it has been doomed to fail from the beginning. Our main result states that any reasonable width measure for directed graphs which satisfies the two properties above must necessarily be similar to treewidth of the underlying undirected graph.

MSC:
05C20 Directed graphs (digraphs), tournaments
05C12 Distance in graphs
05C05 Trees
91A24 Positional games (pursuit and evasion, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ageev, A., Complexity of the network Median problem on planar grids, Siberian Adv. Math., 5, 1-9, (1995) · Zbl 0848.05057
[2] Arnborg, S.; Lagergren, J.; Seese, D., Easy problems for tree-decomposable graphs, J. Algorithms, 12, 2, 308-340, (1991) · Zbl 0734.68073
[3] Barát, J., Directed path-width and monotonicity in digraph searching, Graphs Combin., 22, 2, 161-172, (2006) · Zbl 1138.05069
[4] Berwanger, D.; Dawar, A.; Hunter, P.; Kreutzer, S., DAG-width and parity games, (STACS’06, Lecture Notes in Comput. Sci., vol. 3884, (2006), Springer), 524-536 · Zbl 1136.68447
[5] Berwanger, D.; Dawar, A.; Hunter, P.; Kreutzer, S.; Obdržálek, J., The DAG-width of directed graphs, J. Combin. Theory Ser. B, 102, 4, 900-923, (2012) · Zbl 1246.05065
[6] Bodlaender, H., Treewidth: characterizations, applications, and computations, (WG’06, Lecture Notes in Comput. Sci., vol. 4271, (2006), Springer), 1-14 · Zbl 1167.68404
[7] Brooks, R., On colouring the nodes of a network, Math. Proc. Cambridge Philos. Soc., 37, 194-197, (1941) · Zbl 0027.26403
[8] Chen, X.; Hu, X.; Zang, W., A MIN-MAX theorem on tournaments, SIAM J. Comput., 37, 923-937, (2007) · Zbl 1191.90028
[9] Courcelle, B., The monadic second order logic of graphs I: recognizable sets of finite graphs, Inform. and Comput., 85, 12-75, (1990) · Zbl 0722.03008
[10] Courcelle, B.; Engelfriet, J., Graph structure and monadic second-order logic, a language theoretic approach, (2012), Cambridge University Press · Zbl 1257.68006
[11] Courcelle, B.; Olariu, S., Upper bounds to the clique width of graphs, Discrete Appl. Math., 101, 1-3, 77-114, (2000) · Zbl 0958.05105
[12] Courcelle, B.; Makowsky, J. A.; Rotics, U., Linear time solvable optimization problems on graphs of bounded clique-width, Theory Comput. Syst., 33, 2, 125-150, (2000) · Zbl 1009.68102
[13] Diestel, R., Graph theory, Grad. Texts in Math., vol. 173, (2005), Springer New York · Zbl 1074.05001
[14] Downey, R.; Fellows, M., Parameterized complexity, Monogr. Comput. Sci., (1999), Springer · Zbl 0914.68076
[15] Dvořák, Z.; Škrekovski, R.; Tancer, M., List coloring squares of sparse subcubic graphs, SIAM J. Discrete Math., 22, 139-159, (2008) · Zbl 1159.05018
[16] Ebbinghaus, H. D.; Flum, J.; Thomas, W., Mathematical logic, Undergrad. Texts Math., (1994), Springer · Zbl 0795.03001
[17] Fortune, S.; Hopcroft, J. E.; Wyllie, J., The directed subgraph homeomorphism problem, Theoret. Comput. Sci., 10, 111-121, (1980) · Zbl 0419.05028
[18] Fraysseix, H.; Pach, J.; Pollack, R., How to draw a planar graph on a grid, Combinatorica, 10, 41-51, (1990) · Zbl 0728.05016
[19] Ganian, R.; Hliněný, P., On parse trees and myhill-nerode-type tools for handling graphs of bounded rank-width, Discrete Appl. Math., 158, 851-867, (2010) · Zbl 1231.05096
[20] Ganian, R.; Hliněný, P.; Obdržálek, J., Clique-width: when hard does not mean impossible, (STACS’11, LIPIcs. Leibniz Int. Proc. Inform., vol. 9, (2011), Dagstuhl Publishing), 404-415 · Zbl 1230.68109
[21] Ganian, R.; Hliněný, P.; Obdržálek, J., A unified approach to polynomial algorithms on graphs of bounded (bi-)rank-width, European J. Combin., 34, 3, 680-701, (2013) · Zbl 1257.05168
[22] Ganian, R.; Hliněný, P.; Kneis, J.; Langer, A.; Obdržálek, J.; Rossmanith, P., Digraph width measures in parameterized algorithmics, Discrete Appl. Math., 168, 88-107, (2014) · Zbl 1285.05077
[23] Ganian, R.; Hliněný, P.; Langer, A.; Obdržálek, J.; Rossmanith, P.; Sikdar, S., Lower bounds on the complexity of MSO_1 model-checking, J. Comput. System Sci., 80, 1, 180-194, (2014) · Zbl 1311.68087
[24] Garey, M.; Johnson, D.; Stockmeyer, L., Some simplified NP-complete graph problems, Theoret. Comput. Sci., 1, 237-267, (1976) · Zbl 0338.05120
[25] Hliněný, P.; Oum, S.; Seese, D.; Gottlob, G., Width parameters beyond tree-width and their applications, Comput. J., 51, 3, 326-362, (2008)
[26] Hodges, W., A shorter model theory, (1997), Cambridge University Press · Zbl 0873.03036
[27] Hunter, P., Complexity and infinite games on finite graphs, (2007), University of Cambridge, PhD thesis
[28] Hunter, P.; Kreutzer, S., Digraph measures: kelly decompositions, games, and orderings, Theoret. Comput. Sci., 399, 3, 206-219, (2008) · Zbl 1152.91015
[29] Johnson, T.; Robertson, N.; Seymour, P. D.; Thomas, R., Directed tree-width, J. Combin. Theory Ser. B, 82, 1, 138-154, (2001) · Zbl 1027.05045
[30] Kanté, M., The rank-width of directed graphs, (March 2008)
[31] Kanté, M.; Rao, M., The rank-width of edge-coloured graphs, Theory Comput. Syst., 52, 4, 599-644, (2013) · Zbl 1269.05036
[32] Karp, R.; Lipton, R., Some connections between nonuniform and uniform complexity classes, (STOC’80, (1980), ACM), 302-309
[33] Kim, I.; Seymour, P. D., Tournament minors, J. Combin. Theory Ser. B, 112, 138-153, (2015) · Zbl 1310.05109
[34] Kintali, S.; Zhang, Q., Forbidden directed minors and kelly-width, (August 2013)
[35] Kreutzer, S.; Tazari, S., Lower bounds for the complexity of monadic second-order logic, (LICS’10, (2010), IEEE), 189-198
[36] Kreutzer, S.; Tazari, S., Directed nowhere dense classes of graphs, (SODA’12, (2012), SIAM), 1552-1562
[37] Lampis, M.; Kaouri, G.; Mitsou, V., On the algorithmic effectiveness of digraph decompositions and complexity measures, (ISAAC, Lecture Notes in Comput. Sci., vol. 5369, (2008), Springer), 220-231 · Zbl 1183.68312
[38] Mader, W., On topological tournaments of order 4 in digraphs of outdegree 3, J. Graph Theory, 21, 4, 371-376, (1996) · Zbl 0846.05035
[39] Makowsky, J. A.; Mariño, J., Tree-width and the monadic quantifier hierarchy, Theoret. Comput. Sci., 303, 1, 157-170, (2003) · Zbl 1044.68130
[40] Obdržálek, J., DAG-width—connectivity measure for directed graphs, (SODA’06, (2006), ACM-SIAM), 814-821 · Zbl 1192.05065
[41] Oum, S.; Seymour, P. D., Approximating clique-width and branch-width, J. Combin. Theory Ser. B, 96, 4, 514-528, (2006) · Zbl 1114.05022
[42] Rabin, M. O., A simple method for undecidability proofs and some applications, (Bar-Hillel, Y., Logic, Methodology and Philosophy of Sciences, vol. 1, (1964), North-Holland Amsterdam), 58-68
[43] Robertson, N.; Seymour, P. D., Graph minors. II. algorithmic aspects of tree-width, J. Algorithms, 7, 3, 309-322, (1986) · Zbl 0611.05017
[44] Robertson, N.; Seymour, P. D., Graph minors. X. obstructions to tree-decomposition, J. Combin. Theory Ser. B, 52, 2, 153-190, (1991) · Zbl 0764.05069
[45] Robertson, N.; Seymour, P. D.; Thomas, R., Quickly excluding a planar graph, J. Combin. Theory Ser. B, 62, 323-348, (1994) · Zbl 0807.05023
[46] Safari, M., D-width: a more natural measure for directed tree-width, (MFCS’05, Lecture Notes in Comput. Sci., vol. 3618, (2005), Springer), 745-756 · Zbl 1156.05304
[47] Seymour, P. D.; Thomas, R., Graph searching and a MIN-MAX theorem for tree-width, J. Combin. Theory Ser. B, 58, 1, 22-33, (1993) · Zbl 0795.05110
[48] Slivkins, A., Parameterized tractability of edge-disjoint paths on directed acyclic graphs, (ESA’03, Lecture Notes in Comput. Sci., vol. 2832, (2003), Springer), 482-493 · Zbl 1266.68121
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.