Parameterized Inapproximability of Exact Cover and Nearest Codeword
share
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 1/4√( N/ 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) · N^k - ε, 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 ∈F_2^m × n, a vector y ∈F_2^m, 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 1/8√( N/ N) from y. This improves the best known parameterized inapproximability result, which rules out approximations with a factor of poly ( k), but requires us to assume ETH instead of W[1] ≠ FPT.
READ FULL TEXT