2026-10-19T05:43:24Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6411 2024-03-06T09:38:12Z ddc:004 open_access

Finding Large Set Covers Faster via the Representation Method Nederlof, Jesper Set Cover Exact Exponential Algorithms Fine-Grained Complexity 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jesper Nederlof 2016 Is Part Of LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2016.69 urn:nbn:de:0030-drops-64114 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.69 eng https://creativecommons.org/licenses/by/3.0/legalcode