El ancho de rango es un parámetro de ancho de gráfico utilizado en la teoría de grafos y la complejidad parametrizada , y definido mediante álgebra lineal .
Se define a partir de agrupamientos jerárquicos de los vértices de un grafo dado, que pueden visualizarse como árboles ternarios que tienen los vértices como sus hojas. Eliminar cualquier borde de un árbol de este tipo lo desconecta en dos subárboles y divide los vértices en dos subconjuntos. Los bordes del grafo que cruzan de un lado de la partición al otro pueden describirse mediante una matriz de biadyacencia ; para los fines del ancho de rango, esta matriz se define sobre el cuerpo finito GF(2) en lugar de usar números reales . El ancho de rango de un grafo es el máximo de los rangos de las matrices de biadyacencia, para un agrupamiento elegido para minimizar este máximo. [1]
El ancho de rango está estrechamente relacionado con el ancho de camarilla : , donde es el ancho de camarilla y el ancho de rango. Sin embargo, el ancho de camarilla es NP-difícil de calcular, para gráficos de gran ancho de camarilla, y su complejidad parametrizada es desconocida. Por el contrario, probar si el ancho de rango es como máximo una constante requiere un tiempo polinomial , e incluso cuando el ancho de rango no es constante, se puede aproximar, con una razón de aproximación constante , en tiempo polinomial. Por esta razón, el ancho de rango se puede utilizar como un sustituto más fácil de calcular para el ancho de camarilla. [1]
Un ejemplo de una familia de gráficos con un alto ancho de rango lo proporcionan los gráficos de cuadrícula cuadrada . Para un gráfico de cuadrícula, el ancho de rango es exactamente . [2]
