En teoría de grafos , un conjunto dominante conexo y un árbol de expansión de hojas máximas 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:
Un conjunto dominante conexo mínimo de un grafo G es un conjunto dominante conexo con la cardinalidad más pequeña posible entre todos los conjuntos dominantes conexos de G. El número de dominación conexo de G es el número de vértices en el conjunto dominante conexo mínimo. [1]
Cualquier árbol de expansión T de un grafo G tiene al menos dos hojas, vértices que tienen solo una arista de T incidente a ellos. Un árbol de expansión de hojas máximas es un árbol de expansión que tiene 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 de hojas máximas. [2]
Si d es el número de dominación conexo de un grafo de n vértices G , donde n > 2 , y l es su número máximo de hojas, entonces las tres cantidades d , l y n obedecen a la simple ecuación
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 a un vecino de v en D . Esto muestra que l ≥ n − d .
En la otra dirección, si T es cualquier árbol de expansión en G , entonces los vértices de T que no son hojas forman un conjunto dominante conexo de G . Esto demuestra que n − l ≥ d . Juntando estas dos desigualdades se demuestra la igualdad n = d + l .
Por lo tanto, en cualquier grafo, la suma del número de dominación conexa y el número máximo de hojas es igual al número total de vértices. Desde el punto de vista computacional, esto implica que determinar el número de dominación conexa es tan difícil como encontrar el número máximo de hojas.
Es NP-completo comprobar si existe un conjunto dominante conexo con un tamaño inferior a un umbral dado, o equivalentemente comprobar si existe un árbol de expansión con al menos un número dado 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 número máximo de hojas no se pueden resolver en tiempo polinomial.
Cuando se los considera en términos de algoritmos de aproximación, los árboles de dominación conectados y 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 logra 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 difícil de MAX-SNP , lo que implica que no es probable que exista un 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,9 n ) . [7] El problema de la hoja máxima es manejable 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 dentro de una cantidad de tiempo razonable) ha aumentado gradualmente, a medida que los algoritmos para el problema han mejorado, a aproximadamente 37, [8] y se ha sugerido que al menos 50 deberían ser alcanzables. [9]
En gráficos de máximo grado tres, el conjunto dominante conexo y su problema complementario de árbol de expansión de hojas máximas 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 ad hoc móviles . 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 vecinos que sí están en el conjunto. [11]
El número máximo de hojas se ha empleado en el desarrollo de algoritmos manejables con parámetros fijos : varios problemas de optimización NP-hard se pueden resolver en tiempo polinomial para gráficos de número máximo de hojas acotado. [2]
