Klam value

In the parameterized complexity of algorithms, the klam value of a parameterized algorithm is a number that bounds the parameter values for which the algorithm might reasonably be expected to be practical.[1] An algorithm with a higher klam value can be used for a wider range of parameter values than another algorithm with a lower klam value. The klam value was first defined by Downey and Fellows (1999),[2][3] and has since been used by other researchers in parameterized complexity both as a way of comparing different algorithms to each other and in order to set goals for future algorithmic improvements.

Definition

An algorithm is said to be fixed-parameter tractable if the number of elementary operations it performs has a bound of the form ${\displaystyle O(n^{c})+f(k)}$, where ${\displaystyle n}$ is some measure of the input size (such as the number of vertices in a graph), ${\displaystyle k}$ is a parameter describing the complexity of the input (such as the treewidth of the graph), ${\displaystyle c}$ is a constant that does not depend on ${\displaystyle n}$ or ${\displaystyle k}$, and ${\displaystyle f}$ is a computable function.

Given a time bound of this form, the klam value of the algorithm (or more properly of the time bound) is defined to be the largest value of ${\displaystyle k}$ such that ${\displaystyle f(k)}$ does not exceed "some reasonable absolute bound on the maximum number of steps of any computation".[1] More precisely both Downey & Fellows (1999) and Niedermeier (1998) use the number 10²⁰ as this bound, and this has been followed by later researchers. To prevent artificially improving the klam value of an algorithm by putting more of its complexity into the ${\displaystyle O(n^{c})}$ part of the time bound, Downey & Fellows (1999) also limit ${\displaystyle c}$ to be at most three, valid for many known fixed-parameter tractable algorithms.

Examples

Niedermeier (1998) cites the example of vertex cover, with its natural parameter (the number of vertices in the cover). At that time the best known parameterized time bound had ${\displaystyle f(k)=O(k^{2}1.3248^{k})}$. Solving ${\displaystyle k^{2}1.3248^{k}=10^{20}}$ gives a klam value of approximately 129. However, the ${\displaystyle k^{2}}$ part of the time bound can be simplified out of it, giving a bound of the form ${\displaystyle O(1.3248^{k})}$ with both a larger constant factor hidden in the O-notation and a larger base of the exponent hidden in its approximate decimal value. For a simple exponential bound ${\displaystyle f(k)=c^{k}}$such as this one, one can solve directly ${\displaystyle k=20/\log _{10}c}$ from which Niedermeier derives a klam value of approximately 165. Subsequent research has developed parameterized vertex cover algorithms with ${\displaystyle f(k)=O(1.2738^{k})}$[4] giving a klam value of approximately 190. That is, one can conclude from this analysis that vertex cover instances with cover size greater than 190 are out of reach of this algorithm, but instances whose cover size is sufficiently far below this limit are likely to be solvable.

Another example of a problem in which the klam value has been explicitly used as a goal for future research is the maximum leaf spanning tree problem, in which the goal is to find a spanning tree of a graph with as many leaf nodes as possible (parameterized by the number of leaves). Fellows et al. (2000) develop an algorithm for this problem which they compare using the klam value to previous work on the same problem: previous algorithms had klam values of 1 and 5, and theirs has a klam value of 16.[5] However, they also suggest that it should be possible to provide improved algorithms for this problem with a klam value of at least 50. Although this remains open, several later papers have incrementally improved the klam value of this problem to 37.[6]

References

1. Niedermeier, Rolf (1998), "Some prospects for efficient fixed parameter algorithms", in Rovan, Branislav (ed.), SOFSEM'98: Theory and Practice of Informatics, Lecture Notes in Computer Science, 1521, Springer, pp. 168–185.
2. Downey, R. G.; Fellows, M. R. (1999), Parameterized Complexity, Monographs in Computer Science, Springer, pp. 13–14, doi:10.1007/978-1-4612-0515-9, ISBN 0-387-94883-X, MR 1656112.
3. Niedermeier (1998) uses the klam value and was published earlier than Downey & Fellows (1999), but gives credit to Downey and Fellows for the concept.
4. Chen, Jianer; Kanj, Iyad A.; Xia, Ge (2006), "Improved parameterized upper bounds for vertex cover", MFCS 2006: Mathematical Foundations of Computer Science, Lecture Notes in Computer Science, 4162, Springer, pp. 238–249, doi:10.1007/11821069_21, MR 2298181.
5. Fellows, Michael R.; McCartin, Catherine; Rosamond, Frances A.; Stege, Ulrike (2000), "Coordinatized kernels and catalytic reductions: an improved FPT algorithm for max leaf spanning tree and other problems", FST-TCS 2000: Foundations of Software Technology and Theoretical Computer Science, Lecture Notes in Comput. Sci., 1974, Springer, Berlin, pp. 240–251, doi:10.1007/3-540-44450-5_19, MR 1850108.
6. Binkele-Raible, Daniel; Fernau, Henning (2014), "A parameterized measure-and-conquer analysis for finding a k-leaf spanning tree in an undirected graph", Discrete Mathematics & Theoretical Computer Science, 16 (1): 179–200, MR 3188035.