7
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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