A Survey on Parameterized Inapproximability: $k$-Clique, $k$-SetCover, and More

This article is organized by the problems. In Section 2, we put some preliminaries, including the definition of problems and hypotheses. In Section 3, we introduce MaxCover and MinLabel, two problems which are not only important intermediate problems in proving parameterized inapproximability, but also of great interest themselves. In Section 4 and 5, we introduce recent parameterized inapproximability results of $k$-Clique and $k$-SetCover, respectively.

For a parameterized optimization problem, we use $n$ to denote the input size, and the parameter $k$ usually refers to the number of elements we need to pick to obtain an optimal solution. In some problems $k$ is just the optimal solution size (e.g. $k$-Clique), while in other problems it is not (e.g. One-Sided $k$-Biclique). By enumerating the $k$ elements in the solution, the brute-force algorithm usually runs in time $O(n^{k})$.

An algorithm for a maximization (respectively, minimization) problem is called $\rho$-FPT-approximation if it runs in $f(k)n^{O(1)}$ time for some computable function $f$, and outputs a solution of size at least $k/\rho$ (respectively, at most $k\cdot\rho$). Here $\rho$ is called approximation ratio. If an optimization problem admits no $f(k)$-FPT-approximation for any computable function $f$, we say this problem is totally FPT inapproximable.

Note that since computing a constant-size solution is trivial, for a maximization problem, we only care about $o(k)$-FPT-approximation and the approximation ratio is measured in terms of only $k$. However, for a minimization problem, any computable approximation ratio is non-trivial, so if totally FPT inapproximability is already established, we can also discuss approximation ratio in terms of both $k$ and $n$.

If the input is divided into $k$ groups, and one is only allowed to pick at most one element from each group, we say this problem is colored, otherwise it is uncolored. For some problems (e.g. $k$-Clique), the two versions are equivalent, while for some other problems (e.g. $k$-Biclique) they are not equivalent at all. We will discuss the coloring in each problem’s section separately.

Now we list the problems considered in this article. There are some other problems (e.g. MaxCover) which are used as intermediate problems in proving hardness of approximation. We put their definitions in their separate sections since they are a bit more complicated.

• •

  3SAT. The input is a 3-CNF formula $\varphi$ with $m$ clauses on $n$ variables. The goal is to decide whether there is a satisfying assignment for $\varphi$.

• •

  $k$-Clique. The input is an undirected graph $G=(V,E)$ with $n$ vertices. The goal is to decide whether there is a clique of size $k$.

• •

  Densest $k$-Subgraph. The input is an undirected graph $G=(V,E)$ with $n$ vertices, and the goal is to find the maximum number of edges induced by $k$ vertices.

• •

  $k$-SetCover. The input is a collection of $n$ sets $\mathcal{S}=\{S_{1},\ldots,S_{n}\}$ over universe $U$. The goal is to decide whether there are $k$ sets in $\mathcal{S}$, whose union is $U$.

Here we list the hypotheses which the results are based on.

W[1]$\neq$FPT and W[2]$\neq$FPT are arguably the most natural hypotheses in parameterized complexity, and are often used to derive FPT time lower bounds. Since $k$-Clique and $k$-SetCover are complete problems of W[1] and W[2], respectively, we directly use their intractability results in the statements of those two hypotheses here, and omit the definition of W-Hierarchy.

Tighter time lower bounds like $n^{\Omega(k)}$ often involves the Exponential Time Hypothesis (ETH).

There are two stronger assumptions on the intractability of 3SAT, namely, the Gap Exponential Time hypothesis (Gap-ETH) and Strong Exponential Time hypothesis (SETH). Gap-ETH is useful in proving strong inapproximability results for many parameterized problems, while SETH is used to show tight time lower bounds like $n^{k-o(1)}$.

Note that by current state-of-the-art PCP theorem, a 3SAT formula $\varphi$ on $n$ variables can be transformed into a constant gap 3SAT formula $\varphi^{\prime}$ on only $n\text{polylog}(n)$ variables [Din07]. Therefore, assuming ETH, constant gap 3SAT cannot be solved in $2^{o(n/\text{polylog}(n))}$ time. A big open problem is whether linear-sized PCP exists. If so, Gap-ETH would follow from ETH.

