Show simple item record

dc.contributor.authorOliveira, Mateus De Oliveira
dc.date.accessioned2022-04-26T07:07:05Z
dc.date.available2022-04-26T07:07:05Z
dc.date.created2022-02-14T01:40:41Z
dc.date.issued2021
dc.identifier.issn1860-5974
dc.identifier.urihttps://hdl.handle.net/11250/2992661
dc.description.abstractLet 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.isoengen_US
dc.publisherLogical Methods in Computer Scienceen_US
dc.rightsNavngivelse 4.0 Internasjonal*
dc.rights.urihttp://creativecommons.org/licenses/by/4.0/deed.no*
dc.titleOn Supergraphs Satisfying CMSO Propertiesen_US
dc.typeJournal articleen_US
dc.typePeer revieweden_US
dc.description.versionpublishedVersionen_US
dc.rights.holderCopyright 2021 the authoren_US
cristin.ispublishedtrue
cristin.fulltextoriginal
cristin.qualitycode1
dc.identifier.doi10.46298/LMCS-17(4:14)2021
dc.identifier.cristin2001118
dc.source.journalLogical Methods in Computer Scienceen_US
dc.source.pagenumber14:1-14:22en_US
dc.identifier.citationLogical Methods in Computer Science. 2021, 17 (4), 14:1-14:22.en_US
dc.source.volume17en_US
dc.source.issue4en_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record

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