3
$\begingroup$

A parameterized problem is a subset $L \subseteq \Sigma^* \times \mathbb N$, where $\Sigma$ is a finite alphabet. A parameterized problem is fixed parameter tractable, if it could be decided in time $f(k)|x|^{O(1)}$ for some $(x,k) \in L$.

In terms of the problem definition, a Turing machine for $L$ has access to the parameter. I noted that for some algorithms, for example the kernelization of vertex cover, the algorithm indeed must have access to it, whereas for others, for example clique parametrized by maximal degree, it does not need access to the parameter. The algorithm for the latter simply looks into the neighbourhood of every vertex if it contains a clique, hence it runs in time $O(2^{\Delta} |x|)$, where $(x, \Delta) \in L$.

Was this ever noted? And if so, is there some notion like FPT without access to the parameter, i.e., a problem $L\subseteq \Sigma^*$ is in "FPT without access to the parameter", if it runs in time $f(k)|x|^{O(1)}$ for $x \in L$ and some number $k$ that depends on $x$ (I avoid the term parameter, as it is not given as input)? Or would it not make sense to consider such a class?

$\endgroup$
8
  • 1
    $\begingroup$ One thing to keep in mind is that, in the VC kernelisation example (and I suspect in many other cases), an algorithm that "needs access to" the parameter can be turned into an algorithm that doesn't with at most a polynomial blowup: Here, you can just try kernelizing and then solving for $k=1$, then for $k=2$, etc., until you find a solution (VC). This is at most $n$ times slower than the original algorithm. $\endgroup$ Jun 4 '20 at 14:55
  • 1
    $\begingroup$ @j_random_hacker Is it always the case the the parameter is polynomially bounded by $n$? Seems reasonable, but is not included in the definition. But if so, your arguments seems to be a proof that FPT = "FPT without access to the parameter". $\endgroup$
    – StefanH
    Jun 4 '20 at 15:21
  • $\begingroup$ Good question, but notice that the "try each possible value of $k$ starting at 1" VC algorithm I proposed is also at most $k$ times slower than the original algorithm, so (for this problem) it would not matter. Whether this is true for all FPT problems, I don't know -- but given that $k \in \mathbb{N}$, it looks like the same approach will work at least for all those FPT algorithms for which "A solution exists at $k=i$" implies "A solution exists for $k>i$". $\endgroup$ Jun 4 '20 at 18:39
  • $\begingroup$ I do not see why this "montonicity" criterium should be sufficient. I think what is sufficient is if the parameter value is bounded by some polynomial of the input size. But this does not has to be the case. For example for subset sum with target value $t$, the target value could be exponential in the input size. $\endgroup$
    – StefanH
    Jun 5 '20 at 13:50
  • $\begingroup$ Subset sum with target value $t$ is a good example. All that is required here is that the runtime of the final algorithm is $f(t)|x|^{O(1)}$, which easily holds if $f(t)$ increases by a factor of $t$. The fact that $f(t)$ can be an arbitrary function of $t$ allows a lot of leeway. $\endgroup$ Jun 5 '20 at 18:07

Your Answer

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

Browse other questions tagged or ask your own question.