Conjunto dominante conectado

En la teoría de grafos , un conjunto dominante conexo y un árbol de expansión de hojas máximo son dos estructuras estrechamente relacionadas definidas en un grafo no dirigido .

Un conjunto dominante conexo de un grafo G es un conjunto D de vértices con dos propiedades:

1. Cualquier vértice en D puede alcanzar cualquier otro vértice en D mediante un camino que permanece completamente dentro de D. Es decir, D induce un subgrafo conexo de G.
2. Cada vértice en G pertenece a D o es adyacente a un vértice en D. Es decir, D es un conjunto dominante de G.

Un conjunto dominante conexo mínimo de un grafo G es un conjunto dominante conexo con la menor cardinalidad posible entre todos los conjuntos dominantes conexos de G. El número de dominación conexa de G es el número de vértices en el conjunto dominante conexo mínimo. ^{[ 1 ]}

Todo árbol de expansión T de un grafo G tiene al menos dos hojas, vértices que tienen solo una arista de T incidente. Un árbol de expansión con el máximo número de hojas es aquel que posee el mayor número posible de hojas entre todos los árboles de expansión de G. El número máximo de hojas de G es el número de hojas en el árbol de expansión con el máximo número de hojas. ^{[ 2 ]}

Si d es el número de dominación conexa de un grafo G de n vértices , donde n > 2 , y l es su número máximo de hojas, entonces las tres cantidades d , l y n obedecen la ecuación simple

${\displaystyle \displaystyle n=d+l.}$^{[ 3 ]}

Si D es un conjunto dominante conexo, entonces existe un árbol de expansión en G cuyas hojas incluyen todos los vértices que no están en D : forman un árbol de expansión del subgrafo inducido por D , junto con aristas que conectan cada vértice restante v que no está en D con un vecino de v en D. Esto muestra que l ≥ n − d .

En la otra dirección, si T es cualquier árbol generador en G , entonces los vértices de T que no son hojas forman un conjunto dominante conexo de G. Esto muestra que n − l ≥ d . Al juntar estas dos desigualdades se demuestra la igualdad n = d + l .

Por lo tanto, en cualquier grafo, la suma del número de dominancia conexa y el número máximo de hojas es igual al número total de vértices. Computacionalmente, esto implica que determinar el número de dominancia conexa es igual de difícil que encontrar el número máximo de hojas.

Es un problema NP-completo comprobar si existe un conjunto dominante conexo de tamaño inferior a un umbral dado, o, equivalentemente, comprobar si existe un árbol de expansión con al menos un número determinado de hojas. Por lo tanto, se cree que el problema del conjunto dominante conexo mínimo y el problema del árbol de expansión con el máximo número de hojas no pueden resolverse en tiempo polinomial.

En términos de algoritmos de aproximación, la dominación conectada y los árboles de máxima expansión de hojas no son lo mismo: aproximar uno dentro de una razón de aproximación dada no es lo mismo que aproximar el otro a la misma razón. Existe una aproximación para el conjunto dominante conectado mínimo que alcanza un factor de 2 ln Δ + O(1) , donde Δ es el grado máximo de un vértice en G. ^{[ 4 ]} El problema del árbol de máxima expansión de hojas es MAX-SNP difícil, lo que implica que no es probable ningún esquema de aproximación en tiempo polinomial . ^{[ 5 ]} Sin embargo, se puede aproximar dentro de un factor de 2 en tiempo polinomial. ^{[ 6 ]}

Ambos problemas pueden resolverse, en grafos de n vértices, en tiempo O (1,9n ⁾ . [ ^{7 ] El} problema de la hoja máxima es tratable con parámetros fijos , lo que significa que puede resolverse en tiempo exponencial en el número de hojas, pero solo polinomial en el tamaño del grafo de entrada. El valor klam de estos algoritmos (intuitivamente, un número de hojas hasta el cual el problema puede resolverse en un tiempo razonable) ha aumentado gradualmente, a medida que los algoritmos para el problema han mejorado, hasta aproximadamente 37, ^{[ 8 ]} y se ha sugerido que al menos 50 debería ser alcanzable. ^{[ 9 ]}

En grafos de grado máximo tres, el conjunto dominante conexo y su problema complementario del árbol de expansión de hojas máximo se pueden resolver en tiempo polinomial , transformándolos en una instancia del problema de paridad de matroides para matroides lineales . ^{[ 10 ]}

Los conjuntos dominantes conectados son útiles en el cálculo de enrutamiento para redes móviles ad hoc . En esta aplicación, se utiliza un pequeño conjunto dominante conectado como columna vertebral para las comunicaciones, y los nodos que no están en este conjunto se comunican pasando mensajes a través de los vecinos que sí están en el conjunto. ^{[ 11 ]}

El número máximo de hojas se ha empleado en el desarrollo de algoritmos tratables de parámetros fijos : varios problemas de optimización NP-difíciles pueden resolverse en tiempo polinomial para grafos con un número máximo de hojas acotado. ^{[ 2 ]}

• Vértice universal , un vértice que (cuando existe) proporciona un conjunto dominante conexo mínimo de tamaño uno.