2019/05/16 by Venkatesan Guruswami, Guruswami, Venkatesan, Patrick Lin +1
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Machine Learning and Algorithms
paper · pdf · doi:10.48550/arxiv.1905.06503
openalex publication_date 2019/05/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The k-ExactCover problem is a parameterized version of the ExactCover problem, in which we are given a universe U, a collection S of subsets of U, and an integer k, and the task is to determine whether U can be partitioned into k sets in S. This is a natural extension of the well-studied SetCover problem; though in the parameterized regime we know it to be W[1]-complete in the exact case, its parameterized complexity with respect to approximability is not well understood. We prove that, assuming ETH, for some γ> 0 there is no time f(k) ⋅ Nγk algorithm that can, given a k-ExactCover instance I, distinguish between the case where I has an exact cover of size k and the case where every set cover of I has size at least \frac14 √[k](log N)/(log log N). This rules out even more than FPT algorithms, and additionally rules out any algorithm whose approximation ratio depends only on the parameter k. By assuming SETH, we instead improve the lower bound to requiring time f(k) ⋅ Nk - ε, for any ε > 0. In this work we also extend the inapproximability result to the k-Nearest-Codeword (k-NCP) problem. Specifically, given a generator matrix A ∈ \mathbbF2m × n, a vector y ∈ \mathbbF2m, and the parameter k, we show that it is hard to distinguish between the case where there exists a codeword with distance at most k from y and the case where every codeword has distance at least \frac18 √[k](log N)/(log log N) from y. This improves the best known parameterized inapproximability result, which rules out approximations with a factor of poly (log k), but requires us to assume ETH instead of W[1] ≠ FPT.