2
$\begingroup$

In the setting of parameterized algorithms, we are typically given the problem instance as well as the value of the parameter.

However, it seems like in applications the value of the parameter should be unknown in advance. I know that oftentimes one can "guess" the value of the parameter by enumerating through all possibilities, but this seems inefficient.

My question is: Is there a case of a parameterized problem where the parameter isn't easily computable from the input, so that the problem is FPT if the parameter is given as part of the input, but not known to be FPT if the parameter is not given?

$\endgroup$
4
  • $\begingroup$ To the best of my knowledge, it is still open whether clique-width can be computed in FPT while many problems are known to be FPT when parametrized by clique-width (e.g., Courcelle's Theorem). But this may not be what you are looking for since it can still be done in FPT via approximation (though the approximation is pretty bad). $\endgroup$
    – holf
    Mar 16 at 10:29
  • $\begingroup$ I'm really just trying to understand whether knowing the parameter can significantly change the tractability of a problem. Or some justification as to why it is always assumed that the parameter is known to the algorithm. $\endgroup$ Mar 16 at 18:17
  • $\begingroup$ This is helpful. Would tree-width also be an example of this? Many problems are FPT wrt tree-width, but computing the tree-width of a graph is NP-hard. However, maybe computing the tree-width of a graph is FPT with respect to the tree-width $\endgroup$ Mar 16 at 18:19
  • 2
    $\begingroup$ Computing treewidth is indeed FPT in the treewidth so it will not work. You can achieve what you want by choosing an "unreasonable" parameter. You can choose parameter $cheat_L$ such that $cheat_L(x) = 1$ if $x \in L$ and $0$ otherwise. Then $(L, cheat_L)$ is indeed FPT but it tells you nothing when the parameter is not given. $\endgroup$
    – holf
    Mar 16 at 18:34

1 Answer 1

2
$\begingroup$

I turn my different comments into an answer as I think it gives most answers.

The original definition of FPT states that a parametrized problem $(L, p)$ is FPT if there exists an algorithm deciding whether $x \in L$ in time $f(k)poly(n)$ where $k=p(x)$ and $n = |x|$ for some computable function $f$.

From that definition, $k$ is not explicitly provided in the input. Thus, any FPT algorithm using the fact that some parameter of the input is bounded has to do it from the input alone, by computing it explicitly (e.g., by computing a tree decomposition of a graph in case of bounded treewidth), or implicitly (e.g., by using some heuristic whose complexity is naturally FPT).

That being said, one often finds in the literature, statements of the form:

Theorem 1: Given $x$ and some additional data structure $D_x$ witnessing that $p(x) \leq k$, one can decide whether $x \in L$ in time $f(k)poly(n)$.

Such a statement is not enough to prove that $(L,p)$ is in FPT and one can come up with artificial examples where it is indeed not the case.

Consider for example the parameter $cheat_L(x)$ which is $1$ if $x\in L$ and $0$ otherwise. If $cheat_L(x)$ is provided in the input, one can indeed decide whether $x \in L$ in $O(1)$. However, $(L, cheat_L)$ is in FPT iff one can decide $x \in L$ in time $f(k)poly(n)$. However, $k$ being at most $1$, it is equivalent to say that $L$ is in $P$.

Nevertheless, statements like Theorem 1 found in the literature are usually relying on another property of the parameter to derive the fact that $(L,p)$ is in FPT (sometimes explicitly, sometimes implicitly).

If you know that given $x$ with $p(x)=k$, one can compute the data structure $D_x$ in FPT time $g(k)poly(n)$ then you can conclude that $(L,p)$ is indeed FPT by first computing $D_x$ and then using the algorithm of Theorem 1 for a total time of $(f+g)(k)poly(n)$.

This situation often arises with treewidth. Usually, the algorithms are described using a tree decomposition of with $k$ and their complexity is described as a function of $k$. It is sufficient in this case to derive an FPT algorithm since it is known that given a graph $G$, one can compute a tree decomposition of width $tw(G)$ in time $2^{O(tw(G))}poly(|G|)$ [Bod96].

A somewhat similar situation arises with clique-width. While it remains open whether clique-width can be computed in FPT time, one can compute a (bad) approximation of it. Given a graph of clique width $k$, one can compute a decomposition of with $2^{O(k)}$ in time $f(k)poly(|G|)$ [Oum06].

Thus, combined with statements like Theorem 1, it is enough to prove that some problems are FTP wrt clique-width. However, the dependency on the parameter is badly degraded by the exponential approximation.

Hence, authors prefer to write statements like Theorem 1 instead of packing everything together. It makes the result more modular since any improvements on clique-width computation could directly be plugged into their algorithm.

References

[Bod96] Bodlaender, Hans L. (1996), "A linear time algorithm for finding tree-decompositions of small treewidth", SIAM Journal on Computing, 25 (6): 1305–1317

[Oum06] Oum, Sang-il; Seymour, Paul (2006), "Approximating clique-width and branch-width", Journal of Combinatorial Theory, Series B, 96 (4): 514–528,

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