The Library
Reducing CMSO model checking to highly connected graphs
Tools
Lokshtanov, Daniel, Ramanujan, Maadapuzhi Sridharan, Saurabh, Saket and Zehavi, Meirav (2018) Reducing CMSO model checking to highly connected graphs. In: 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), Prague, 13 Jul 2018. Published in: 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), 107 135:1-135:14. ISBN 9783959770767. doi:10.4230/LIPIcs.ICALP.2018.135
|
PDF
WRAP-reducing-CMSO-model-checking-highly-graphs-Ramnujan-2018.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (542Kb) | Preview |
Official URL: https://doi.org/10.4230/LIPIcs.ICALP.2018.135
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.
Item Type: | Conference Item (Paper) | ||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||||||||
Library of Congress Subject Headings (LCSH): | Computer algorithms, Logic, Symbolic and mathematical -- Graphic methods | ||||||||||||
Journal or Publication Title: | 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) | ||||||||||||
Publisher: | Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik | ||||||||||||
ISBN: | 9783959770767 | ||||||||||||
Editor: | Chatzigiannakis, Ioannis and Kaklamanis , Christos and Marx, Daniel and Sannella, Donald | ||||||||||||
Official Date: | 9 July 2018 | ||||||||||||
Dates: |
|
||||||||||||
Volume: | 107 | ||||||||||||
Page Range: | 135:1-135:14 | ||||||||||||
DOI: | 10.4230/LIPIcs.ICALP.2018.135 | ||||||||||||
Status: | Peer Reviewed | ||||||||||||
Publication Status: | Published | ||||||||||||
Access rights to Published version: | Open Access (Creative Commons) | ||||||||||||
Date of first compliant deposit: | 10 September 2018 | ||||||||||||
Date of first compliant Open Access: | 10 September 2018 | ||||||||||||
RIOXX Funder/Project Grant: |
|
||||||||||||
Conference Paper Type: | Paper | ||||||||||||
Title of Event: | 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) | ||||||||||||
Type of Event: | Conference | ||||||||||||
Location of Event: | Prague | ||||||||||||
Date(s) of Event: | 13 Jul 2018 | ||||||||||||
Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year