<p>In <em>Defective Coloring</em> 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 <em>Coloring</em>).</p>

<p>In [1] we showed the following regarding this problem <em>parameterized by treewidth</em>: (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.</p>

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

CC BY-SA 3.0
2018-05-01T22:01:03.163Z
2018-05-01T22:01:03.163Z
Michael Lampis
<p>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. </p>

<p>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.</p>

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

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

CC BY-SA 3.0
2018-04-29T19:05:58.727Z
2018-04-29T19:05:58.727Z
holf
<p>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.</p>

CC BY-SA 4.0
2018-05-02T01:58:51.183Z
Under Small Set Expansion hypothesis it is known that k-cut does not admit a $(2-\epsilon)$-approximation. A recent paper of Gupta etal in SODA 2018 shows that one can get a $(2-\delta)$-approximation in $2^{O(k)} n^{O(1)}$ time where $\delta > 0$ is a fixed but small constant.
Chandra Chekuri
CC BY-SA 3.0
2018-05-01T22:12:46.977Z
2018-05-01T22:12:46.977Z
Chandra Chekuri
<p>(This question was asked two years ago, but I'll post the answer for other people who may see this question.)</p>

<p>In the <em>Capacitated <span class="math-container">$k$</span>-median</em> problem we are given a set <span class="math-container">$F$</span> of facilities, each facility <span class="math-container">$f$</span> with a capacity <span class="math-container">$u_f \in \mathbb{Z}_{\geq0}$</span>, a set <span class="math-container">$C$</span> of clients, a metric <span class="math-container">$d$</span> over <span class="math-container">$F\cup C$</span> and an upper bound <span class="math-container">$k$</span> on the number of facilities we can open. A solution to the problem is a set <span class="math-container">$S \subseteq F$</span> of at most <span class="math-container">$k$</span> open facilities and a connection assignment <span class="math-container">$\phi:C\rightarrow S$</span> of clients to open facilities such that <span class="math-container">$|\phi^{-1}(f)| \leq u_{f}$</span> for every facility <span class="math-container">$f \in S$</span>. We want to find a solution that minimizes the connection cost <span class="math-container">$\sum_{c\in C} d(c,\phi(C))$</span>. The problem is <span class="math-container">$W[2]$</span>-hard when parameterized by <span class="math-container">$k$</span>. In <a href="https://arxiv.org/pdf/1809.05791.pdf" rel="noreferrer">this paper</a>, 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 <a href="https://arxiv.org/pdf/1708.04218.pdf" rel="noreferrer">https://arxiv.org/pdf/1708.04218.pdf</a>)</p>

CC BY-SA 4.0
2020-01-29T17:00:57.513Z
2020-01-29T17:06:58.180Z
2020-01-29T17:06:58.180Z
Amir Nikabadi
<p>In the <em>Directed Odd Cycle Transversal</em> 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. </p>

<p>In <a href="https://arxiv.org/abs/1704.04249" rel="noreferrer">this paper</a> 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 &gt; 0$ such that the problem does not admit a $(1+\epsilon)$ approximation algorithm in time $f(k)n^{O(1)}$.</p>

CC BY-SA 3.0
2018-04-29T15:32:44.767Z
2018-04-29T15:32:44.767Z
daniello
<p>I'm looking for problems that are hard to solve in FPT time but has an approximation algorithm. That is, problems that are:</p>

<p>R1. W[1]-hard.</p>

<p>R2. Admit a (preferably constant) approximation algorithm in FPT time.</p>

<p>The problem I'm familiar with is counting the number of simple paths of length $k$ in a graph. <a href="https://people.csail.mit.edu/rrw/presentations/counting-k-paths.pdf" rel="noreferrer">It is known to be #W[1]-hard</a>, but <a href="https://www.math.ias.edu/csdm/files/Archives/8-9/nalon_balanced_hashing_color_coding.pdf" rel="noreferrer">admits a $(1+\epsilon)$-approximation in FPT time</a> (for any constant $\epsilon$).</p>

<p>Also interesting would be problems that satisfy R1 and R2, and also:</p>

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

<blockquote>
  <p>What other problems satisfy R1 and R2, and possibly R3?</p>
</blockquote>

<ds.algorithms><approximation-algorithms><parameterized-complexity><fixed-parameter-tractable>
W[1]-hard problems with FPT time approximation algorithms
R B
# W[1]-hard problems with FPT time approximation algorithms

(Asked by: username_0 on 2018-04-29)

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](https://people.csail.mit.edu/rrw/presentations/counting-k-paths.pdf), but [admits a $(1+\epsilon)$-approximation in FPT time](https://www.math.ias.edu/csdm/files/Archives/8-9/nalon_balanced_hashing_color_coding.pdf) (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?

**Tags:** ds.algorithms, approximation-algorithms, parameterized-complexity, fixed-parameter-tractable


---

## 5 answers

### Answer by username_5 on 2018-04-29. Score: 9 | Accepted answer

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](https://arxiv.org/abs/1704.04249) 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 by username_1 on 2018-05-01. Score: 6

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, username_1, and Valia Mitsou: Parameterized (Approximate) Defective Coloring. STACS '18.


---

### Answer by username_2 on 2018-04-29. Score: 6

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, username_1, 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 by username_3 on 2018-05-01. Score: 5

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.

> **Comments:**
> **username_3**: Under Small Set Expansion hypothesis it is known that k-cut does not admit a $(2-\epsilon)$-approximation. A recent paper of Gupta etal in SODA 2018 shows that one can get a $(2-\delta)$-approximation in $2^{O(k)} n^{O(1)}$ time where $\delta > 0$ is a fixed but small constant.  

---

### Answer by username_4 on 2020-01-29. Score: 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](https://arxiv.org/pdf/1809.05791.pdf), 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>)


---

