Abstract
Recent characterization [9] of those graphs for which coloured MSO2 model checking is fast raised the interest in the graph invariant called tree-depth. Looking for a similar characterization for (coloured) MSO1, we introduce the notion of shrub-depth of a graph class. To prove that MSO1 model checking is fast for classes of bounded shrub-depth, we show that shrub-depth exactly characterizes the graph classes having interpretation in coloured trees of bounded height. We also introduce a common extension of cographs and of graphs with bounded shrub-depth — m-partite cographs (still of bounded clique-width), which are well quasi-ordered by the relation “is an induced subgraph of” and therefore allow polynomial time testing of hereditary properties.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bodlaender, H., Deogun, J., Jansen, K., Kloks, T., Kratsch, D., Müller, H., Tuza, Z.: Rankings of Graphs. In: Mayr, E.W., Schmidt, G., Tinhofer, G. (eds.) WG 1994. LNCS, vol. 903, pp. 292–304. Springer, Heidelberg (1995)
Courcelle, B.: The monadic second order logic of graphs I: Recognizable sets of finite graphs. Inform. and Comput. 85, 12–75 (1990)
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)
Courcelle, B., Olariu, S.: Upper bounds to the clique width of graphs. Discrete Appl. Math. 101(1-3), 77–114 (2000)
Deogun, J., Kloks, T., Kratsch, D., Muller, H.: On Vertex Ranking for Permutation and Other Graphs. In: Enjalbert, P., Mayr, E.W., Wagner, K.W. (eds.) STACS 1994. LNCS, vol. 775, pp. 747–758. Springer, Heidelberg (1994)
Espelage, W., Gurski, F., Wanke, E.: How to solve NP-hard graph problems on clique-width bounded graphs in polynomial time. In: Brandstädt, A., Van Le, B. (eds.) WG 2001. LNCS, vol. 2204, pp. 117–128. Springer, Heidelberg (2001)
Frick, M., Grohe, M.: The complexity of first-order and monadic second-order logic revisited. Ann. Pure Appl. Logic 130(1-3), 3–31 (2004)
Gajarský, J.: Efficient solvability of graph MSO properties. Master’s thesis, Masaryk University, Brno (2012)
Gajarský, J., Hliněný, P.: Deciding graph MSO properties: Has it all been told already (submitted, 2012)
Ganian, R.: Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics. In: Marx, D., Rossmanith, P. (eds.) IPEC 2011. LNCS, vol. 7112, pp. 259–271. Springer, Heidelberg (2012)
Ganian, R., Hliněný, P., Obdržálek, J.: Clique-width: When hard does not mean impossible. In: STACS 2011. LIPIcs, vol. 9, pp. 404–415. Dagstuhl Publishing (2011)
Gerber, M.U., Kobler, D.: Algorithms for vertex-partitioning problems on graphs with fixed clique-width. Theoret. Comput. Sci. 299(1-3), 719–734 (2003)
Giakoumakis, V., Vanherpe, J.-M.: Bi-complement reducible graphs. Adv. Appl. Math. 18, 389–402 (1997)
Hung, L.-J., Kloks, T.: k-cographs are Kruskalian. Chic. J. Theoret. Comput. Sci. 2011, 1–11 (2011)
Lampis, M.: Algorithmic Meta-theorems for Restrictions of Treewidth. In: de Berg, M., Meyer, U. (eds.) ESA 2010. LNCS, vol. 6346, pp. 549–560. Springer, Heidelberg (2010)
Nešetřil, J., Ossona de Mendez, P.: Tree-depth, subgraph coloring and homomorphism bounds. European J. Combin. 27(6), 1024–1041 (2006)
Nešetřil, J., Ossona de Mendez, P.: Grad and classes with bounded expansion I. Decompositions. European J. Combin. 29(3), 760–776 (2008)
Nešetřil, J., Ossona de Mendez, P.: Sparsity (Graphs, Structures, and Algorithms) Algorithms and Combinatorics, vol. 28, p. 465. Springer (2012)
Rabin, M.O.: A simple method for undecidability proofs and some applications. In: Bar-Hillel, Y. (ed.) Logic, Methodology and Philosophy of Sciences, vol. 1, pp. 58–68. North-Holland, Amsterdam (1964)
Schaffer, P.: Optimal node ranking of trees in linear time. Inform. Process. Lett. 33, 91–96 (1989/1990)
Wanke, E.: k-NLC graphs and polynomial algorithms. Discrete Appl. Math. 54, 251–266 (1994)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ganian, R., Hliněný, P., Nešetřil, J., Obdržálek, J., Ossona de Mendez, P., Ramadurai, R. (2012). When Trees Grow Low: Shrubs and Fast MSO1 . In: Rovan, B., Sassone, V., Widmayer, P. (eds) Mathematical Foundations of Computer Science 2012. MFCS 2012. Lecture Notes in Computer Science, vol 7464. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-32589-2_38
Download citation
DOI: https://doi.org/10.1007/978-3-642-32589-2_38
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-32588-5
Online ISBN: 978-3-642-32589-2
eBook Packages: Computer ScienceComputer Science (R0)