En teoría de grafos , un conjunto dominante de aristas para un gráfico 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 borde también se conoce como conjunto dominante de línea . Las figuras (a) a (d) son ejemplos de conjuntos dominantes de bordes (líneas rojas gruesas).
Un conjunto dominante de ventaja mínima es un conjunto dominante de ventaja más pequeño. Las figuras (a) y (b) son ejemplos de conjuntos dominantes de aristas mínimas (se puede comprobar que no hay 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 lineal L ( G ) y viceversa.
Cualquier coincidencia máxima es siempre un conjunto dominante de ventaja. Las figuras (b) y (d) son ejemplos de coincidencias máximas.
Además, el tamaño de un conjunto dominante de borde mínimo es igual al tamaño de una coincidencia máxima mínima . Una coincidencia mínima máxima es un conjunto dominante de borde mínimo; La figura (b) es un ejemplo de coincidencia mínima máxima. Un conjunto dominante de borde mínimo no es necesariamente una coincidencia mínima máxima, como se ilustra en la Figura (a); sin embargo, dado un conjunto D dominante de borde mínimo , es fácil encontrar una coincidencia mínima máxima con | D | bordes (ver, por ejemplo, Yannakakis y Gavril 1980).
Determinar si existe un conjunto dominante de aristas de un tamaño determinado para un gráfico determinado 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 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 simple de aproximación en tiempo polinomial con factor de aproximación 2: encuentre cualquier coincidencia máxima. Una coincidencia máxima es un conjunto dominante de ventaja; 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 ponderada del problema 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 y Viehmann demostraron que el problema es UGC, difícil de aproximar dentro de cualquier constante mejor que 3/2.