License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2018.135
URN: urn:nbn:de:0030-drops-91391
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9139/
Go to the corresponding LIPIcs Volume Portal

Lokshtanov, Daniel ; Ramanujan, M. S. ; Saurabh, Saket ; Zehavi, Meirav

Reducing CMSO Model Checking to Highly Connected Graphs

pdf-format:
LIPIcs-ICALP-2018-135.pdf (0.5 MB)

Abstract

Given a Counting Monadic Second Order (CMSO) sentence psi, the CMSO[psi] problem is defined as follows. The input to CMSO[psi] is a graph G, and the objective is to determine whether G |= psi. Our main theorem states that for every CMSO sentence psi, if CMSO[psi] is solvable in polynomial time on "globally highly connected graphs", then CMSO[psi] is solvable in polynomial time (on general graphs). We demonstrate the utility of our theorem in the design of parameterized algorithms. Specifically we show that technical problem-specific ingredients of a powerful method for designing parameterized algorithms, recursive understanding, can be replaced by a black-box invocation of our main theorem. We also show that our theorem can be easily deployed to show fixed parameterized tractability of a wide range of problems, where the input is a graph G and the task is to find a connected induced subgraph of G such that "few" vertices in this subgraph have neighbors outside the subgraph, and additionally the subgraph has a CMSO-definable property.

BibTeX - Entry

@InProceedings{lokshtanov_et_al:LIPIcs:2018:9139,
  author =	{Daniel Lokshtanov and M. S. Ramanujan and Saket Saurabh and Meirav Zehavi},
  title =	{{Reducing CMSO Model Checking to Highly Connected Graphs}},
  booktitle =	{45th International Colloquium on Automata, Languages, and  Programming (ICALP 2018)},
  pages =	{135:1--135:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Ioannis Chatzigiannakis and Christos Kaklamanis and D{\'a}niel Marx and Donald Sannella},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9139},
  URN =		{urn:nbn:de:0030-drops-91391},
  doi =		{10.4230/LIPIcs.ICALP.2018.135},
  annote =	{Keywords: Fixed Parameter Tractability Model Checking Recursive Understanding}
}

Keywords: Fixed Parameter Tractability Model Checking Recursive Understanding
Collection: 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Issue Date: 2018
Date of publication: 04.07.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI