Conjunto de borde dominante

En teoría de grafos , un conjunto dominante de aristas para un grafo G  = ( V ,  E ) es un subconjunto D  ⊆  E tal que cada arista que no está en D es adyacente a al menos una arista en D . Un conjunto dominante de aristas también se conoce como conjunto dominante de líneas . Las figuras (a)–(d) son ejemplos de conjuntos dominantes de aristas (líneas rojas gruesas).

Un conjunto mínimo dominante de aristas es el conjunto más pequeño dominante de aristas. Las figuras (a) y (b) son ejemplos de conjuntos mínimos dominantes de aristas (se puede comprobar que no existe ningún conjunto dominante de aristas de tamaño 2 para este gráfico).

Un conjunto dominante de aristas para G es un conjunto dominante para su gráfico de líneas L ( G ) y viceversa.

Cualquier coincidencia máxima es siempre un conjunto con aristas dominantes. Las figuras (b) y (d) son ejemplos de coincidencias máximas.

Además, el tamaño de un conjunto mínimo dominante de aristas es igual al tamaño de una coincidencia máxima mínima . Una coincidencia máxima mínima es un conjunto mínimo dominante de aristas; la Figura (b) es un ejemplo de una coincidencia máxima mínima. Un conjunto mínimo dominante de aristas no es necesariamente una coincidencia máxima mínima, como se ilustra en la Figura (a); sin embargo, dado un conjunto mínimo dominante de aristas D , es fácil encontrar una coincidencia máxima mínima con | D | aristas (véase, por ejemplo, Yannakakis y Gavril 1980).

Determinar si existe un conjunto dominante de aristas de un tamaño dado para un grafo dado es un problema NP-completo (y, por lo tanto, encontrar un conjunto dominante de aristas mínimo es un problema NP-difícil ). Yannakakis y Gavril (1980) muestran que el problema es NP-completo incluso en el caso de un grafo bipartito con un grado máximo de 3, y también en el caso de un grafo planar con un grado máximo de 3.

Existe un algoritmo de aproximación de tiempo polinómico simple con un factor de aproximación 2: encontrar cualquier coincidencia máxima. Una coincidencia máxima es un conjunto que domina las aristas; además, una coincidencia máxima M puede ser, en el peor de los casos, 2 veces más grande que una coincidencia máxima más pequeña, y una coincidencia máxima más pequeña tiene el mismo tamaño que el conjunto que domina las aristas más pequeño.

La versión ponderada por los bordes del problema también se puede aproximar dentro del factor 2, pero el algoritmo es considerablemente más complicado (Fujito y Nagamochi 2002; Parekh 2002).

Chlebík y Chlebíková (2006) demuestran que encontrar una aproximación mejor que (7/6) es NP-difícil. Schmied y Viehmann demostraron que el problema es UGC-difícil de aproximar dentro de cualquier constante mejor que 3/2.

• Ausiello, Giorgio; Crescenzi, Pierluigi; Gambosi, Giorgio; Kann, Viggo; Marchetti-Spaccamela, Alberto; Protasi, Marco (2003), Complejidad y aproximación: problemas de optimización combinatoria y sus propiedades de aproximabilidad , Springer.

El conjunto de aristas mínimas dominantes (versión de optimización) es el problema GT3 en el Apéndice B (página 370).

El emparejamiento mínimo-máximo (versión de optimización) es el problema GT10 en el Apéndice B (página 374).

• Chlebík, Miroslav; Chlebíková, Janka (2006), "Dureza de aproximación de problemas de conjuntos dominantes de aristas", Journal of Combinatorial Optimization , 11 (3): 279–290, doi :10.1007/s10878-006-7908-0, S2CID  8024435.
• Garey, Michael R.; Johnson , David S. (1979), Computadoras e intratabilidad: una guía para la teoría de la NP-completitud , WH Freeman, ISBN 978-0-7167-1045-5.

El conjunto dominante de aristas (versión de decisión) se analiza en el problema del conjunto dominante, que es el problema GT2 en el Apéndice A1.1.

El emparejamiento mínimo máximo (versión de decisión) es el problema GT10 en el Apéndice A1.1.

• Yannakakis, Mihalis ; Gavril, Fanica (1980), "Conjuntos con aristas dominantes en grafos", SIAM Journal on Applied Mathematics , 38 (3): 364–372, CiteSeerX  10.1.1.477.4278 , doi :10.1137/0138030, JSTOR  2100648.
• Fujito, Toshihiro; Nagamochi, Hiroshi (2002), "Un algoritmo de 2 aproximaciones para el problema de conjunto dominante de aristas de peso mínimo", Discrete Applied Mathematics , 118 (3): 199–207, doi :10.1016/S0166-218X(00)00383-8.
• Parekh, Ojas (2002), "Conjuntos de aristas dominantes e hipoemparejables", Actas del decimotercer simposio anual ACM-SIAM sobre algoritmos discretos , págs. 287-291.
• Richard Schmied y Claus Viehmann (2012), "Aproximación del conjunto dominante de aristas en grafos densos", Theor. Comput. Sci. 414(1), págs. 92-99.

• Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski, Gerhard Woeginger (2000), "Un compendio de problemas de optimización NP":

Conjunto mínimo de borde dominante,

Coincidencia mínima y máxima.