En la teoría de grafos , la coloración completa es lo opuesto a la coloración armoniosa en el sentido de que es una coloración de vértice en la que cada par de colores aparece en al menos un par de vértices adyacentes. De manera equivalente, una coloración completa es mínima en el sentido de que no se puede transformar en una coloración adecuada con menos colores fusionando pares de clases de colores. El número acromático ψ (G) de un gráfico G es el número máximo de colores posible en cualquier coloración completa de G.
Teoría de la complejidad [ editar ]
Encontrar ψ (G) es un problema de optimización . El problema de decisión para la coloración completa se puede expresar como:
- INSTANCIA: un gráfico y entero positivo
- PREGUNTA: ¿existe una partición de dentro o más conjuntos disjuntos tal que cada es un conjunto independiente para y tal que para cada par de conjuntos distintos No es un conjunto independiente.
Determinar el número acromático es NP-duro ; determinar si es mayor que un número dado es NP-completo , como lo muestran Yannakakis y Gavril en 1978 mediante la transformación del problema de coincidencia máxima mínima. [1]
Tenga en cuenta que cualquier color de un gráfico con el número mínimo de colores debe ser un color completo, por lo que minimizar el número de colores en un color completo es solo una reafirmación del problema de color estándar del gráfico .
Algoritmos [ editar ]
Para cualquier k fijo , es posible determinar si el número acromático de un gráfico dado es al menos k , en tiempo lineal. [2]
El problema de optimización permite la aproximación y es aproximable dentro de un relación de aproximación . [3]
Clases especiales de gráficos [ editar ]
La completitud NP del problema del número acromático también se aplica a algunas clases especiales de gráficos: gráficos bipartitos , [2] complementos de gráficos bipartitos (es decir, gráficos que no tienen un conjunto independiente de más de dos vértices), [1] gráficos e intervalos gráficos , [4] e incluso para árboles. [5]
Para complementos de árboles, el número acromático se puede calcular en tiempo polinómico. [6] Para los árboles, puede aproximarse a un factor constante. [3]
Se sabe que el número acromático de un gráfico hipercubo n- dimensional es proporcional a, pero la constante de proporcionalidad no se conoce con precisión.
En teoría de grafos , una partición domática de un grafo es una partición de en conjuntos disjuntos , , ...,de tal manera que cada V i es un conjunto dominante para G . La figura de la derecha muestra una partición domática de un gráfico; aquí el conjunto dominante consiste en los vértices amarillos, consiste en los vértices verdes, y consiste en los vértices azules.
El número domático es el tamaño máximo de una partición domática, es decir, el número máximo de conjuntos dominantes disjuntos. El gráfico en la figura tiene el número domatic 3. Es fácil ver que el número domatic es al menos 3 porque hemos presentado una partición domatic de tamaño 3. Para ver que el número domatic es como máximo 3, primero revisamos un simple límite superior.
Límites superiores [ editar ]
Dejar ser el grado mínimo de la gráfica. El número domático de es a lo sumo . Para ver esto, considere un vértice de grado . Dejar consiste en y sus vecinos Sabemos que (1) cada conjunto dominante debe contener al menos un vértice en (dominación) y (2) cada vértice en está contenido como máximo en un conjunto dominante (disyunción). Por lo tanto hay como mucho conjuntos dominantes disjuntos.
El gráfico en la figura tiene grado mínimo y, por lo tanto, su número domático es como máximo 3. Por lo tanto, hemos demostrado que su número domático es exactamente 3; la figura muestra una partición domática de tamaño máximo.
Límites inferiores [ editar ]
Si no hay vértice aislado en el gráfico (es decir, ≥ 1), entonces el número domático es al menos 2. Para ver esto, tenga en cuenta que (1) un color débil 2 es una partición domática si no hay vértice aislado, y (2) cualquier gráfico tiene un color débil 2 . Alternativamente, (1) un conjunto independiente máximo es un conjunto dominante, y (2) el complemento de un conjunto independiente máximo también es un conjunto dominante si no hay vértices aislados.
La figura de la derecha muestra una débil coloración 2, que también es una partición domática de tamaño 2: los nodos oscuros son un conjunto dominante, y los nodos claros son otro conjunto dominante (los nodos claros forman un conjunto independiente máximo). Ver coloración débil para más información.
Complejidad computacional [ editar ]
Encontrar una partición domática de tamaño 1 es trivial: let . Encontrar una partición domática de tamaño 2 (o determinar que no existe) es fácil: verifique si hay nodos aislados y, si no, encuentre un color débil 2.
Sin embargo, encontrar una partición domática de tamaño máximo es computacionalmente difícil. Específicamente, el siguiente problema de decisión , conocido como el problema del número domático , es NP completo : dado un gráfico y un entero , determinar si el número domatic de Por lo menos . Por lo tanto, el problema de determinar el número domático de un gráfico dado es NP-hard , y el problema de encontrar una partición domática de tamaño máximo también es NP-hard.
Existe un algoritmo de aproximación de tiempo polinómico con una garantía de aproximación logarítmica, [1] es decir, es posible encontrar una partición domática cuyo tamaño esté dentro de un factor de lo óptimo.
Sin embargo, bajo supuestos teóricos de complejidad plausibles, no existe un algoritmo de aproximación de tiempo polinomial con un factor de aproximación sublogarítmico. [1] Más específicamente, un algoritmo de aproximación de tiempo polinómico para la partición domática con el factor de aproximación por una constante implicaría que todos los problemas en NP pueden resolverse en un tiempo ligeramente superpolinómico.
Comparación con conceptos similares [ editar ]
- Tabique domatico
- Partición de vértices en conjuntos dominantes disjuntos. El número domático es el número máximo de tales conjuntos.
- Coloración de vértice
- Partición de vértices en conjuntos independientes disjuntos . El número cromático es el número mínimo de tales conjuntos.
- Partición de camarilla
- Partición de vértices en camarillas disjuntas . Igual a la coloración del vértice en el gráfico del complemento .
- Coloración del borde
- Partición de bordes en emparejamientos disjuntos . El número cromático de borde es el número mínimo de tales conjuntos.
Sea G = ( U ∪ V , E ) un gráfico bipartito sin nodos aislados; todos los bordes son de la forma { u , v } ∈ E con u ∈ U y V ∈ V . Entonces { U , V } es a la vez un vértice de 2 colores y una partición domática de tamaño 2; los conjuntos U y V son conjuntos dominantes independientes. El número cromático de G es exactamente 2; no hay vértice 1 para colorear. El número domático de Ges al menos 2. Es posible que haya una partición domática más grande; por ejemplo, el gráfico bipartito completo K n , n para cualquier n ≥ 2 tiene un número domático n .
En la teoría de grafos , un conjunto dominante para un gráfico G = ( V , E ) es un subconjunto D de V de tal manera que cada vértice no en D es adyacente a al menos un miembro de D . El número dominación γ ( G ) es el número de vértices en un conjunto dominante más pequeño para G .
El problema del conjunto dominante se refiere a probar si γ ( G ) ≤ K para un gráfico dado G y la entrada K ; Es un problema clásico de decisión de NP completo en la teoría de la complejidad computacional . [1] Por lo tanto, se cree que puede no haber un algoritmo eficiente que encuentre un conjunto dominante más pequeño para todos los gráficos, aunque existen algoritmos de aproximación eficientes, así como algoritmos eficientes y exactos para ciertas clases de gráficos.
Las figuras (a) - (c) a la derecha muestran tres ejemplos de conjuntos dominantes para un gráfico. En cada ejemplo, cada vértice blanco es adyacente a al menos un vértice rojo, y se dice que el vértice blanco está dominado por el vértice rojo. El número de dominación de este gráfico es 2: los ejemplos (b) y (c) muestran que hay un conjunto dominante con 2 vértices, y se puede comprobar que no hay un conjunto dominante con solo 1 vértice para este gráfico.
Historia [ editar ]
El problema de dominación se estudió desde la década de 1950 en adelante, pero la tasa de investigación sobre dominación aumentó significativamente a mediados de la década de 1970. En 1972, Richard Karp demostró que el problema de la cobertura del conjunto era NP completo . Esto tuvo implicaciones inmediatas para el problema dominante del conjunto, ya que hay vértices directos para establecer y bordear las biyecciones de intersección no disjunta entre los dos problemas. Esto demostró que el problema del conjunto dominante era NP-completo también. [2]
Los conjuntos dominantes son de interés práctico en varias áreas. En las redes inalámbricas , los conjuntos dominantes se utilizan para encontrar rutas eficientes dentro de redes móviles ad-hoc. También se han utilizado en el resumen de documentos y en el diseño de sistemas seguros para redes eléctricas.
Dominación independiente [ editar ]
Los conjuntos dominantes están estrechamente relacionados con los conjuntos independientes : un conjunto independiente también es un conjunto dominante si y solo si es un conjunto independiente máximo , por lo que cualquier conjunto independiente máximo en un gráfico es necesariamente también un conjunto dominante mínimo. Por lo tanto, el conjunto independiente máximo más pequeño es mayor o igual en tamaño que el conjunto dominante independiente más pequeño. El número de dominación independiente i ( G ) de un gráfico G es el tamaño del conjunto dominante independiente más pequeño (o, de manera equivalente, el tamaño del conjunto independiente máximo más pequeño).
El conjunto dominante mínimo en un gráfico no será necesariamente independiente, pero el tamaño de un conjunto dominante mínimo siempre es menor o igual al tamaño de un conjunto independiente máximo mínimo, es decir, γ ( G ) ≤ i ( G ).
Hay familias de gráficos en las que un conjunto independiente mínimo máximo es un conjunto dominante mínimo. Por ejemplo, γ ( G ) = i ( G ) si G es un gráfico sin garras . [3]
Un gráfico de G se denomina gráfico de dominación-perfecto si γ ( H ) = i ( H ) en cada inducida subgrafo H de G . Como un subgrafo inducido de un gráfico sin garras no tiene garras, se deduce que cada gráfico sin garras también es perfecto para dominar. [4]
Ejemplos [ editar ]
Las figuras (a) y (b) son conjuntos dominantes independientes, mientras que la figura (c) ilustra un conjunto dominante que no es un conjunto independiente.
Para cualquier gráfico G , su gráfico lineal L ( G ) no tiene garras y, por lo tanto, un conjunto independiente mínimo máximo en L ( G ) también es un conjunto dominante mínimo en L ( G ). Un conjunto independiente en L ( G corresponde) a un juego en G , y un conjunto dominante en L ( G corresponde) a un conjunto de aristas que domina en G . Por lo tanto, una coincidencia máxima mínima tiene el mismo tamaño que un conjunto dominante de borde mínimo.
El siguiente ejemplo ilustra que la desigualdad estricta puede ser válida para γ ( G ) ≤ i ( G ). Sea G el gráfico de doble estrella que consta de vértices x_1 , ..., x_p , a , b , y_1 , ..., y_q , donde p , q > 1. Los bordes de G se definen de la siguiente manera: cada x_i es adyacente a una , una es adyacente a b , y b es adyacente a cada b_j . Entonces γ ( G) = 2 ya que { a , b } es un conjunto mínimo de dominación de vértices. Si p ≤ q , entonces i ( G ) = p + 1 ya que { x_1 , ..., x_p , b} es el conjunto independiente máximo más pequeño.
Algoritmos y complejidad computacional [ editar ]
El problema de la cobertura del conjunto es un problema NP-hard bien conocido : la versión de decisión de la cobertura del conjunto fue uno de los 21 problemas completos de NP de Karp . Existen un par de reducciones de L en tiempo polinomial entre el problema de conjunto dominante mínimo y el problema de cobertura de conjunto . [5] Estas reducciones ( ver más abajo ) muestran que un algoritmo eficiente para el problema de conjunto dominante mínimo proporcionaría un algoritmo eficiente para el problema de cobertura de conjunto, y viceversa. Además, las reducciones conservan la relación de aproximación: para cualquier α, un algoritmo de aproximación α de tiempo polinomial para conjuntos dominantes mínimos proporcionaría un algoritmo de aproximación α de tiempo polinomial para el problema de cobertura de conjunto y viceversa. De hecho, ambos problemas son Log-APX-complete . [6]
La aproximabilidad de la cobertura del conjunto también se entiende bien: se puede encontrar un factor de aproximación logarítmico utilizando un algoritmo codicioso simple , y encontrar un factor de aproximación sublogarítmico es NP-duro. Más específicamente, el algoritmo codicioso proporciona un factor 1 + log | V | aproximación de un conjunto dominante mínimo, y ningún algoritmo de tiempo polinómico puede lograr un factor de aproximación mejor que c log | V | para algunos c > 0 a menos que P = NP . [7]
Reducciones en L [ editar ]
Las dos reducciones siguientes muestran que el problema del conjunto dominante mínimo y el problema de la cobertura del conjunto son equivalentes en las reducciones L : dada una instancia de un problema, podemos construir una instancia equivalente del otro problema. [5]
De conjunto dominante a conjunto de cobertura. Dado un gráfico G = ( V , E ) con V = {1, 2, ..., n }, construya una instancia de cobertura de conjunto ( U , S ) de la siguiente manera: el universo U es V y la familia de subconjuntos es S = { S 1 , S 2 , ..., S n } tal que S v consiste en el vértice v y todos los vértices adyacentes a v en G .
Ahora, si D es un conjunto dominante para G , entonces C = { S v : v ∈ D } es una solución factible del problema de cobertura del conjunto, con | C | = | D |. Por el contrario, si C = { S v : v ∈ D } es una solución factible del problema de cobertura del conjunto, entonces D es un conjunto dominante para G , con | D | = | C |.
Por lo tanto, el tamaño de un conjunto dominante mínimo para G es igual al tamaño de una cubierta de conjunto mínimo para ( U , S ). Además, existe un algoritmo simple que asigna un conjunto dominante a una cubierta de conjunto del mismo tamaño y viceversa. En particular, un algoritmo eficiente de aproximación α para la cobertura de conjuntos proporciona un algoritmo eficiente de aproximación α para conjuntos dominantes mínimos.
-
- Por ejemplo, dada la gráfica G que se muestra a la derecha, construimos una instancia de cobertura con el universo U = {1, 2, ..., 6} y los subconjuntos S 1 = {1, 2, 5}, S 2 = {1, 2, 3, 5}, S 3 = {2, 3, 4, 6}, S 4 = {3, 4}, S 5 = {1, 2, 5, 6} y S 6 = {3, 5, 6}. En este ejemplo, D = {3, 5} es un conjunto dominante para G - esto corresponde a la cubierta del conjunto C = { S 3 , S 5 }. Por ejemplo, el vértice 4 ∈ Vestá dominado por el vértice 3 ∈ D , y el elemento 4 ∈ U está contenido en el conjunto S 3 ∈ C .
De conjunto que cubre a conjunto dominante. Sea ( S , U ) una instancia del problema de cobertura del conjunto con el universo U y la familia de subconjuntos S = { S i : i ∈ I }; suponemos que U y el conjunto de índices I son disjuntos. Construya un gráfico G = ( V , E ) de la siguiente manera: el conjunto de vértices es V = I ∪ U , hay un borde { i , j } ∈ E entre cada par i , j ∈ I , y también hay una ventaja { i , u } para cada i ∈ I y u ∈ S i . Es decir, G es un gráfico dividido : I es una camarilla y U es un conjunto independiente .
Ahora bien, si C = { S i : i ∈ D } es una solución factible del problema de cobertura del conjunto para algún subconjunto D ⊆ I , entonces D es un conjunto dominante para G , con | D | = | C |: Primero, para cada u ∈ U hay una i ∈ D tal que u ∈ S i , y por construcción, u e i son adyacentes en G ; por lo tanto, estás dominado por i. En segundo lugar, puesto que D debe ser no vacío, cada i ∈ I es adyacente a un vértice en D .
Por el contrario, dejar que D sea un conjunto dominante de G . Entonces es posible construir otro conjunto dominante X tal que | X | ≤ | D | y X ⊆ I : simplemente reemplace cada u ∈ D ∩ U por un vecino i ∈ I de u . Entonces C = { S i : i ∈ X } es una solución factible del problema de cobertura del conjunto, con | C | = | X | ≤ | D |.
-
- La ilustración de la derecha muestra la construcción para U = { a , b , c , d , e }, I = {1, 2, 3, 4}, S 1 = { a , b , c }, S 2 = { a , b }, S 3 = { b , c , d } y S 4 = { c , d , e }.
-
- En este ejemplo, C = { S 1 , S 4 } es una cubierta de conjunto; esto corresponde al conjunto dominante D = {1, 4}.
-
- D = { a , 3, 4} es otro conjunto dominante para el gráfico G . Dada D , podemos construir un conjunto dominante X = {1, 3, 4} que no es mayor que D y que es un subconjunto de I . El conjunto dominante X corresponde a la cubierta del conjunto C = { S 1 , S 3 , S 4 }.
Casos especiales [ editar ]
Si el gráfico tiene un grado máximo Δ, entonces el algoritmo de aproximación codicioso encuentra una aproximación O (log Δ) de un conjunto dominante mínimo. Además, supongamos que d g es la cardinalidad del conjunto dominante obtenido usando una aproximación codiciosa y luego siguiendo las relaciones de retención,, donde N es el número de nodos y M es el número de aristas en un gráfico no dirigido dado. [8] Para Δ fijo, esto califica como un conjunto dominante para la membresía APX ; de hecho, es APX-complete. [9]
El problema admite un esquema de aproximación de tiempo polinomial (PTAS) para casos especiales como gráficos de unidades de disco y gráficos planos . [10] Se puede encontrar un conjunto dominante mínimo en el tiempo lineal en gráficos en serie-paralelo . [11]
Algoritmos exactos [ editar ]
Se puede encontrar un conjunto mínimo dominante de un gráfico n- vértice en el tiempo O (2 n n ) inspeccionando todos los subconjuntos de vértices. Fomin, Grandoni y Kratsch (2009) muestran cómo encontrar un conjunto dominante mínimo en el tiempo O (1.5137 n ) y el espacio exponencial, y en el tiempo O (1.5264 n ) y el espacio polinomial. Van Rooij, Nederlof y van Dijk (2009) encontraron un algoritmo más rápido, utilizando el tiempo O (1.5048 n ) , que también muestra que el número de conjuntos dominantes mínimos se puede calcular en este tiempo. El número de conjuntos dominantes mínimos es como máximo 1.7159 ny todos estos conjuntos se pueden enumerar en el tiempo O (1.7159 n ). [12]
Complejidad parametrizada [ editar ]
Encontrar un conjunto dominante de tamaño k juega un papel central en la teoría de la complejidad parametrizada. Es el problema más conocido completo para la clase W [2] y se utiliza en muchas reducciones para mostrar la intratabilidad de otros problemas. En particular, el problema no es un parámetro fijo manejable en el sentido de que no existe un algoritmo con tiempo de ejecución f ( k ) n O (1) para ninguna función f a menos que la jerarquía W colapse a FPT = W [2].
Por otro lado, si el gráfico de entrada es plano, el problema sigue siendo NP-duro, pero se conoce un algoritmo de parámetro fijo. De hecho, el problema tiene un núcleo de tamaño lineal en k , [13] y los tiempos de ejecución que son exponenciales en √ k y cúbicos en n pueden obtenerse aplicando programación dinámica a una descomposición de ramificación del núcleo. [14] Más generalmente, el problema del conjunto dominante y muchas variantes del problema son manejables con parámetros fijos cuando se parametrizan tanto por el tamaño del conjunto dominante como por el tamaño del subgrafo bipartito completo prohibido más pequeño ; es decir, el problema es FPT engráficos libres de bicliques , una clase muy general de gráficos dispersos que incluye los gráficos planos. [15]
El conjunto complementario a un conjunto dominante, un no bloqueador , se puede encontrar mediante un algoritmo de parámetro fijo en cualquier gráfico. [dieciséis]
Variantes [ editar ]
La conjetura de Vizing relaciona el número de dominación de un producto cartesiano de gráficos con el número de dominación de sus factores.
Se ha trabajado mucho en conjuntos dominantes conectados . Si S es un conjunto dominante conectado, se puede formar un árbol de expansión de G en el que S forma el conjunto de vértices que no son hojas del árbol; por el contrario, si T es cualquier árbol de expansión en un gráfico con más de dos vértices, los vértices no T de la hoja forman un conjunto dominante conectado. Por lo tanto, encontrar conjuntos dominantes conectados mínimos es equivalente a encontrar árboles de expansión con el máximo número posible de hojas.
Un conjunto dominante total es un conjunto de vértices de tal manera que todos los vértices en el gráfico (incluidos los vértices en el conjunto dominante) tienen un vecino en el conjunto dominante. La Figura (c) anterior muestra un conjunto dominante que es un conjunto dominante conectado y un conjunto dominante total; los ejemplos en las figuras (a) y (b) no son ninguno.
Un conjunto dominante de k-tuplas es un conjunto de vértices de tal manera que cada vértice en el gráfico tiene al menos k vecinos en el conjunto. Se puede encontrar una aproximación (1 + log n) de un conjunto dominante mínimo de tuplas k en el tiempo polinómico. [17] Del mismo modo, un conjunto que domina k es un conjunto de vértices de tal manera que cada vértice que no está en el conjunto tiene al menos k vecinos en el conjunto. Si bien cada gráfico admite un conjunto dominante de k , solo los gráficos con un grado mínimo k - 1 admiten un conjunto dominante de tuplas k . Sin embargo, incluso si el gráfico admite un conjunto dominante de k-tuplas, un conjunto dominante mínimo de k -tuplas puede ser casi kveces tan grande como un conjunto mínimo de k dominantes para el mismo gráfico; [18] También se puede encontrar una aproximación (1.7 + log Δ) de un conjunto mínimo que domina k en el tiempo polinómico.
Una partición domática es una partición de los vértices en conjuntos dominantes disjuntos. El número domático es el tamaño máximo de una partición domática.
Un conjunto dominante eterno es una versión dinámica de dominación en la que se elige un vértice v en el conjunto dominante D y se reemplaza con un vecino u ( u no está en D ) de modo que la D modificada también sea un conjunto dominante y este proceso puede repetirse sobre cualquier secuencia infinita de elecciones de vértices v .
No hay comentarios:
Publicar un comentario