Show simple item record

dc.contributor.authorFomin, Fedor
dc.contributor.authorGolovach, Petr
dc.contributor.authorLokshtanov, Daniel
dc.contributor.authorPanolan, Fahad
dc.contributor.authorSaurabh, Saket
dc.contributor.authorZehavi, Meirav
dc.PublishedLeibniz International Proceedings in Informatics. 2020, 151 39:1-39:13.
dc.description.abstractParameterization above a guarantee is a successful paradigm in Parameterized Complexity. To the best of our knowledge, all fixed-parameter tractable problems in this paradigm share an additive form defined as follows. Given an instance (I,k) of some (parameterized) problem Π with a guarantee g(I), decide whether I admits a solution of size at least (at most) k+g(I). Here, g(I) is usually a lower bound (resp. upper bound) on the maximum (resp. minimum) size of a solution. Since its introduction in 1999 for Max SAT and Max Cut (with g(I) being half the number of clauses and half the number of edges, respectively, in the input), analysis of parameterization above a guarantee has become a very active and fruitful topic of research. We highlight a multiplicative form of parameterization above a guarantee: Given an instance (I,k) of some (parameterized) problem Π with a guarantee g(I), decide whether I admits a solution of size at least (resp. at most) k ⋅ g(I). In particular, we study the Long Cycle problem with a multiplicative parameterization above the girth g(I) of the input graph, and provide a parameterized algorithm for this problem. Apart from being of independent interest, this exemplifies how parameterization above a multiplicative guarantee can arise naturally. We also show that, for any fixed constant ε>0, multiplicative parameterization above g(I)^(1+ε) of Long Cycle yields para-NP-hardness, thus our parameterization is tight in this sense. We complement our main result with the design (or refutation of the existence) of algorithms for other problems parameterized multiplicatively above girth.en_US
dc.publisherDagstuhl publishingen_US
dc.rightsNavngivelse 4.0 Internasjonal*
dc.titleParameterization Above a Multiplicative Guaranteeen_US
dc.typeJournal articleen_US
dc.typePeer revieweden_US
dc.rights.holderCopyright 2020 The Authorsen_US
dc.source.journalLeibniz International Proceedings in Informaticsen_US
dc.relation.projectNorges forskningsråd: 263317en_US
dc.identifier.citationLeibniz International Proceedings in Informatics. 2020, 39, 39:1–39:13en_US

Files in this item


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