Valor klam

En el campo de la complejidad parametrizada de algoritmos, el valor klam de un algoritmo parametrizado es un número que limita los valores de los parámetros para los cuales se podría esperar razonablemente que el algoritmo sea práctico.^[1]​ Un algoritmo con un valor klam más alto puede utilizarse para un rango más amplio de valores de parámetros que otro algoritmo con un valor klam más bajo. El valor klam fue definido inicialmente por Downey y Fellows (1999),^[2]​^[3]​ y desde entonces ha sido utilizado por otros investigadores en complejidad parametrizada, tanto para comparar diferentes algoritmos entre sí como para establecer objetivos para futuras mejoras algorítmicas.

Se dice que un algoritmo es manejable con parámetros fijos si el número de operaciones elementales que realiza tiene un límite de la forma ${\displaystyle O(n^{c})+f(k)}$, donde ${\displaystyle n}$ es una medida del tamaño de la entrada (como el número de vértices en un grafo), ${\displaystyle k}$ es un parámetro que describe la complejidad de la entrada (como la anchura del árbol del grafo), ${\displaystyle c}$ es una constante que no depende de ${\displaystyle n}$ ni de ${\displaystyle k}$, y ${\displaystyle f}$ es una función computable.

Dado un límite temporal de esta forma, el valor klam del algoritmo (o, más propiamente, el límite temporal) se define como el mayor valor de ${\displaystyle k}$ tal que ${\displaystyle f(k)}$ no exceda un límite absoluto razonable en el número máximo de pasos de cualquier cálculo.^[1]​ Más precisamente, tanto Downey y Fellows (1999) como Niedermeier (1998) utilizan el número 10²⁰ como límite, y esto ha sido seguido por investigadores posteriores. Para evitar mejorar artificialmente el valor klam de un algoritmo al asignar mayor complejidad a la parte ${\displaystyle O(n^{c})}$ del límite de tiempo, Downey y Fellows (1999) también limita ${\displaystyle c}$ a un máximo de tres, lo cual es válido para muchos algoritmos manejables con parámetros fijos conocidos.

Niedermeier (1998) cita el ejemplo de cobertura de vértices, con su parámetro natural (el número de vértices en la cubierta). En aquel entonces, el límite de tiempo parametrizado conocido era ${\displaystyle f(k)=O(k^{2}1.3248^{k})}$. Resolviendo ${\displaystyle k^{2}1.3248^{k}=10^{20}}$ se obtiene un valor klam de aproximadamente 129. Sin embargo, la parte ${\displaystyle k^{2}}$ del límite de tiempo puede simplificarse, obteniendo un límite de la forma ${\displaystyle O(1.3248^{k})}$ con un factor constante mayor oculto en la notación O y una base del exponente mayor oculta en su valor decimal aproximado. Para una cota exponencial simple ${\displaystyle f(k)=c^{k}}$ como esta, se puede resolver directamente ${\displaystyle k=20/\log _{10}c}$, de la que Niedermeier deriva un valor klam de aproximadamente 165. Investigaciones posteriores han desarrollado algoritmos de cobertura de vértices parametrizados, con ${\displaystyle f(k)=O(1.2738^{k})}$^[4]​ que proporciona un valor klam de aproximadamente 190. Es decir, de este análisis se puede concluir que las instancias de cobertura de vértices con un tamaño de cobertura superior a 190 están fuera del alcance de este algoritmo, pero las instancias con un tamaño de cobertura muy inferior a este límite probablemente sean solucionables.

Otro ejemplo de un problema en el que el valor klam se ha utilizado explícitamente como objetivo para futuras investigaciones es el árbol de máxima expansión de hojas, cuyo objetivo es encontrar un árbol de expansión de un grafo con el mayor número posible de nodos hoja (parametrizado por el número de hojas). Fellows et al. (2000) desarrolló un algoritmo para este problema, que comparan utilizando el valor klam con trabajos previos sobre el mismo problema: los algoritmos anteriores tenían valores klam de 1 y 5, y el suyo tiene un valor klam de 16.^[5]​ Sin embargo, también sugieren que debería ser posible proporcionar algoritmos mejorados para este problema con un valor klam de al menos 50. Aunque este tema aún está abierto, varios artículos posteriores han mejorado gradualmente el valor klam de este problema hasta 37.^[6]​