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

L. Jaffke, H.L. Bodlaender

Research output: Book/ReportReportAcademic

21 Downloads (Pure)

Abstract

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.
Original languageEnglish
Publishers.n.
Number of pages39
Publication statusPublished - 2015

Publication series

NamearXiv
Volume1503.01604 [cs.LO]

Bibliographical note

39 pages, 9 figures

Keywords

  • cs.LO
  • math.CO

Fingerprint Dive into the research topics of 'MSOL-definability equals recognizability for Halin graphs and bounded degree $k$-outerplanar graphs'. Together they form a unique fingerprint.

  • Cite this