Parameterized Approximation: Algorithms and Hardness

For a fixed class $F$ of graphs, the $F$-Deletion problem, given a graph $G$, asks to remove the minimum number of vertices so that the resulting graph belongs to the class $F$. The study of various $F$-Deletion problems has led to interesting connections between approximation algorithms and parameterized algorithms, ultimately leading to parameterized approximation algorithms. In this talk, we survey known results for subgraph, induced subgraph, and minor deletion problems.

We present the cut covering lemma, a classic result by Kratsch and Wahlstrom (2012)[1] in FPT literature with many applications to kernelization. Loosely speaking, the lemma states that on any graph with k terminal vertices, there is a smaller graph on $O(k^3)$ vertices that preserves the complete cut structure of the graph. We discuss connections to the field of fast graph algorithms, in particular the implications of an approximate version of the cut covering lemma with $O(k)$ vertices.

We consider the well-studied algorithmic regime of designing a $(1+ϵ)$-approximation algorithm for a $k$-clustering problem that runs in time $f(k,ϵ)\text{poly}(n)$. Our main contribution is a clean and simple EPAS that settles more than ten clustering problems (across multiple well-studied objectives as well as metric spaces) and unifies well-known EPASes. Our algorithm gives EPASes for a large variety of clustering objectives (for example, $k$-means, $k$-center, $k$-median, priority $k$-center, $\mathrm{\ell }$-centrum, ordered $k$-median, socially fair $k$-median aka robust $k$-median, or more generally monotone norm $k$-clustering) and metric spaces (for example, continuous high-dimensional Euclidean spaces, metrics of bounded doubling dimension, bounded treewidth metrics, and planar metrics). Key to our approach is a new concept that we call bounded $ϵ$-scatter dimension – an intrinsic complexity measure of a metric space that is a relaxation of the standard notion of bounded doubling dimension.

We study budgeted variants of well known maximization problems with multiple matroid constraints. Given an $\mathrm{\ell }$-matchoid $ℳ$ on a ground set $E$, a profit function $p$ and a cost function $c$ on $E$, and a budget $B$, the goal is to find in the $\mathrm{\ell }$-matchoid a feasible set $S$ of maximum profit $p(S)$ subject to the budget constraint, i.e., $c(S)\le B$. The budgeted $\mathrm{\ell }$-matchoid (BM) problem includes as special cases budgeted $\mathrm{\ell }$-dimensional matching and budgeted $\mathrm{\ell }$-matroid intersection. A strong motivation for studying BM from parameterized viewpoint comes from the APX-hardness of unbudgeted $\mathrm{\ell }$-dimensional matching (i.e., $B=\mathrm{\infty }$) already for $\mathrm{\ell }=3$. Nevertheless, while there are known FPT algorithms for the unbudgeted variants of the above problems, the budgeted variants are studied here for the first time through the lens of parameterized complexity.

We show that BM parametrized by solution size is $W[1]$-hard, already with a degenerate single matroid constraint. Thus, an exact parameterized algorithm is unlikely to exist, motivating the study of FPT-approximation schemes (FPAS). Our main result is an FPAS for BM (implying an FPAS for $\mathrm{\ell }$-dimensional matching and budgeted $\mathrm{\ell }$-matroid intersection), relying on the notion of representative set $-$ a small cardinality subset of elements which preserves the optimum up to a small factor. We also give a lower bound on the minimum possible size of a representative set which can be computed in polynomial time.

The Weighted Connectivity Augmentation Problem (WCAP) asks to increase the edge-connectivity of a graph in the cheapest possible way by adding edges from a given set. It is one of the most elementary network design problems for which no better-than-$2$ approximation algorithm has been known, whereas $2$-approximations can be easily obtained through a variety of well-known techniques.

In this talk, I will discuss an approach showing that approximation factors below 2 are achievable for WCAP, ultimately leading to a $(1.5+ϵ)$-approximation algorithm. Our approach is based on a highly structured directed simplification of WCAP with planar optimal solutions. We show how one can successively improve solutions of this directed simplification by moving to mixed-solutions, consisting of both directed and undirected edges. These insights can be leveraged in local search and relative greedy strategies, inspired by recent advances on the Weighted Tree Augmentation Problem, to obtain a $(1.5+ϵ)$-approximation algorithm for WCAP.

Given a set of points (clients) $C$ and a set of facilities $F$ in a metric space $(C\cup F,\mathrm{dist})$, the classic $k$-Median problem asks to find a subset $S\subseteq F$ of size $k$ (the centers), such that the total distance $d(S):={\sum }_{p\in C}{\min }_{c\in S}\mathrm{dist}(p,c)$ of points in $C$ to the closest facility is minimized.