Gap-ETH and SETH both imply ETH. However, no formal relationship between them is known now.

There are also randomized versions of ETH, Gap-ETH and SETH, which also rule out randomized algorithms running in corresponding time. We do not separately list them here.

One last important hypothesis is the Parameterized Inapproximability Hypothesis (PIH).

The factor $(1+\varepsilon)$ can be replaced by any constant and is not important.

Note that if for a graph the number of edges induced by $k$ vertices is only $\binom{\varepsilon k}{2}\approx\varepsilon^{2}\binom{k}{2}$, it can not have a clique of size $>\varepsilon k$. Thus, PIH implies $k$-Clique is hard to approximate within any constant factor in FPT time. However, the reverse direction is not necessarily true (forbiddinng small clique does not imply low density of edges), and it remains an important open question that whether PIH holds if we assume $k$-Clique is FPT inapproximable within any constant factor.

Another remark is that PIH can be implied from Gap-ETH. See Appendix A of [BGKM18] for a simple proof. However, deriving PIH from a gap-free hypothesis such as ETH is still open.

Results in this subsection are from [CCK⁺17].

A 3SAT instance can be formulated as MaxCover instance as follows. Each left super-node consists of 7 vertices, which represent the satisfying assignments of a clause. Each right super-node consists of 2 vertices, which correspond to the true/false assignment for a variable. Two vertices are linked if and only if the assignments are consistent. Therefore, Gap-ETH can be also restated as an intractability result of constant gap MaxCover:

Actually Gap-ETH is equivalent to the above, see Appendix E of [CCK⁺17].

Note that MaxCover can be solved in $O^{*}(|\Sigma_{U}|^{\ell})$ or $O^{*}(|\Sigma_{W}|^{h})$ time, by just enumerating vertices picked from each left super-nodes or right super-nodes. Moreover, it can even decide whether the answer is $\geq\frac{r}{\ell}$ in $O^{*}(\binom{\ell}{r}|\Sigma_{U}|^{r})=O^{*}((\ell|\Sigma_{U}|)^{r})$ or $O^{*}(|\Sigma_{W}|^{h})$ time. As shown below, these are the best possible assuming Gap-ETH.

The theorem is straightforward when $r=\Theta(\ell)$, because we can directly compress a constant number of left super-nodes into one. The interesting case is when $r$ is much smaller than $\ell$.

The proof involves a combinatorial object called disperser, which is defined as follows.

Dispersers with proper parameters can be constructed using random subsets with high probability.

This above construction can also be derandomized easily. With this tool, we can compress the left super-nodes in a MaxCover instance according to those subsets. Each left super-node now corresponds to satisfying assignments of the AND of $k$ clauses. If there is a labeling that covers at least $r$ left super-nodes, from the definition of disperser we know that at least $(1-\varepsilon)m$ clauses in the original 3SAT instance can be simultaneously satisfied. The size of the new instance is $2^{O(k)}=2^{O(m/r)}$, thus an algorithm for MaxCover which runs in $|\Gamma|^{o(r)}$ time would lead to an algorithm for constant gap 3SAT in $2^{o(m)}$ time, refuting Gap-ETH.

In the other direction, we would like to rule out $|\Gamma|^{o(h)}$ algorithms for approximating MaxCover, where $h$ is the number of right super-nodes. We have the following theorem:

Note that in the statement of this theorem, $h$ can be any fixed constant, while in the statement of Gap-ETH, $h$ is the number of variables which goes to infinity. Thus, a straightforward idea is to compress the variables into $h$ groups, each of size $n/h$.

