En la teoría de grafos , un borde dominando conjunto para un gráfico G = ( V , E ) es un subconjunto D ⊆ E de tal manera que cada borde no en D es adyacente a al menos un borde en D . Un conjunto que domina el borde también se conoce como un conjunto que domina la línea . Las figuras (a) - (d) son ejemplos de conjuntos que dominan los bordes (líneas rojas gruesas).
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/e/e3/Edge-dominating-set.svg/140px-Edge-dominating-set.svg.png)
Un conjunto de dominio de borde mínimo es un conjunto de dominio de borde más pequeño. Las figuras (a) y (b) son ejemplos de conjuntos mínimos de dominio de bordes (se puede comprobar que no hay un conjunto de dominio de bordes de tamaño 2 para este gráfico).
Propiedades
Un conjunto dominante de aristas para G es un conjunto dominante para su gráfico lineal L ( G ) y viceversa.
Cualquier coincidencia máxima es siempre un conjunto que domina la ventaja. Las figuras (b) y (d) son ejemplos de emparejamientos máximos.
Además, el tamaño de un conjunto que domina el borde mínimo es igual al tamaño de una coincidencia máxima mínima . Un emparejamiento máximo mínimo es un conjunto dominante de borde mínimo; La figura (b) es un ejemplo de coincidencia mínima máxima. Un conjunto que domina el borde mínimo no es necesariamente una coincidencia máxima mínima, como se ilustra en la Figura (a); sin embargo, dado un conjunto D que domina el borde mínimo , es fácil encontrar una coincidencia máxima mínima con | D | bordes (ver, por ejemplo, Yannakakis y Gavril 1980 ).
Algoritmos y complejidad computacional
Determinar si hay un conjunto dominante de aristas de un tamaño dado para un gráfico dado es un problema NP-completo (y, por lo tanto, encontrar un conjunto mínimo dominante de aristas es un problema NP-difícil ). Yannakakis y Gavril (1980) muestran que el problema es NP-completo incluso en el caso de un gráfico bipartito con grado máximo 3, y también en el caso de un gráfico plano con grado máximo 3.
Existe un algoritmo de aproximación de tiempo polinomial simple con factor de aproximación 2: encuentre cualquier coincidencia máxima. Un emparejamiento máximo es un conjunto que domina el borde; 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 dominante de borde más pequeño.
Además, la versión del problema ponderada en los bordes 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) muestran que encontrar una aproximación mejor que (7/6) es NP-difícil. Schmied & Viehmann demostraron que el problema es UGC, difícil de aproximar dentro de cualquier constante mejor que 3/2.
Referencias
- 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 aproximación , Springer.
- El conjunto dominante de borde mínimo (versión de optimización) es el problema GT3 en el Apéndice B (página 370).
- La coincidencia mínima máxima (versión de optimización) es el problema GT10 en el Apéndice B (página 374).
- Chlebík, Miroslav; Chlebíková, Janka (2006), "Aproximación de la dureza de los problemas de conjuntos dominantes del borde" , Journal of Combinatorial Optimization , 11 (3): 279-290, doi : 10.1007 / s10878-006-7908-0.
- Garey, Michael R .; Johnson, David S. (1979), Computadoras e intratabilidad: una guía para la teoría de NP-Completeness , WH Freeman, ISBN 978-0-7167-1045-5.
- El conjunto dominante de aristas (versión de decisión) se analiza bajo el problema del conjunto dominante, que es el problema GT2 en el Apéndice A1.1.
- La correspondencia mínima máxima (versión de decisión) es el problema GT10 en el Apéndice A1.1.
- Yannakakis, Mihalis ; Gavril, Fanica (1980), "Conjuntos dominantes de bordes en gráficos", 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 borde de peso mínimo", Matemáticas aplicadas discretas , 118 (3): 199-207, doi : 10.1016 / S0166-218X (00) 00383-8.
- Parekh, Ojas (2002), "Conjuntos que dominan el borde e hipomatizables" , Actas del decimotercer simposio anual ACM-SIAM sobre algoritmos discretos , págs. 287-291.
- Richard Schmied y Claus Viehmann (2012), "Aproximación de bordes dominantes en gráficos densos", Theor. Computación. Sci. 414 (1), págs. 92-99.
enlaces externos
- Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski, Gerhard Woeginger (2000), "Un compendio de problemas de optimización de NP" :