Header menu link for other important links
X
Multiplicative Parameterization above a Guarantee
F.V. Fomin, P.A. Golovach, D. Lokshtanov, , S. Saurabh, M. Zehavi
Published in Association for Computing Machinery
2021
Volume: 13
   
Issue: 3
Abstract
Parameterization 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 (or at most) k + g(I). Here, g(I) is usually a lower bound on the 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 (or, rather, times) 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 (or 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, which is the most natural guarantee for this problem, and provide a fixed-parameter algorithm. 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 fixed-parameter algorithms as well as kernelization algorithms for additional problems parameterized multiplicatively above girth. © 2021 ACM.
About the journal
JournalData powered by TypesetACM Transactions on Computation Theory
PublisherData powered by TypesetAssociation for Computing Machinery
ISSN19423454