Multiplicative Parameterization Above a Guarantee
Fomin, Fedor V. and Golovach, Petr A. and Lokshtanov, Daniel and Panolan, Fahad and et al, . (2021) Multiplicative Parameterization Above a Guarantee. In: ACM Transactions on Computation Theory.
Text
ACM_Transactions.pdf  Published Version Restricted to Registered users only Download (443kB)  Request a copy 
Abstract
Parameterization above a guarantee is a successful paradigm in Parameterized Complexity. To the best of our knowledge, all fixedparameter 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 fixedparameter 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 paraNPhardness, thus our parameterization is tight in this sense. We complement our main result with the design (or refutation of the existence) of fixedparameter algorithms as well as kernelization algorithms for additional problems parameterized multiplicatively above girth. © 2021 ACM.
[error in script]IITH Creators: 



Item Type:  Conference or Workshop Item (Paper)  
Additional Information:  A preliminary version of this paper appeared in the proceedings of ITCS 2020. The research leading to these results has received funding from the Research Council of Norway via the projects “CLASSIS” and “MULTIVAL”, the European Research Council (ERC) via grant LOPPRE, reference 819416, the Swarnajayanti Fellowship grant DST/SJF/MSA01/201718, the Israel Science Foundation (ISF) grant no. 1176/18, the United States – Israel Binational Science Foundation (BSF) grant  
Uncontrolled Keywords:  Aboveguarantee; Girth; Long cycle; Multiplicative aboveguarantee; Parameterized complexity  
Subjects:  Computer science  
Divisions:  Department of Computer Science & Engineering  
Depositing User:  . LibTrainee 2021  
Date Deposited:  09 Sep 2022 07:15  
Last Modified:  09 Sep 2022 07:15  
URI:  http://raiith.iith.ac.in/id/eprint/10507  
Publisher URL:  http://doi.org/10.1145/3460956  
Related URLs: 
Actions (login required)
View Item 
Statistics for this ePrint Item 