de Oliveira Oliveira, Mateus
On Supergraphs Satisfying CMSO Properties
Abstract
Let CMSO denote the counting monadic second order logic of graphs. We give a constructive proof that for some computable function f, there is an algorithm A that takes as input a CMSO sentence F, a positive integer t, and a connected graph G of maximum degree at most D, and determines, in time f(F,t)*2^O(D*t)*G^O(t), whether G has a supergraph G' of treewidth at most t such that G' satisfies F.
The algorithmic metatheorem described above sheds new light on certain unresolved questions within the framework of graph completion algorithms. In particular, using this metatheorem, we provide an explicit algorithm that determines, in time f(d)*2^O(D*d)*G^O(d), whether a connected graph of maximum degree D has a planar supergraph of diameter at most d. Additionally, we show that for each fixed k, the problem of determining whether G has a kouterplanar supergraph of diameter at most d is strongly uniformly fixed parameter tractable with respect to the parameter d.
This result can be generalized in two directions. First, the diameter parameter can be replaced by any contractionclosed effectively CMSOdefinable parameter p. Examples of such parameters are vertexcover number, dominating number, and many other contractionbidimensional parameters. In the second direction, the planarity requirement can be relaxed to bounded genus, and more generally, to bounded local treewidth.
BibTeX  Entry
@InProceedings{deoliveiraoliveira:LIPIcs:2017:7705,
author = {Mateus de Oliveira Oliveira},
title = {{On Supergraphs Satisfying CMSO Properties}},
booktitle = {26th EACSL Annual Conference on Computer Science Logic (CSL 2017)},
pages = {33:133:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770453},
ISSN = {18688969},
year = {2017},
volume = {82},
editor = {Valentin Goranko and Mads Dam},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7705},
URN = {urn:nbn:de:0030drops77058},
doi = {10.4230/LIPIcs.CSL.2017.33},
annote = {Keywords: On Supergraphs Satisfying CMSO Properties}
}
16.08.2017
Keywords: 

On Supergraphs Satisfying CMSO Properties 
Seminar: 

26th EACSL Annual Conference on Computer Science Logic (CSL 2017)

Issue date: 

2017 
Date of publication: 

16.08.2017 