En teoría de grafos , una rama de las matemáticas, una completitud cordal de un grafo no dirigido G dado es un grafo cordal , en el mismo conjunto de vértices, que tiene a G como subgrafo. Una completitud cordal mínima es una completitud cordal tal que cualquier grafo formado al eliminar una arista ya no sería una completitud cordal. Una completitud cordal mínima es una completitud cordal con la menor cantidad posible de aristas.
Se puede utilizar un tipo diferente de compleción de acordes, uno que minimice el tamaño de la camarilla máxima en el gráfico de acordes resultante, para definir el ancho de árbol de G. Las compleciones de acordes también se pueden utilizar para caracterizar varias otras clases de gráficos, incluidos los gráficos sin AT, los gráficos sin AT sin garras y los cografos .
La compleción mínima de cuerdas fue uno de los doce problemas computacionales cuya complejidad se incluyó como abierta en el libro Computers and Intractability de 1979. Las aplicaciones de la compleción de cuerdas incluyen el modelado del problema de minimizar el relleno al realizar la eliminación gaussiana en matrices simétricas dispersas y la reconstrucción de árboles filogenéticos .
Las terminaciones cordales de un gráfico a veces se denominan triangulaciones, [1] pero este término es ambiguo incluso en el contexto de la teoría de gráficos, ya que también puede referirse a gráficos planos máximos .
Un grafo G es un grafo libre de AT si y solo si todas sus terminaciones de cuerdas mínimas son grafos de intervalo . G es un grafo libre de AT sin garras si y solo si todas sus terminaciones de cuerdas mínimas son grafos de intervalo propios. Y G es un cografo si y solo si todas sus terminaciones de cuerdas mínimas son grafos trivialmente perfectos . [1]
Un grafo G tiene un ancho de árbol como máximo k si y solo si G tiene al menos una completitud cordal cuyo tamaño máximo de clique es como máximo k + 1 . Tiene un ancho de camino como máximo k si y solo si G tiene al menos una completitud cordal que es un grafo de intervalo con un tamaño máximo de clique como máximo k + 1 . Tiene un ancho de banda como máximo k si y solo si G tiene al menos una completitud cordal que es un grafo de intervalo propio con un tamaño máximo de clique como máximo k + 1 . [2] Y tiene una profundidad de árbol k si y solo si tiene al menos una completitud cordal que es un grafo trivialmente perfecto con un tamaño máximo de clique como máximo k . [3]
La aplicación original de la compleción de cuerdas descrita en Computadoras e intratabilidad implica la eliminación gaussiana para matrices dispersas . Durante el proceso de eliminación gaussiana, se desea minimizar el relleno, los coeficientes de la matriz que inicialmente eran cero pero luego se vuelven distintos de cero, porque la necesidad de calcular los valores de estos coeficientes ralentiza el algoritmo. El patrón de los no ceros en una matriz simétrica dispersa se puede describir mediante un grafo no dirigido (que tiene la matriz como su matriz de adyacencia ); el patrón de los no ceros en la matriz rellena es siempre un grafo de cuerdas, cualquier compleción de cuerdas mínima corresponde a un patrón de relleno de esta manera. Si se da una compleción de cuerdas de un grafo, se puede encontrar una secuencia de pasos en los que realizar la eliminación gaussiana para lograr este patrón de relleno calculando un orden de eliminación del grafo de cuerdas resultante. De esta manera, el problema de relleno mínimo puede verse como equivalente al problema de compleción de cuerdas mínimas. [4] En esta aplicación, los gráficos planares pueden surgir en la solución de sistemas de elementos finitos bidimensionales; del teorema del separador planar se deduce que cada gráfico planar con n vértices tiene una completitud cordal con como máximo O ( n log n ) aristas. [5]
Otra aplicación proviene de la filogenia , el problema de reconstruir árboles evolutivos, por ejemplo árboles de organismos sujetos a mutaciones genéticas o árboles de conjuntos de manuscritos antiguos copiados uno de otro sujetos a errores de copistas. Si se supone que cada mutación genética o error de copista ocurre solo una vez, se obtiene una filogenia perfecta , un árbol en el que las especies o manuscritos que tienen alguna característica particular siempre forman un subárbol conectado. Como describe Buneman (1974), la existencia de una filogenia perfecta puede modelarse como un problema de completitud de cuerdas. Se dibuja un "gráfico de superposición" G en el que los vértices son valores de atributos (elecciones específicas para alguna característica de una especie o manuscrito) y los bordes representan pares de valores de atributos que son compartidos por al menos una especie. Los vértices del gráfico pueden colorearse con las identidades de las características de las que proviene cada valor de atributo, de modo que el número total de colores sea igual al número de características utilizadas para derivar la filogenia. Entonces existe una filogenia perfecta si y sólo si G tiene una completitud cordal que respeta la coloración. [6]
Aunque aparece como un problema abierto en el libro Computers and Intractability de 1979 , [7] la complejidad computacional del problema de completitud cordal mínima (también llamado problema de relleno mínimo ) se resolvió rápidamente: Yannakakis (1981) demostró que es NP-completo . [8] Si la completitud cordal mínima agrega k aristas a un grafo G , entonces es posible encontrar una completitud cordal usando como máximo 8 k 2 aristas agregadas, en tiempo polinomial. [9] El problema de encontrar el conjunto óptimo de k aristas para agregar también se puede resolver mediante un algoritmo manejable de parámetros fijos , en tiempo polinomial en el tamaño del grafo y subexponencial en k . [10]
El ancho del árbol (tamaño mínimo de camarilla de una completitud cordal) y los parámetros relacionados, incluyendo el ancho del camino y la profundidad del árbol, también son NP-completos para calcular y (a menos que P=NP) no pueden aproximarse en tiempo polinomial dentro de un factor constante de sus valores óptimos; sin embargo, se conocen algoritmos de aproximación con razones de aproximación logarítmicas para ellos. [11]
Tanto los problemas de relleno mínimo como los de ancho de árbol se pueden resolver en tiempo exponencial . Más precisamente, para un gráfico de n vértices, el tiempo es O (1,9601 n ) . [12]