When Trees Grow Low: Shrubs and Fast MSO1

Investor logo

Warning

This publication doesn't include Faculty of Arts. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

GANIAN Robert HLINĚNÝ Petr OBDRŽÁLEK Jan NEŠETŘIL Jaroslav OSSONA DE MENDEZ Patrice RAMADURAI Reshma

Year of publication 2012
Type Article in Proceedings
Conference Math Foundations of Computer Science MFCS 2012
MU Faculty or unit

Faculty of Informatics

Citation
Doi http://dx.doi.org/10.1007/978-3-642-32589-2_38
Field Informatics
Keywords tree-depth; shrub-depth; MSO model checking
Description 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.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.