After grouping variables, we can also compress the clauses in order to amplify the soundness parameter to $\gamma$. Specifically, let $k=\ln(\frac{1}{\gamma})/\varepsilon$, take $\ell=\binom{m}{k}$ left super-nodes, each corresponding to satisfying assignments of the AND of some $k$ clauses. If only $(1-\varepsilon)m$ clauses in the original 3SAT instance can be satisfied, then only $\binom{(1-\varepsilon)m}{k}$ clauses in the new instance can be satisfied, leading to a soundness parameter $\binom{(1-\varepsilon)m}{k}/\binom{m}{k}\leq e^{-\varepsilon k}=\gamma$. Furthermore, $|\Sigma_{U}|=O(1)^{k}\leq(1/\gamma)^{O(1)}$.

One important thing is that we need to make sure $\ell$ and $|\Sigma_{U}|$ can be bounded by $|\Sigma_{W}|=2^{n/h}$, so that $|\Sigma_{W}|$ is the dominating term in $|\Gamma|$. Thus, $\gamma$ cannot be arbitrarily small. Fortunately in its major applications (e.g. hardness of SetCover), this will not be the bottleneck.

Next we proceed to discuss hardness of MinLabel.

The instance is exactly the one in Theorem 3.6. It is easy to see that in the completeness case, MaxCover$=1$ implies MinLabel$=1$. We only need to additionally argue that, in the soundness case, small MaxCover implies large MinLabel. Prove by contradiction, if MinLabel$\leq\gamma^{-1/h}$, we can fix this multi-labeling, and pick a vertex uniformly at random from each right super-node to form a labeling. By proving the expected fraction of covered left super-nodes $\geq\gamma$, we have MaxCover$\geq\gamma$. In the following we suppose the optimal right multi-labeling $S\subseteq W$ covers left vertices $u_{1}\in U_{1},\ldots,u_{h}\in U_{h}$.

The left alphabet size is $(1/\gamma)^{O(1)}$, as in Theorem 3.6.

Threshold Graph Composition is a powerful gap-producing technique. It was first proposed by Lin in his breakthrough work [Lin18], and has been used to create gap for many parameterized problems [CL19, Lin19, BBE⁺19, KN21].

At a high level, in TGC we compose an instance which has no gap, with a threshold graph which is oblivious to the instance, to produce a gap instance of that problem. The two main challenges of TGC are the creation of a threshold graph with desired properties, and the right way to compose the input and the threshold graph, respectively.

In this subsection, we introduce a delicate threshold graph, which is constructed via error correcting codes. This graph was proposed by Karthik et al. [KN21], and had many applications such as in proving hardness of MaxCover starting from W[1]$\neq$FPT or ETH (later in this Section), and in simplifying the proof of $k$-SetCover inapproximability in [Lin19] (see Section 5.4).

We first formalize some definitions related to error correcting codes.

We sometimes abuse notations and treat an error correcting code as its image, i.e., $C\subset\Sigma^{\ell}$.

For any error correcting code $C:\Sigma^{r}\to\Sigma^{\ell}$ and any $k\in\mathbb{N}$, we can take it to build a bipartite threshold graph $G=(A\dot{\cup}B,E)$ with the following properties efficiently:

• •

  $A$ is divided into $k$ groups, each of size $|\Sigma|^{r}$. $B$ is divided into $\ell$ groups, each of size $|\Sigma|^{k}$.

• •

  (Completeness) For any $a_{1}\in A_{1},\ldots a_{k}\in A_{k}$ and for any $j\in[\ell]$, there is a unique vertex $b\in B_{j}$ which is a common neighbor of $\{a_{1},\ldots,a_{k}\}$.

• •

  (Soundness) For every $i\in[k]$ and every distinct $a\neq a^{\prime}\in A_{i}$, for $\Delta(C)\cdot\ell$ of the parts $j\in[\ell]$, we have that $\mathcal{N}(a)\cap\mathcal{N}(a^{\prime})\cap\mathcal{B}_{j}=\emptyset$.

• •

  (Collision Property) Let $X\subseteq A$ such that for every $j\in[\ell]$, there exists $b\in B_{j}$ which is a common neighbor of (at least) $k+1$ vertices in $X$. Then $|X|\geq Col(C)$.

The graph is constructed as follows:

