Nederlof, Jesper
Finding Large Set Covers Faster via the Representation Method
Abstract
The worstcase 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 nontrivial 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^{(1Omega(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 nvertex graph G to Set Cover in the natural way, we show there is an O^*(2^{(1Omega(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 HowgraveGraham 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:169:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770156},
ISSN = {18688969},
year = {2016},
volume = {57},
editor = {Piotr Sankowski and Christos Zaroliagis},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6411},
URN = {urn:nbn:de:0030drops64114},
doi = {10.4230/LIPIcs.ESA.2016.69},
annote = {Keywords: Set Cover, Exact Exponential Algorithms, FineGrained Complexity}
}
18.08.2016
Keywords: 

Set Cover, Exact Exponential Algorithms, FineGrained Complexity 
Seminar: 

24th Annual European Symposium on Algorithms (ESA 2016)

Issue date: 

2016 
Date of publication: 

18.08.2016 