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.