• •

  For every $i\in[k]$, we associate $A_{i}$ with all codewords in $C$, i.e. each vertex in $A_{i}$ is a unique codeword in the image of $C$.

• •

  For every $j\in[\ell]$, we associate $B_{j}$ with the set $\Sigma^{k}$.

• •

  A vertex $a\in A_{i}$ and a vertex $b\in B_{j}$ are linked if and only if $a_{j}=b_{i}$.

We can think of the graph as an $k\times\ell$ matrix, when picking vertices from each $A_{i},i\in[k]$, we are filling the codewords into each row of the matrix. By reading out each column of the matrix, we can pick exactly one common neighbor of them in each $B_{j},j\in[\ell]$, satisfying the completeness property.

The soundness property is also straightforward: if we pick two vertices $a,a^{\prime}$ from the same left group $A_{i}$, the two codewords differ in at least $\Delta(C)\cdot\ell$ positions. For those columns we cannot “read out” any $k$-bit string whose $i$-th bit equals to two different characters.

As for the collision property, for a set $X\subseteq A$, if for every $j\in[\ell]$ there exists $b\in B_{j}$ which is a common neighbor of at least $k+1$ vertices in $X$, it’s easy to see that for any $j\in[\ell]$, we can pick $x,y\in X$ such that $x_{j}=y_{j}$ by pigeonhole principle.

Now we describe how to compose this threshold graph with a $k$-MaxCover instance $\Gamma$ where the parameter $k$ denotes the number of right super-nodes, to produce a Gap $k$-MaxCover instance $\Gamma^{\prime}$ such that:

• •

  (Completeness) If MaxCover$(\Gamma)=1$, then MaxCover$(\Gamma^{\prime})=1$.

• •

  (Soundness) If MaxCover$(\Gamma)<1$, then MaxCover$(\Gamma^{\prime})\leq 1-\Delta(C)$.

Given a $k$-MaxCover instance $\Gamma=G=(U\dot{\cup}W,E)$ with pseudo projection property, where $W=W_{1}\dot{\cup}\ldots\dot{\cup}W_{k}$ and $U=U_{1}\dot{\cup}\ldots\dot{\cup}U_{t}$, and a threshold graph $G^{\prime}=(A\dot{\cup}B,E^{\prime})$, where $A=A_{1}\dot{\cup}\ldots\dot{\cup}A_{t}$ and $B=B_{1}\dot{\cup}\ldots\dot{\cup}B_{\ell}$, w.l.o.g. assume $|\Sigma|^{r}\geq\max_{i=1}^{t}|U_{i}|$, we build the new $k$-MaxCover instance $\Gamma^{\prime}$ as follows.

• •

  Arbitrarily match every vertex $u_{i}\in U_{i}$ to a vertex in $a_{i}\in A_{i}$ without repetitions. This can be done since $|\Sigma|^{r}\geq\max_{i=1}^{t}|U_{i}|$.

• •

  The new right super-nodes are $W_{1}\ldots W_{k}$, and the new left super-nodes are $B_{1}\ldots B_{\ell}$.

• •

  A right vertex $w\in W_{i}$ and a left vertex $b\in B_{j}$ are linked if and only if there exists $u_{1}\in U_{1},\ldots,u_{t}\in U_{t}$ such that $w_{i}$ is linked to each $u_{1}\ldots u_{t}$ in $G$, and $b$ is linked to the matching $a_{1}\ldots a_{t}$ in $G^{\prime}$.

The completeness case is obvious, by picking one $w$ in each right super-node $W_{i}$, there is a common neighbor in each left super-node $U_{i}$. Consider their matching vertices $a_{1}\ldots a_{t}$, there is exactly one common neighbor in each $B_{i}$.

