Fomin, Fedor V. ;
Golovach, Petr A. ;
Lokshtanov, Daniel ;
Panolan, Fahad ;
Saurabh, Saket ;
Zehavi, Meirav
Parameterization Above a Multiplicative Guarantee
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 (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 paraNPhardness, 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.
BibTeX  Entry
@InProceedings{fomin_et_al:LIPIcs:2020:11724,
author = {Fedor V. Fomin and Petr A. Golovach and Daniel Lokshtanov and Fahad Panolan and Saket Saurabh and Meirav Zehavi},
title = {{Parameterization Above a Multiplicative Guarantee}},
booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
pages = {39:139:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771344},
ISSN = {18688969},
year = {2020},
volume = {151},
editor = {Thomas Vidick},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/11724},
URN = {urn:nbn:de:0030drops117248},
doi = {10.4230/LIPIcs.ITCS.2020.39},
annote = {Keywords: Parameterized Complexity, AboveGuarantee Parameterization, Girth}
}
06.01.2020
Keywords: 

Parameterized Complexity, AboveGuarantee Parameterization, Girth 
Seminar: 

11th Innovations in Theoretical Computer Science Conference (ITCS 2020)

Issue date: 

2020 
Date of publication: 

06.01.2020 