patternMinor
Does $\#W$[1]-hardness imply approximation hardness?
Viewed 0 times
implyapproximationdoeshardness
Problem
Let $\Pi$ be a parametrized counting problem, where the parameter is the solution cost, e.g. counting the number of $k$-sized vertex cover in a graph, parametrized by $k$.
Assume that $\Pi$ is $\#W$[1]-complete (a known problem for example would be counting the number of simple paths of length $k$ in a graph).
Does it imply that $\Pi$ is $APX$-hard (i.e. no PTAS for the problem exists unless $P=NP$)?
Note that when discussing a parameter which is the cost of solution it makes sense to discuss the approximation hardness (e.g. see this question), as opposed to other popular parametrizations.
Assume that $\Pi$ is $\#W$[1]-complete (a known problem for example would be counting the number of simple paths of length $k$ in a graph).
Does it imply that $\Pi$ is $APX$-hard (i.e. no PTAS for the problem exists unless $P=NP$)?
Note that when discussing a parameter which is the cost of solution it makes sense to discuss the approximation hardness (e.g. see this question), as opposed to other popular parametrizations.
Solution
$\mathrm{W}[1]$-hardness implies that a problem has no eptas unless (at least) $\mathrm{W}[1] = \mathrm{FPT}$ (having an eptas implies parameterized tractability for the standard solution size parameterization), but there are problems with a ptas that are $\mathrm{W}[1]$-hard (i.e. not $\mathrm{APX}$-hard unless $\mathrm{APX} = \mathrm{PTAS}$).
Transferring this to $\#\mathrm{W}[1]$-hardness, you can at least say that a $\#\mathrm{W}[1]$-hard problem still has no eptas, but I don't think a stronger statement can be made a priori. Turning to speculation, I suspect it's also not true that $\mathrm{APX}$-hardness immediately follows from $\#\mathrm{W}[1]$-hardness in general, though perhaps something may be said for higher classes, such as the counting version of $\mathrm{para}\text{-}\mathrm{NP}$.
Transferring this to $\#\mathrm{W}[1]$-hardness, you can at least say that a $\#\mathrm{W}[1]$-hard problem still has no eptas, but I don't think a stronger statement can be made a priori. Turning to speculation, I suspect it's also not true that $\mathrm{APX}$-hardness immediately follows from $\#\mathrm{W}[1]$-hardness in general, though perhaps something may be said for higher classes, such as the counting version of $\mathrm{para}\text{-}\mathrm{NP}$.
Context
StackExchange Computer Science Q#28689, answer score: 3
Revisions (0)
No revisions yet.