dc.contributor.author Oliveira, Mateus De Oliveira dc.date.accessioned 2022-04-26T07:07:05Z dc.date.available 2022-04-26T07:07:05Z dc.date.created 2022-02-14T01:40:41Z dc.date.issued 2021 dc.identifier.issn 1860-5974 dc.identifier.uri https://hdl.handle.net/11250/2992661 dc.description.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 φ, a positive integer t, and a connected graph G of maximum degree at most Δ, and determines, in time f(|φ|,t)⋅2O(Δ⋅t)⋅|G|O(t), whether G has a supergraph G′ of treewidth at most t such that G′⊨φ. 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)⋅2O(Δ⋅d)⋅|G|O(d), whether a connected graph of maximum degree Δ has a planar supergraph of diameter at most d. Additionally, we show that for each fixed k, the problem of determining whether G has an k-outerplanar 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 contraction-closed effectively CMSO-definable parameter p. Examples of such parameters are vertex-cover number, dominating number, and many other contraction-bidimensional parameters. In the second direction, the planarity requirement can be relaxed to bounded genus, and more generally, to bounded local treewidth. en_US dc.language.iso eng en_US dc.publisher Logical Methods in Computer Science en_US dc.rights Navngivelse 4.0 Internasjonal * dc.rights.uri http://creativecommons.org/licenses/by/4.0/deed.no * dc.title On Supergraphs Satisfying CMSO Properties en_US dc.type Journal article en_US dc.type Peer reviewed en_US dc.description.version publishedVersion en_US dc.rights.holder Copyright 2021 the author en_US cristin.ispublished true cristin.fulltext original cristin.qualitycode 1 dc.identifier.doi 10.46298/LMCS-17(4:14)2021 dc.identifier.cristin 2001118 dc.source.journal Logical Methods in Computer Science en_US dc.source.pagenumber 14:1-14:22 en_US dc.identifier.citation Logical Methods in Computer Science. 2021, 17 (4), 14:1-14:22. en_US dc.source.volume 17 en_US dc.source.issue 4 en_US
﻿

### This item appears in the following Collection(s)

Except where otherwise noted, this item's license is described as Navngivelse 4.0 Internasjonal