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.
Asked By : R B
Answered By : Luke Mathieson
$\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}$.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/28689
0 comments:
Post a Comment
Let us know your responses and feedback