<p>There are several examples of problems where a parameterized algorithm performs well in practice. Let me mention two such problems.</p>
<p>In the <span class="math-container">$k$</span>-Path problem where we are looking for a simple path of length <span class="math-container">$k$</span>. Alon, Yuster and Zwick [<a href="https://doi.org/10.1145/210332.210337" rel="noreferrer">1</a>] showed that this problem can be solved in <span class="math-container">$2^{O(k)}\cdot n$</span> time on <span class="math-container">$n$</span>-vertex graphs. A weighted version of <span class="math-container">$k$</span>-Path has applications in computational biology and the biologically interesting paths have length at most 20. Several of the implemented algorithms successfully use the color coding technique [<a href="https://doi.org/10.1089/cmb.2006.13.133" rel="noreferrer">2</a>].</p>
<p>The Clique problem parameterized by the solution size <span class="math-container">$k$</span> has presumably no FPT algorithm, but Clique parameterized by the degeneracy <span class="math-container">$d$</span> of the input graph has an FPT algorithm. More precisely, all maximal cliques of an <span class="math-container">$n$</span>-vertex graph can be enumerated in <span class="math-container">$O(3^{d/3}\cdot n)$</span> time [<a href="https://doi.org/10.1145/2543629" rel="noreferrer">3</a>]. Since many real-world graphs (e.g. social networks) have small degeneracy, this running time bound explains why clique enumeration is feasible on these graphs.</p>
<p>I would say there is a crucial difference between the two results. In the case of <span class="math-container">$k$</span>-Path, the color coding technique is an FPT technique that was developed in theory and was later turned into a practical algorithm. In the case of Clique, the central technique of the FPT algorithm, which, roughly speaking, is to enumerate first the cliques containing a minimum-degree vertex <span class="math-container">$v$</span> and then enumerating all cliques not containing <span class="math-container">$v$</span>, was already known, in some form, before the theoretical analysis and probably used in several implementations. Hence, I would say that for <span class="math-container">$k$</span>-Path, parameterized algorithmics has <em>led</em> to better algorithms, and for Clique, parameterized algorithmics rather <em>explains</em> why algorithms are good.</p>
<p>[<a href="https://doi.org/10.1145/210332.210337" rel="noreferrer">1</a>]: Alon, Yuster and Zwick: Color Coding.  J. ACM 42(4): 844-856 (1995) <a href="https://doi.org/10.1145/210332.210337" rel="noreferrer">https://doi.org/10.1145/210332.210337</a></p>
<p>[<a href="https://doi.org/10.1089/cmb.2006.13.133" rel="noreferrer">2</a>] Jacob Scott, Trey Ideker, Richard M. Karp, Roded Sharan: <a href="https://doi.org/10.1089/cmb.2006.13.133" rel="noreferrer">Efficient Algorithms for Detecting Signaling Pathways in Protein Interaction Networks</a>. J. Comput. Biol. 13(2): 133-144 (2006)</p>
<p>[<a href="https://doi.org/10.1145/2543629" rel="noreferrer">3</a>] David Eppstein, Maarten Löffler, Darren Strash:
<a href="https://doi.org/10.1145/2543629" rel="noreferrer">Listing All Maximal Cliques in Large Sparse Real-World Graphs</a>. ACM J. Exp. Algorithmics 18 (2013)</p>

CC BY-SA 4.0
2020-10-03T02:45:38.297Z
It is worth mentioning the PACE challenge, which has, among other things lead to order of magnitude improvements on the best programs computing treewidth.
daniello
CC BY-SA 4.0
2020-10-03T20:11:55.537Z
I agree completely, it would actually make sense to have another answer discussing PACE and its impact on practical computing
Christian Komusiewicz
CC BY-SA 4.0
2020-10-02T11:42:21.993Z
2020-10-02T11:42:21.993Z
Christian Komusiewicz
<p>I know that for the vertex cover problem, if we know that the parameter <span class="math-container">$k$</span> (which is the number of vertices in the solution) is small, then we can expect to solve it feasibly in practice. So far, this is the only example I've seen on Downey, Rodney G. and Michael R. Fellows. &quot;Parameterized Complexity&quot;.</p>
<p>Has considering a problem in a parameterized way led to different algorithms that end up to be feasible in practice? Or is the Parameterized Complexity Theory just a tool for evaluating complexity of problems?</p>

