MSOL-definability equals recognizability for Halin graphs and bounded degree $k$-outerplanar graphs

L. Jaffke, H.L. Bodlaender

Onderzoeksoutput: Boek/rapportRapportAcademic

26 Downloads (Pure)

Samenvatting

One of the most famous algorithmic meta-theorems states that every graph property that can be defined by a sentence in counting monadic second order logic (CMSOL) can be checked in linear time for graphs of bounded treewidth, which is known as Courcelle's Theorem. These algorithms are constructed as finite state tree automata, and hence every CMSOL-definable graph property is recognizable. Courcelle also conjectured that the converse holds, i.e. every recognizable graph property is definable in CMSOL for graphs of bounded treewidth. We prove this conjecture for a number of special cases in a stronger form. That is, we show that each recognizable property is definable in MSOL, i.e. the counting operation is not needed in our expressions. We give proofs for Halin graphs, bounded degree $k$-outerplanar graphs and some related graph classes. We furthermore show that the conjecture holds for any graph class that admits tree decompositions that can be defined in MSOL, thus providing a useful tool for future proofs.
Originele taal-2Engels
Uitgeverijs.n.
Aantal pagina's39
StatusGepubliceerd - 2015

Publicatie series

NaamarXiv
Volume1503.01604 [cs.LO]

Bibliografische nota

39 pages, 9 figures

Vingerafdruk Duik in de onderzoeksthema's van 'MSOL-definability equals recognizability for Halin graphs and bounded degree $k$-outerplanar graphs'. Samen vormen ze een unieke vingerafdruk.

Citeer dit