The soundness case needs the pseudo projection property of $G$, i.e., for every $i\in[k]$ and $j\in t$, edges between $W_{i}$ and $U_{j}$ either form a function, or are complete. Fix any labeling $w_{1}\in W_{1},\ldots,w_{k}\in W_{k}$, there must be a super-node $U_{j}$ which cannot be covered. This means there must be two left vertices $w,w^{\prime}$ mapping to different vertices in $U_{j}$. Let the two vertices be $u,u^{\prime}\in U_{j}$, and let the matching vertices of them be $a,a^{\prime}\in A_{j}$, by the soundness property of threshold graph, only in $1-\Delta(C)$ fraction of parts $j\in[\ell]$ is there a common neighbor of $a,a^{\prime}$ in $B_{j}$. This means the labeling $\{w_{1},\ldots,w_{k}\}$ can only cover $(1-\Delta(C))\cdot\ell$ parts of $B$, i.e., MaxCover$(\Gamma^{\prime})\leq 1-\Delta(C)$.

Next we use this technique to prove strong inapproximability results of $k$-MaxCover based on W[1]$\neq$FPT and ETH.

The Gap-ETH hardness of $k$-Clique directly follows from Theorem 3.3. Since the instance has projection property, two left vertices agree if and only if they map to the same vertex in each right super-node, and $k$ left vertices agree if and only if they pairwise agree. Thus, we can transform a MaxCover instance in Theorem 3.3 with $k$ left super-nodes to an $k$-Clique instance with the same value.

Therefore, as pointed out in Theorem 3.3, even deciding if there is a clique of size $\geq r$ needs $n^{\Omega(r)}$ time. Here $r$ can be any $\omega(1)$, which means approximating $k$-Clique to any $\rho=k/r=o(k)$ ratio cannot be done in $f(k)\cdot n^{o(r)}=f(k)\cdot n^{o(k/\rho)}$ time.

Note the projection property is crucial, without which a MaxCover instance cannot be reduced to an $k$-Clique instance, because the agreement test of $k$ left vertices cannot be decomposed locally to agreement tests of $\binom{k}{2}$ pairs of left vertices.

One interesting thing is that the optimal inapproximability result of $k$-Clique can be obtained from hypotheses other than (but similar to) Gap-ETH, see the following as an example.

This assumption is a little weaker than Gap-ETH since it can be obtained through the canonical reduction from 3SAT to Clique.

The proof is almost the same as that in Theorem 3.3: just compose the groups using a disperser. Details are omitted here.

Before introducing W[1]-hardness of constant approximating $k$-Clique, we want to mention an important W[1]-complete problem, $k$-VectorSum, which is used as an intermediate problem in the reduction in [Lin21].

In the $k$-VectorSum problem, we are given $k$ groups of vectors $V_{1},\ldots,V_{k}\subseteq\mathbb{F}^{d}$ together with a target vector $\vec{t}\in\mathbb{F}^{d}$, where $\mathbb{F}$ is some finite field and $d$ is the dimension of vectors. The goal is to decide whether there exists vectors $\vec{v}_{1}\in V_{1},\ldots,\vec{v}_{k}\in V_{k}$ such that $\sum_{i=1}^{k}\vec{v}_{i}=\vec{t}$.

It’s easy to see $k$-VectorSum with $|\mathbb{F}|=O(1)$ and $d=O(k\log n)$ is W[1]-hard, and even does not admit $n^{o(k)}$ time algorithms assuming ETH. The idea is to use entries of vectors to check the consistency in $k$-Clique or 3SAT.

Note that the $\mathbb{F}_{2}$ can be replaced by any finite field, as long as we slightly adjust the value of an entry: both 0 if $x=0$; $c$ in the first appearance and $-c$ in the second appearance for some constant $c\neq 0$ if $x=1$.

In this subsection we briefly introduce how Lin [Lin21] rules out constant FPT-approximations of $k$-Clique under W[1]$\neq$FPT.

The most essential step in the reduction is to combine $k$-VectorSum, whose W[1]-hardness was shown in Theorem 4.2, with Hadamard codes to create a gap. The technique is very similar to which people used in proving weakened PCP theorem, namely, in proving NP $\subseteq$ PCP$(\text{poly(n),1})$ [ALM⁺98].

Here follows the definition of Hadamard Code, and its two important properties.

