License
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2019.81
URN: urn:nbn:de:0030-drops-106573
URL: http://drops.dagstuhl.de/opus/volltexte/2019/10657/
Go to the corresponding LIPIcs Volume Portal


Lin, Bingkai

A Simple Gap-Producing Reduction for the Parameterized Set Cover Problem

pdf-format:
LIPIcs-ICALP-2019-81.pdf (0.5 MB)


Abstract

Given an n-vertex 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 NP-hard to approximate set cover to within a (1-o(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^{k-epsilon} 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^{k-epsilon}-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 gap-producing reduction which, given a set cover instance I=(S,U,E) and two integers k<h <=(1-o(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 k-sized solution, then so does I'; - if I has no k-sized solution, then every solution of I' must contain at least h vertices. Setting h=(1-o(1))sqrt[k]{log |S|/log log |S|}, we show that assuming SETH, for any computable function f, no f(k)* n^{k-epsilon}-time algorithm can distinguish between a set cover instance with k-sized solution and one whose minimum solution size is at least (1-o(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 Gap-Producing Reduction for the Parameterized Set Cover Problem}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{81:1--81:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10657},
  URN =		{urn:nbn:de:0030-drops-106573},
  doi =		{10.4230/LIPIcs.ICALP.2019.81},
  annote =	{Keywords: set cover, FPT inapproximability, gap-producing reduction, (n, k)-universal set}
}

Keywords: set cover, FPT inapproximability, gap-producing reduction, (n, k)-universal set
Seminar: 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Issue Date: 2019
Date of publication: 08.07.2019


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI