W[1]-hard problems with FPT time approximation algorithms

Question

I'm looking for problems that are hard to solve in FPT time but has an approximation algorithm. That is, problems that are:

R1. W[1]-hard.

R2. Admit a (preferably constant) approximation algorithm in FPT time.

The problem I'm familiar with is counting the number of simple paths of length $k$ in a graph. It is known to be #W[1]-hard, but admits a $(1+\epsilon)$-approximation in FPT time (for any constant $\epsilon$).

Also interesting would be problems that satisfy R1 and R2, and also:

R3. There exists $\epsilon>0$ such that the problem is not $(1+\epsilon)$ approximable in FPT time (unless W[1]=FPT).

What other problems satisfy R1 and R2, and possibly R3?

Answer 1

In the Directed Odd Cycle Transversal problem the input is a graph $G$ and the task is to find a smallest set $S$ of vertices such that $G-S$ has no (directed) cycles of odd length. In the parameterized version we are also given an integer $k$ and asked whether a solution of size at most $k$ exists.

In this paper we prove that (R1) the problem is W$[1]$-hard, (R2) that it admits a factor 2 approximation algorithm in time $2^{k^{O(1)}}n^{O(1)}$, and that (R3’) assuming a hypothesis somewhat stronger than $FPT \neq W[1]$ that there exists an $\epsilon > 0$ such that the problem does not admit a $(1+\epsilon)$ approximation algorithm in time $f(k)n^{O(1)}$.

Answer 2

In [1], the authors prove that MaxSAT parametrized by the clique-width (resp. neighbor diversity) of the incidence graph of the CNF formula has an FPT-AS (Fixed Parameter Tractable Approximation Scheme) but it is known that MaxSAT parametrized by clique-width (resp. neighbor diversity) is W[1]-hard.

The theorem mostly relies on a result of [2] that roughly says that a graphs of bounded clique-width without large cliques also has bounded treewidth.They thus smartly trim the formula so that they do not have large clique in the incidence graph and solve the reduced formula in FPT time using a well-known algorithm for MaxSAT on bounded treewidth. I guess this approach may work in other problems as well.

[1] Holger Dell, Eun Jung Kim, Michael Lampis, Valia Mitsou, Tobias Mömke: Complexity and Approximability of Parameterized MAX-CSPs. IPEC 2015

[2] Gurski, F., & Wanke, E. (2000, June). The tree-width of clique-width bounded graphs without K n, n. In International Workshop on Graph-Theoretic Concepts in Computer Science (pp. 196-205). Springer, Berlin, Heidelberg.

Answer 3

In Defective Coloring we are given a graph $G$ and an integer $\Delta^*$ and are asked to partition the vertices of $G$ into the minimum possible number of color classes so that each class induces a graph of maximum degree at most $\Delta^*$. (If $\Delta^*=0$ this problem is just Coloring).

In [1] we showed the following regarding this problem parameterized by treewidth: (R1) the problem is W[1]-hard; (R2) the minimum number of colors can be 2-approximated in FPT time; (R3) there is no $(3/2-\epsilon)$-approximation in FPT time, under standard assumptions.

[1] Rémy Belmonte, Michael Lampis, and Valia Mitsou: Parameterized (Approximate) Defective Coloring. STACS '18.

Answer 4

The k-cut problem is to remove a minimum number of edges to create at least k components. W[1] hard when parameterized by k but admits a 2-approximation for any k.

Answer 5

(This question was asked two years ago, but I'll post the answer for other people who may see this question.)

In the Capacitated $k$-median problem we are given a set $F$ of facilities, each facility $f$ with a capacity $u_f \in \mathbb{Z}_{\geq0}$, a set $C$ of clients, a metric $d$ over $F\cup C$ and an upper bound $k$ on the number of facilities we can open. A solution to the problem is a set $S \subseteq F$ of at most $k$ open facilities and a connection assignment $\phi:C\rightarrow S$ of clients to open facilities such that $|\phi^{-1}(f)| \leq u_{f}$ for every facility $f \in S$. We want to find a solution that minimizes the connection cost $\sum_{c\in C} d(c,\phi(C))$. The problem is $W[2]$-hard when parameterized by $k$. In this paper, the authors showed that there exists an FPT-time constant factor approximation algorithm for the problem. (in this case, you can check GAP-ETH for some negative results. See https://arxiv.org/pdf/1708.04218.pdf)