2026-07-21T21:09:30Z https://drops.dagstuhl.de/oai
oai:drops-oai.dagstuhl.de:22232 2024-12-05T15:32:41Z ddc:004 open_access
On Equivalence of Parameterized Inapproximability of k-Median, k-Max-Coverage, and 2-CSP Karthik C. S. Lee, Euiwoong Manurangsi, Pasin Parameterized complexity Hardness of Approximation Parameterized Inapproximability Hypothesis max coverage k-median Parameterized Inapproximability Hypothesis (PIH) is a central question in the field of parameterized complexity. PIH asserts that given as input a 2-CSP on k variables and alphabet size n, it is đ–¶[1]-hard parameterized by k to distinguish if the input is perfectly satisfiable or if every assignment to the input violates 1% of the constraints. An important implication of PIH is that it yields the tight parameterized inapproximability of the k-maxcoverage problem. In the k-maxcoverage problem, we are given as input a set system, a threshold τ > 0, and a parameter k and the goal is to determine if there exist k sets in the input whose union is at least τ fraction of the entire universe. PIH is known to imply that it is đ–¶[1]-hard parameterized by k to distinguish if there are k input sets whose union is at least τ fraction of the universe or if the union of every k input sets is not much larger than τ⋅ (1-1/e) fraction of the universe. In this work we present a gap preserving FPT reduction (in the reverse direction) from the k-maxcoverage problem to the aforementioned 2-CSP problem, thus showing that the assertion that approximating the k-maxcoverage problem to some constant factor is đ–¶[1]-hard implies PIH. In addition, we present a gap preserving FPT reduction from the k-median problem (in general metrics) to the k-maxcoverage problem, further highlighting the power of gap preserving FPT reductions over classical gap preserving polynomial time reductions. Schloss Dagstuhl – Leibniz-Zentrum fĂŒr Informatik Karthik C. S. and Euiwoong Lee and Pasin Manurangsi 2024 Is Part Of LIPIcs, Volume 321, 19th International Symposium on Parameterized and Exact Computation (IPEC 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2024.6 urn:nbn:de:0030-drops-222322 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2024.6 eng https://creativecommons.org/licenses/by/4.0/legalcode