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,[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.
An algorithm is said to be fixed-parameter tractable if the number of elementary operations it performs has a bound of the form
O(nc)+f(k)
n
k
c
n
k
f
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
k
f(k)
O(nc)
c
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
f(k)=O(k21.3248k)
k21.3248k=1020
k2
O(1.3248k)
f(k)=ck
k=20/log10c
f(k)=O(1.2738k)
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). 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]