{"ID":23475005,"CreatedAt":"2026-09-18T01:09:05.407443952Z","UpdatedAt":"2026-09-20T18:11:56.143995915Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2609.19685","arxiv_id":"2609.19685","title":"Almost Optimal FPT Inapproximability for k-SetCover","abstract":"We show that $\\bigl(\\frac{\\log n}{\\log\\log n}\\bigr)$-approximate parameterized $k$-SetCover is W[1]-hard, and has no $n^{o(k/\\log k)}$-time algorithms under ETH. This improves upon the previous best factors $\\bigl(\\frac{\\log n}{\\log\\log n}\\bigr)^{1/k}$ in (Lin, 2019) and $(\\log n)^{1/\\operatorname{poly}(k)}$ in (Karthik, Laekhanukit, and Manurangsi, 2019). Here $k$ is the yes-case guarantee and $n$ is the number of candidate sets. While the best approximation ratio is still $O(\\log n)$ via the greedy algorithm, closing this $1/k$ gap in the exponent has been a longstanding open problem; we remove this loss via a simple direct reduction. The construction is self-contained and does not rely on the parameterized inapproximability hypothesis (PIH). Starting with sparse parameterized 2-CSP instances (Karthik, Marx, Pilipczuk, and Souza, 2024), we build a monotone CNF formula, which is equivalent to a SetCover instance. To obtain a $k$-versus-$h$ gap, the reduction enumerates all hash functions from $Σ$ to $[2h]$ and all unsatisfiable 2-CSP instances on the same constraint graph with alphabet $[2h]$. For each such instance, it asks for a certificate that the hashed label pairs are not all contained in that instance. Perfect hashing makes this enumeration efficient for $h=\\log n/\\log\\log n$.","short_abstract":"We show that $\\bigl(\\frac{\\log n}{\\log\\log n}\\bigr)$-approximate parameterized $k$-SetCover is W[1]-hard, and has no $n^{o(k/\\log k)}$-time algorithms under ETH. This improves upon the previous best factors $\\bigl(\\frac{\\log n}{\\log\\log n}\\bigr)^{1/k}$ in (Lin, 2019) and $(\\log n)^{1/\\operatorname{poly}(k)}$ in (Karthi...","url_abs":"https://arxiv.org/abs/2609.19685","url_pdf":"https://arxiv.org/pdf/2609.19685v1","authors":"[\"Venkatesan Guruswami\",\"Xuandi Ren\"]","published":"2026-09-17T04:32:18Z","proceeding":"cs.CC","tasks":"[\"cs.CC\",\"cs.DS\"]","methods":"[]","has_code":false}