1. 1.

   Find a $(1+2/e)$-approximation that runs in time $2^{O(k)}\mathrm{poly}(n)$ (where $(C\cup F,\mathrm{dist})$ is an arbitrary metric space).

2. 2.

   Consider the continuous setting of $k$-median with $L_{\mathrm{\infty }}$ metrics (i.e.: $C$ is a subset of ${ℝ}^d$ and $F$ is ${ℝ}^d$). Find a 2-Approximation that runs in $2^{O(k)}\mathrm{poly}(nd)$ time.

In the Santa Claus problem we are given a collection of presents and a collection of children. Each present i has a value $v_{ij}\ge 0$ for child $j$. The happiness of a child $j$ is the sum of the values of the presents that (s)he receives. Our goal is to assign the presents so as to maximize the minimum happiness of any child. Santa Claus turns out to be an extremely challenging problem in terms of approximation algorithms. The best known lower bound on the (polynomial-time) approximation ratio is $2$, while the best known upper bound on the same ratio is polynomial in the number $n$ of items.

Given the difficulty of this problem, it makes sense to consider FPT approximation algorithms. One natural parameter is the number $k$ of children. I did ask if a constant approximation (or better) is possible in FPT time. Andreas Wiese made me notice that a parameterized approximation scheme (PAS) for this problem is implied by [1] (described in the form of an EPTAS for constant $k$)

An interesting open question that remains is to define alternative parameters that make sense in practice, and design FPT approximation algorithms with respect to them.

While a number of parameterized problems are known to be hard to approximate under the Gap Exponential Time Hypothesis (Gap-ETH), certain results are still out of reach of the current techniques even under Gap-ETH. We discuss a few such questions, including:

1. 1.

   Strong FPT Inapproximability of $k$-Set Cover. While it is known that approximating $k$-Set Cover to within $g(k)$-factor is W[1]-hard for any function $g$[6]. The situation is less clear when we allow dependency on $n$ (the number of elements in the universe) in the approximation factor; the greedy algorithm yields $O(\log n)$-approximation while the best known ETH-hardness result is only $\tilde{\mathrm{\Omega }}({\log }^{1/k}n)$[4]. Open Question: Can we improve this hardness to, say, $\mathrm{\Omega }({\log }^{0.99}n)$ under Gap-ETH?

2. 2.

   Total FPT Inapproximability of Exact $k$-Set Cover. Exact $k$-Set Cover is a special case of the Set Cover problem where we are promised that there exists a set cover of size $k$ such that the subsets in the solution are all disjoint. (Note here that the output solution only needs to cover the space but needs not be disjoint.) This version of Set Cover is often useful in subsequent reductions, e.g. to Coding-theoretic and Lattice problems. While the hardness of Exact Set Cover is achieved for free in the NP-hardness of approximation reduction for Set Cover of Feige[3], the parameterized hardness reductions do not give the hardness of such a version. This is due to the so-called “projection” property in Label Cover, which does not hold in the parameterized version of Label Cover used in the FPT hardness regime; in fact, it is not hard to see that requiring such projection properties will lead to at most $2^k$ gap. To the best of our knowledge, the best FPT hardness of approximation of Exact Set Cover based on Gap-ETH is only $k^{1/2--o(1)}$, which follows from the result of Manurangsi and Dinur [2]. Open Question: Can we rule out all $g(k)$-approximation FPT algorithm for Exact $k$-Set Cover?

3. 3.

   Total FPT Inapproximability of Densest $k$-Subgraph (with perfect completeness). The best known FPT hardness of approximation under Gap-ETH of Densest $k$-Subgraph has inapproximability factor of $k^{o(1)}$ (where $o(1)$ can be any function that converges to zero as $k\to \mathrm{\infty }$)[1]. On the other hand, under a non-standard “Strongish Planted Clique Hypothesis”, this factor can be improved to $o(k)$[5]. Open Question: Can we prove the same hardness under Gap-ETH?

In the capacitated vehicle routing problem, we are given a metric space with a vertex called depot and a set of vertices called terminals. The goal is to find a minimum length collection of tours starting and ending at the depot such that each tour visits at most $k$ terminals, and each terminal is visited by some tour. We consider this problem in the Euclidean plane. The best-to-date approximation ratio was $2+ϵ$ using the iterated tour partitioning technique introduced by Haimovich and Rinnooy Kan. It is an open question whether there is a better-than-$2$ approximation.