<p>I turn my different comments into an answer as I think it gives most answers.</p>
<p>The original definition of FPT states that a parametrized problem <span class="math-container">$(L, p)$</span> is FPT if there exists an algorithm deciding whether <span class="math-container">$x \in L$</span> in time <span class="math-container">$f(k)poly(n)$</span> where <span class="math-container">$k=p(x)$</span> and <span class="math-container">$n = |x|$</span> for some computable function <span class="math-container">$f$</span>.</p>
<p>From that definition, <span class="math-container">$k$</span> 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).</p>
<p>That being said, one often finds in the literature, statements of the form:</p>
<p><strong>Theorem 1:</strong> <em>Given <span class="math-container">$x$</span> and some additional data structure <span class="math-container">$D_x$</span> witnessing that <span class="math-container">$p(x) \leq k$</span>, one can decide whether <span class="math-container">$x \in L$</span> in time <span class="math-container">$f(k)poly(n)$</span></em>.</p>
<p>Such a statement is not enough to prove that <span class="math-container">$(L,p)$</span> is in FPT and one can come up with artificial examples where it is indeed not the case.</p>
<p>Consider for example the parameter <span class="math-container">$cheat_L(x)$</span> which is <span class="math-container">$1$</span> if <span class="math-container">$x\in L$</span> and <span class="math-container">$0$</span> otherwise. If <span class="math-container">$cheat_L(x)$</span> is provided in the input, one can indeed decide whether <span class="math-container">$x \in L$</span> in <span class="math-container">$O(1)$</span>. However, <span class="math-container">$(L, cheat_L)$</span> is in FPT iff one can decide <span class="math-container">$x \in L$</span> in time <span class="math-container">$f(k)poly(n)$</span>. However, <span class="math-container">$k$</span> being at most <span class="math-container">$1$</span>, it is equivalent to say that <span class="math-container">$L$</span> is in <span class="math-container">$P$</span>.</p>
<p>Nevertheless, statements like <strong>Theorem 1</strong> found in the literature are usually relying on another property of the parameter to derive the fact that <span class="math-container">$(L,p)$</span> is in FPT (sometimes explicitly, sometimes implicitly).</p>
<p>If you know that given <span class="math-container">$x$</span> with <span class="math-container">$p(x)=k$</span>, one can compute the data structure <span class="math-container">$D_x$</span> in FPT time <span class="math-container">$g(k)poly(n)$</span> then you can conclude that <span class="math-container">$(L,p)$</span> is indeed FPT by first computing <span class="math-container">$D_x$</span> and then using the algorithm of <strong>Theorem 1</strong> for a total time of <span class="math-container">$(f+g)(k)poly(n)$</span>.</p>
<p>This situation often arises with treewidth. Usually, the algorithms are described using a tree decomposition of with <span class="math-container">$k$</span> and their complexity is described as a function of <span class="math-container">$k$</span>. It is sufficient in this case to derive an FPT algorithm since it is known that given a graph <span class="math-container">$G$</span>, one can compute a tree decomposition of width <span class="math-container">$tw(G)$</span> in time <span class="math-container">$2^{O(tw(G))}poly(|G|)$</span> [Bod96].</p>
<p>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 <span class="math-container">$k$</span>, one can compute a decomposition of with <span class="math-container">$2^{O(k)}$</span> in time <span class="math-container">$f(k)poly(|G|)$</span> [Oum06].</p>
<p>Thus, combined with statements like <strong>Theorem 1</strong>, 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.</p>
<p>Hence, authors prefer to write statements like <strong>Theorem 1</strong> 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.</p>
<h1>References</h1>
<p>[Bod96] Bodlaender, Hans L. (1996), &quot;A linear time algorithm for finding tree-decompositions of small treewidth&quot;, SIAM Journal on Computing, 25 (6): 1305–1317</p>
<p>[Oum06] Oum, Sang-il; Seymour, Paul (2006), &quot;Approximating clique-width and branch-width&quot;, Journal of Combinatorial Theory, Series B, 96 (4): 514–528,</p>

CC BY-SA 4.0
2022-03-19T09:48:17.260Z
2022-03-19T09:48:17.260Z
holf
<p>In the setting of parameterized algorithms, we are typically given the problem instance as well as the value of the parameter.</p>
<p>However, it seems like in applications the value of the parameter should be unknown in advance. I know that oftentimes one can &quot;guess&quot; the value of the parameter by enumerating through all possibilities, but this seems inefficient.</p>
<p>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?</p>

CC BY-SA 4.0
2022-03-16T10:29:15.043Z
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).
holf
CC BY-SA 4.0
2022-03-16T18:17:31.827Z
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.
Karagounis Z
CC BY-SA 4.0
2022-03-16T18:19:20.080Z
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
Karagounis Z
CC BY-SA 4.0
2022-03-16T18:34:34.510Z
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.
holf
<ds.algorithms><graph-algorithms><parameterized-complexity><fixed-parameter-tractable>
Parameterized algorithm when the parameter is not known in advance?
Karagounis Z
# Parameterized algorithm when the parameter is not known in advance?

(Asked by: username_0 on 2022-03-15)

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?

**Tags:** ds.algorithms, graph-algorithms, parameterized-complexity, fixed-parameter-tractable
> **Comments:**
> **username_1**: 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).  
> **username_0**: 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.  
> **username_0**: 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  
> **username_1**: 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.  

---

## 1 answers

### Answer by username_1 on 2022-03-19. Score: 2 | Accepted answer

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,


---

