Definability equals recognizability for κ-outerplanar graphs

Lars Jaffke; Hans L. Bodlaender

doi:10.4230/LIPIcs.IPEC.2015.175

Definability equals recognizability for κ-outerplanar graphs

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

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 [6]. 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 κ-outerplanar graphs, which are known to have treewidth at most 3κ - 1 [2].

Original language	English
Title of host publication	Leibniz International Proceedings in Informatics, LIPIcs
Publisher	Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Pages	176-186
Number of pages	11
Volume	43
ISBN (Print)	9783939897927
DOIs	https://doi.org/10.4230/LIPIcs.IPEC.2015.175
Publication status	Published - 1 Nov 2015
Event	10th International Symposium on Parameterized and Exact Computation, IPEC 2015 - Patras, Greece Duration: 16 Sept 2015 → 18 Sept 2015

Conference

Conference	10th International Symposium on Parameterized and Exact Computation, IPEC 2015
Country/Territory	Greece
City	Patras
Period	16/09/15 → 18/09/15

Keywords

Finite state tree automata
Monadic second order logic of graphs
Treewidth
κ-outerplanar graphs

Access to Document

10.4230/LIPIcs.IPEC.2015.175Licence: CC BY

Cite this

@inproceedings{f5650216c05c48688efb85e83e8da921,

title = "Definability equals recognizability for κ-outerplanar graphs",

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 [6]. 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 κ-outerplanar graphs, which are known to have treewidth at most 3κ - 1 [2].",

keywords = "Finite state tree automata, Monadic second order logic of graphs, Treewidth, κ-outerplanar graphs",

author = "Lars Jaffke and Bodlaender, {Hans L.}",

year = "2015",

month = nov,

day = "1",

doi = "10.4230/LIPIcs.IPEC.2015.175",

language = "English",

isbn = "9783939897927",

volume = "43",

pages = "176--186",

booktitle = "Leibniz International Proceedings in Informatics, LIPIcs",

publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",

address = "Germany",

note = "10th International Symposium on Parameterized and Exact Computation, IPEC 2015 ; Conference date: 16-09-2015 Through 18-09-2015",

}

Jaffke, L & Bodlaender, HL 2015, Definability equals recognizability for κ-outerplanar graphs. in Leibniz International Proceedings in Informatics, LIPIcs. vol. 43, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, pp. 176-186, 10th International Symposium on Parameterized and Exact Computation, IPEC 2015, Patras, Greece, 16/09/15. https://doi.org/10.4230/LIPIcs.IPEC.2015.175

Definability equals recognizability for κ-outerplanar graphs. / Jaffke, Lars; Bodlaender, Hans L.
Leibniz International Proceedings in Informatics, LIPIcs. Vol. 43 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2015. p. 176-186.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Definability equals recognizability for κ-outerplanar graphs

AU - Jaffke, Lars

AU - Bodlaender, Hans L.

PY - 2015/11/1

Y1 - 2015/11/1

N2 - 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 [6]. 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 κ-outerplanar graphs, which are known to have treewidth at most 3κ - 1 [2].

AB - 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 [6]. 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 κ-outerplanar graphs, which are known to have treewidth at most 3κ - 1 [2].

KW - Finite state tree automata

KW - Monadic second order logic of graphs

KW - Treewidth

KW - κ-outerplanar graphs

UR - http://www.scopus.com/inward/record.url?scp=84958248283&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.IPEC.2015.175

DO - 10.4230/LIPIcs.IPEC.2015.175

M3 - Conference contribution

AN - SCOPUS:84958248283

SN - 9783939897927

VL - 43

SP - 176

EP - 186

BT - Leibniz International Proceedings in Informatics, LIPIcs

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 10th International Symposium on Parameterized and Exact Computation, IPEC 2015

Y2 - 16 September 2015 through 18 September 2015

ER -

Definability equals recognizability for κ-outerplanar graphs

Abstract

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this