CC BY-SA 4.0
2020-10-03T17:55:30.007Z
You can do a scan over e.g., ALENEX/SEA papers from the recent years to see a good amount of examples of FPT algorithms that are practical.
Juho
CC BY-SA 4.0
2020-10-07T06:54:40.267Z
Yes, e.g., for MaxCut (https://arxiv.org/abs/1905.10902) or for independent set (https://arxiv.org/abs/2008.05180). See also the references in these papers.
tranisstor
<cc.complexity-theory><ds.algorithms><complexity-classes><time-complexity><parameterized-complexity>
Has parameterized complexity led to better algorithms?
Felipe
# Has parameterized complexity led to better algorithms?

(Asked by: username_0 on 2020-10-02)

I know that for the vertex cover problem, if we know that the parameter $k$ (which is the number of vertices in the solution) is small, then we can expect to solve it feasibly in practice. So far, this is the only example I've seen on Downey, Rodney G. and Michael R. Fellows. "Parameterized Complexity".

Has considering a problem in a parameterized way led to different algorithms that end up to be feasible in practice? Or is the Parameterized Complexity Theory just a tool for evaluating complexity of problems?

**Tags:** cc.complexity-theory, ds.algorithms, complexity-classes, time-complexity, parameterized-complexity
> **Comments:**
> **username_1**: You can do a scan over e.g., ALENEX/SEA papers from the recent years to see a good amount of examples of FPT algorithms that are practical.  
> **username_2**: Yes, e.g., for MaxCut (https://arxiv.org/abs/1905.10902) or for independent set (https://arxiv.org/abs/2008.05180). See also the references in these papers.  

---

## 1 answers

### Answer by username_3 on 2020-10-02. Score: 26 | Accepted answer

There are several examples of problems where a parameterized algorithm performs well in practice. Let me mention two such problems.

In the $k$-Path problem where we are looking for a simple path of length $k$. Alon, Yuster and Zwick [[1](https://doi.org/10.1145/210332.210337)] showed that this problem can be solved in $2^{O(k)}\cdot n$ time on $n$-vertex graphs. A weighted version of $k$-Path has applications in computational biology and the biologically interesting paths have length at most 20. Several of the implemented algorithms successfully use the color coding technique [[2](https://doi.org/10.1089/cmb.2006.13.133)].

The Clique problem parameterized by the solution size $k$ has presumably no FPT algorithm, but Clique parameterized by the degeneracy $d$ of the input graph has an FPT algorithm. More precisely, all maximal cliques of an $n$-vertex graph can be enumerated in $O(3^{d/3}\cdot n)$ time [[3](https://doi.org/10.1145/2543629)]. Since many real-world graphs (e.g. social networks) have small degeneracy, this running time bound explains why clique enumeration is feasible on these graphs.

I would say there is a crucial difference between the two results. In the case of $k$-Path, the color coding technique is an FPT technique that was developed in theory and was later turned into a practical algorithm. In the case of Clique, the central technique of the FPT algorithm, which, roughly speaking, is to enumerate first the cliques containing a minimum-degree vertex $v$ and then enumerating all cliques not containing $v$, was already known, in some form, before the theoretical analysis and probably used in several implementations. Hence, I would say that for $k$-Path, parameterized algorithmics has *led* to better algorithms, and for Clique, parameterized algorithmics rather *explains* why algorithms are good.

[[1](https://doi.org/10.1145/210332.210337)]: Alon, Yuster and Zwick: Color Coding. J. ACM 42(4): 844-856 (1995) <https://doi.org/10.1145/210332.210337>

[[2](https://doi.org/10.1089/cmb.2006.13.133)] Jacob Scott, Trey Ideker, Richard M. Karp, Roded Sharan: [Efficient Algorithms for Detecting Signaling Pathways in Protein Interaction Networks](https://doi.org/10.1089/cmb.2006.13.133). J. Comput. Biol. 13(2): 133-144 (2006)

[[3](https://doi.org/10.1145/2543629)] David Eppstein, Maarten Löffler, Darren Strash:
[Listing All Maximal Cliques in Large Sparse Real-World Graphs](https://doi.org/10.1145/2543629). ACM J. Exp. Algorithmics 18 (2013)

> **Comments:**
> **username_4**: It is worth mentioning the PACE challenge, which has, among other things lead to order of magnitude improvements on the best programs computing treewidth.  
> **username_3**: I agree completely, it would actually make sense to have another answer discussing PACE and its impact on practical computing  

---

