9
$\begingroup$

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?

$\endgroup$
7
$\begingroup$

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)}$.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Chandra Chekuri May 2 '18 at 1:58

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.