1. 1.

   (Linearity Testing, [BLR93]) Let $g$ be a function mapping from $\{0,1\}^{n}$ to $\{0,1\}$. If it can pass $(1-\delta)$ fraction of tests $g(x)+g(x^{\prime})=g(x+x^{\prime}),x,x^{\prime}\in\{0,1\}^{n}$, then $g$ is at least $(1-\delta)$-close to a true linear function $\tilde{g}:\{0,1\}^{n}\to\{0,1\}$, which can also be parsed as a Hadamard codeword. By setting $0\leq\delta<\frac{1}{4}$, this codeword is unique since the relative distance of Hadamard Code is exactly $\frac{1}{2}$.

2. 2.

   (Locally Decodable Property) Suppose $g$ is $(1-\delta)$-close to a Hadamard codeword $f(x)$ for some $x\in\{0,1\}^{n}$, then for any $y\in\{0,1\}^{n}$, we can recover $(f(x))_{y}$ probabilistically by querying only two positions of $g$. Namely, sample $y^{\prime}\in\{0,1\}^{n}$ uniformly at random, and output $g(y+y^{\prime})+g(y^{\prime})$. This succeeds with probability at least $1-2\delta$ by a simple union bound.

Given an $k$-VectorSum instance $(V_{1},\ldots,V_{k},\vec{t})$, we build a CSP instance on variable set $X=\{x_{\vec{a}_{1},\ldots,\vec{a}_{k}}:\vec{a}_{1},\ldots,\vec{a}_{k}\in\mathbb{F}^{d}\}$. Let $\vec{v}_{1}\in V_{1},\ldots,\vec{v}_{k}\in V_{k}$ be a solution that sums up to $\vec{t}$ in the yes case, each variable $x_{\vec{a}_{1},\ldots,\vec{a}_{k}}$ is supposed to take the value $\sum_{i\in[k]}\langle\vec{a}_{i},\vec{v}_{i}\rangle$. Here we are actually concatenating the $k$ solution vectors into one long vector $\vec{v}\in\mathbb{F}^{kd}$, and the concatenation of variables is supposed to be the Hadamard codeword of $\vec{v}$.

There are three types of tests we want to make:

• •

  (T1) $\forall\vec{a}_{1},\ldots,\vec{a}_{k},\vec{b}_{1},\ldots\vec{b}_{k}\in\mathbb{F}^{d}$, test whether $x_{\vec{a}_{1},\ldots,\vec{a}_{k}}+x_{\vec{b}_{1},\ldots\vec{b}_{k}}=x_{\vec{a}_{1}+\vec{b}_{1},\ldots,\vec{a}_{k}+\vec{b}_{k}}$.

• •

  (T2) $\forall i\in[k],\forall\vec{a}_{1},\ldots,\vec{a}_{k},\vec{a}\in\mathbb{F}^{d}$, test whether $x_{\vec{a}_{1},\ldots,\vec{a}_{i}+\vec{a},\ldots,\vec{a}_{k}}-x_{\vec{a}_{1},\ldots,\vec{a}_{k}}=\langle\vec{a},\vec{v}\rangle$ for some $v\in V_{i}$.

• •

  (T3) $\forall\vec{a}_{1},\ldots,\vec{a}_{k},\vec{a}\in\mathbb{F}^{d}$, test whether $x_{\vec{a}_{1}+\vec{a},\ldots,\vec{a}_{k}+\vec{a}}-x_{\vec{a}_{1},\ldots,\vec{a}_{k}}=\langle\vec{a},\vec{t}\rangle$.

By linearity testing, if an assignment to $X$ satisfies $(1-\delta)$-fraction of constraints in (T1), then $X$ is at least $(1-\delta)$-close to a true Hadamard codeword $f(\vec{u})$, $\vec{u}\in\mathbb{F}^{kd}$. The constraints (T2) and (T3) use locally decodable properties to recover $f(\vec{u})_{(\vec{0},\ldots,\vec{a},\ldots,\vec{0})},f(\vec{u})_{(\vec{a},\ldots,\vec{a})}$, and use them to check whether $\vec{u}$ indeed indicates a satisfying solution of our $k$-VectorSum instance.