Skip to main content
SpringerLink
Log in

When Trees Grow Low: Shrubs and Fast MSO1

  • Conference paper
Mathematical Foundations of Computer Science 2012 (MFCS 2012)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 7464))

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

Log in via an institution
Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 89.00
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 119.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. 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)

    Chapter  Google Scholar 

  2. Courcelle, B.: The monadic second order logic of graphs I: Recognizable sets of finite graphs. Inform. and Comput. 85, 12–75 (1990)

    Article  MathSciNet  MATH  Google Scholar 

  3. 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)

    Article  MathSciNet  MATH  Google Scholar 

  4. Courcelle, B., Olariu, S.: Upper bounds to the clique width of graphs. Discrete Appl. Math. 101(1-3), 77–114 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  5. 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)

    Chapter  Google Scholar 

  6. 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)

    Chapter  Google Scholar 

  7. 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)

    Article  MathSciNet  MATH  Google Scholar 

  8. Gajarský, J.: Efficient solvability of graph MSO properties. Master’s thesis, Masaryk University, Brno (2012)

    Google Scholar 

  9. Gajarský, J., Hliněný, P.: Deciding graph MSO properties: Has it all been told already (submitted, 2012)

    Google Scholar 

  10. 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)

    Chapter  Google Scholar 

  11. 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)

    Google Scholar 

  12. 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)

    Article  MathSciNet  MATH  Google Scholar 

  13. Giakoumakis, V., Vanherpe, J.-M.: Bi-complement reducible graphs. Adv. Appl. Math. 18, 389–402 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  14. Hung, L.-J., Kloks, T.: k-cographs are Kruskalian. Chic. J. Theoret. Comput. Sci. 2011, 1–11 (2011)

    MathSciNet  Google Scholar 

  15. 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)

    Chapter  Google Scholar 

  16. Nešetřil, J., Ossona de Mendez, P.: Tree-depth, subgraph coloring and homomorphism bounds. European J. Combin. 27(6), 1024–1041 (2006)

    Google Scholar 

  17. Nešetřil, J., Ossona de Mendez, P.: Grad and classes with bounded expansion I. Decompositions. European J. Combin. 29(3), 760–776 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  18. Nešetřil, J., Ossona de Mendez, P.: Sparsity (Graphs, Structures, and Algorithms) Algorithms and Combinatorics, vol. 28, p. 465. Springer (2012)

    Google Scholar 

  19. 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)

    Google Scholar 

  20. Schaffer, P.: Optimal node ranking of trees in linear time. Inform. Process. Lett. 33, 91–96 (1989/1990)

    Google Scholar 

  21. Wanke, E.: k-NLC graphs and polynomial algorithms. Discrete Appl. Math. 54, 251–266 (1994)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institute for Informatics, Goethe University, Frankfurt, Germany

    Robert Ganian

  2. Faculty of Informatics, Masaryk University, Brno, Czech Republic

    Petr Hliněný, Jan Obdržálek & Reshma Ramadurai

  3. Computer Science Inst. of Charles University (IUUK), Praha, Czech Republic

    Jaroslav Nešetřil

  4. École des Hautes Études en Sciences Sociales, CNRS UMR 8557, Paris, France

    Patrice Ossona de Mendez

Authors
  1. Robert Ganian
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Petr Hliněný
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Jaroslav Nešetřil
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Jan Obdržálek
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Patrice Ossona de Mendez
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Reshma Ramadurai
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Computer Science, Comenius University, Mlynska Dolina, 84248, Bratislava, Slovakia

    Branislav Rovan

  2. Department of Electronics and Computer Science, University of Southampton, SO17 1BJ, Southampton, UK

    Vladimiro Sassone

  3. Institute of Theoretical Computer Science, ETH Zürich, CAB H 39.2, Universitätstrasse 6, 8092, Zürich, Switzerland

    Peter Widmayer

Rights and permissions

Reprints 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)

Publish with us

Policies and ethics

Search

Navigation