License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2016.69
URN: urn:nbn:de:0030-drops-64114
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6411/
Go to the corresponding LIPIcs Volume Portal

Nederlof, Jesper

Finding Large Set Covers Faster via the Representation Method

pdf-format:
LIPIcs-ESA-2016-69.pdf (0.5 MB)

Abstract

The worst-case fastest known algorithm for the Set Cover problem on universes with n elements still essentially is the simple O^*(2^n)-time dynamic programming algorithm, and no non-trivial consequences of an O^*(1.01^n)-time algorithm are known. Motivated by this chasm, we study the following natural question: Which instances of Set Cover can we solve faster than the simple dynamic programming algorithm? Specifically, we give a Monte Carlo algorithm that determines the existence of a set cover of size sigma*n in O^*(2^{(1-Omega(sigma^4))n}) time. Our approach is also applicable to Set Cover instances with exponentially many sets: By reducing the task of finding the chromatic number chi(G) of a given n-vertex graph G to Set Cover in the natural way, we show there is an O^*(2^{(1-Omega(sigma^4))n})-time randomized algorithm that given integer s = sigma*n, outputs NO if chi(G) > s and YES with constant probability if \chi(G) <= s - 1.

On a high level, our results are inspired by the "representation method" of Howgrave-Graham and Joux~[EUROCRYPT'10] and obtained by only evaluating a randomly sampled subset of the table entries of a dynamic programming algorithm.

BibTeX - Entry

@InProceedings{nederlof:LIPIcs:2016:6411,
  author =	{Jesper Nederlof},
  title =	{{Finding Large Set Covers Faster via the Representation Method}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{69:1--69:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Piotr Sankowski and Christos Zaroliagis},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6411},
  URN =		{urn:nbn:de:0030-drops-64114},
  doi =		{10.4230/LIPIcs.ESA.2016.69},
  annote =	{Keywords: Set Cover, Exact Exponential Algorithms, Fine-Grained Complexity}
}

Keywords: Set Cover, Exact Exponential Algorithms, Fine-Grained Complexity
Collection: 24th Annual European Symposium on Algorithms (ESA 2016)
Issue Date: 2016
Date of publication: 18.08.2016

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