Lin, Bingkai
A Simple GapProducing Reduction for the Parameterized Set Cover Problem
Abstract
Given an nvertex bipartite graph I=(S,U,E), the goal of set cover problem is to find a minimum sized subset of S such that every vertex in U is adjacent to some vertex of this subset. It is NPhard to approximate set cover to within a (1o(1))ln n factor [I. Dinur and D. Steurer, 2014]. If we use the size of the optimum solution k as the parameter, then it can be solved in n^{k+o(1)} time [Eisenbrand and Grandoni, 2004]. A natural question is: can we approximate set cover to within an o(ln n) factor in n^{kepsilon} time?
In a recent breakthrough result[Karthik et al., 2018], Karthik, Laekhanukit and Manurangsi showed that assuming the Strong Exponential Time Hypothesis (SETH), for any computable function f, no f(k)* n^{kepsilon}time algorithm can approximate set cover to a factor below (log n)^{1/poly(k,e(epsilon))} for some function e.
This paper presents a simple gapproducing reduction which, given a set cover instance I=(S,U,E) and two integers k<h <=(1o(1))sqrt[k]{log S/log log S}, outputs a new set cover instance I'=(S,U',E') with U'=U^{h^k}S^{O(1)} in U^{h^k}* S^{O(1)} time such that
 if I has a ksized solution, then so does I';
 if I has no ksized solution, then every solution of I' must contain at least h vertices.
Setting h=(1o(1))sqrt[k]{log S/log log S}, we show that assuming SETH, for any computable function f, no f(k)* n^{kepsilon}time algorithm can distinguish between a set cover instance with ksized solution and one whose minimum solution size is at least (1o(1))* sqrt[k]((log n)/(log log n)). This improves the result in [Karthik et al., 2018].
BibTeX  Entry
@InProceedings{lin:LIPIcs:2019:10657,
author = {Bingkai Lin},
title = {{A Simple GapProducing Reduction for the Parameterized Set Cover Problem}},
booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
pages = {81:181:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771092},
ISSN = {18688969},
year = {2019},
volume = {132},
editor = {Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10657},
URN = {urn:nbn:de:0030drops106573},
doi = {10.4230/LIPIcs.ICALP.2019.81},
annote = {Keywords: set cover, FPT inapproximability, gapproducing reduction, (n, k)universal set}
}
2019
Keywords: 

set cover, FPT inapproximability, gapproducing reduction, (n, k)universal set 
Seminar: 

46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Issue date: 

2019 
Date of publication: 

2019 