On Equivalence of Parameterized Inapproximability of k-Median, k-Max-Coverage, and 2-CSP
Abstract
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 W[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 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 implies that it is W[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 from the k-maxcoverage problem to the aforementioned 2-CSP problem, thus showing that the assertion that approximating k-maxcoverage to some constant factor 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.
An important implication of PIH is that it yields the tight parameterized inapproximability of the 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 implies that it is W[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 from the k-maxcoverage problem to the aforementioned 2-CSP problem, thus showing that the assertion that approximating k-maxcoverage to some constant factor 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.
