Parameterized approximation algorithm

The k-cut problem has no polynomial-time ${\displaystyle (2-\varepsilon )}$-approximation algorithm for any ${\displaystyle \varepsilon >0}$, assuming ${\displaystyle P\neq NP}$ and the small set expansion hypothesis.[3] It is also W[1]-hard parameterized by the number ${\displaystyle k}$ of required components.[4] However an EPAS exists, which computes a ${\displaystyle (1+\varepsilon )}$-approximation in ${\displaystyle (k/\varepsilon )^{O(k)}n^{O(1)}}$ time.[5]

The Steiner tree problem is FPT parameterized by the number of terminals.[6] However for the "dual" parameter consisting of the number ${\displaystyle k}$ of non-terminals contained in the optimum solution, the problem is W[2]-hard (due to a folklore reduction from the Dominating Set problem). Steiner Tree is also known to be APX-hard.[7] However, there is an EPAS computing a ${\displaystyle (1+\varepsilon )}$-approximation in ${\displaystyle 2^{O(k^{2}/\varepsilon ^{4})}n^{O(1)}}$ time.[8]

It is known that the Strongly Connected Steiner Subgraph problem is W[1]-hard parameterized by the number ${\displaystyle k}$ of terminals,[9] and also does not admit an ${\displaystyle O(\log ^{2-\varepsilon }n)}$-approximation in polynomial time (under standard complexity assumptions).[10] However a 2-approximation can be computed in ${\displaystyle 3^{k}n^{O(1)}}$ time.[11] Furthermore, this is best possible, since no ${\displaystyle (2-\varepsilon )}$-approximation can be computed in ${\displaystyle f(k)n^{O(1)}}$ time for any function ${\displaystyle f}$, under Gap-ETH.[12]

For the well-studied metric clustering problems of k-median and k-means parameterized by the number ${\displaystyle k}$ of centers, it is known that no ${\displaystyle (1+2/e-\varepsilon )}$-approximation for k-Median and no ${\displaystyle (1+8/e-\varepsilon )}$-approximation for k-Means can be computed in ${\displaystyle f(k)n^{O(1)}}$ time for any function ${\displaystyle f}$, under Gap-ETH.[13] Matching parameterized approximation algorithms exist,[13] but it is not known whether matching approximations can be computed in polynomial time.

Clustering is often considered in settings of low dimensional data, and thus a practically relevant parameterization is by the dimension of the underlying metric. In the Euclidean space, the k-Median and k-Means problems admit an EPAS parameterized by the dimension ${\displaystyle d}$,[14][15] and also an EPAS parameterized by ${\displaystyle k}$.[16][17] The former was generalized to an EPAS for the parameterization by the doubling dimension.[18] For the loosely related highway dimension parameter, only an approximation scheme with XP runtime is known to date.[19]

For the metric k-center problem a 2-approximation can be computed in polynomial time. However, when parameterizing by either the number ${\displaystyle k}$ of centers,[20] the doubling dimension (in fact the dimension of a Manhattan metric),[21] or the highway dimension,[20] no parameterized ${\displaystyle (2-\varepsilon )}$-approximation algorithm exists, under standard complexity assumptions. Furthermore, the k-Center problem is W[1]-hard even on planar graphs when simultaneously parameterizing it by the number ${\displaystyle k}$ of centers, the doubling dimension, the highway dimension, and the pathwidth.[22] However, when combining ${\displaystyle k}$ with the doubling dimension an EPAS exists,[22] and the same is true when combining ${\displaystyle k}$ with the highway dimension.[23] For the more general version with vertex capacities, an EPAS exists for the parameterization by k and the doubling dimension, but not when using k and the highway dimension as the parameter.[24] Regarding the pathwidth, k-Center admits an EPAS even for the more general treewidth parameter, and also for cliquewidth.[25]

An optimization variant of the k-Clique problem is the Densest k-Subgraph problem (which is a 2-ary Constraint Satisfaction problem), where the task is to find a subgraph on ${\displaystyle k}$ vertices with maximum number of edges. It is not hard to obtain a ${\displaystyle (k-1)}$-approximation by just picking a matching of size ${\displaystyle k/2}$ in the given input graph, since the maximum number of edges on ${\displaystyle k}$ vertices is always at most ${\displaystyle {k \choose 2}=k(k-1)/2}$. This is also asymptotically optimal, since under Gap-ETH no ${\displaystyle k^{1-o(1)}}$-approximation can be computed in FPT time parameterized by ${\displaystyle k}$.[26]

For the Dominating set problem it is W[1]-hard to compute any ${\displaystyle g(k)}$-approximation in ${\displaystyle f(k)n^{O(1)}}$ time for any functions ${\displaystyle g}$ and ${\displaystyle f}$.[27]