19
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ 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. $\endgroup$
    – Juho
    Oct 3, 2020 at 17:55
  • 1
    $\begingroup$ Yes, e.g., for MaxCut (arxiv.org/abs/1905.10902) or for independent set (arxiv.org/abs/2008.05180). See also the references in these papers. $\endgroup$
    – tranisstor
    Oct 7, 2020 at 6:54

1 Answer 1

Reset to default
26
$\begingroup$

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] 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].

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

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

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

Improve this answer
$\endgroup$
2
  • 4
    $\begingroup$ It is worth mentioning the PACE challenge, which has, among other things lead to order of magnitude improvements on the best programs computing treewidth. $\endgroup$
    – daniello
    Oct 3, 2020 at 2:45
  • 2
    $\begingroup$ I agree completely, it would actually make sense to have another answer discussing PACE and its impact on practical computing $\endgroup$
    – Christian Komusiewicz
    Oct 3, 2020 at 20:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.