Encontrar un buen subgrafo inducido

Se le da un gráfico con vértices. Puede ser bipartito si quieres. Hay conjuntos de aristas (digamos disjunto). Estoy interesado en el problema de encontrar un subconjunto , lo más pequeño posible (o incluso más pequeño), de modo que el gráfico inducido tenga al menos un borde de cada clase , para . $G = (V,E)$ $n$ $m$ $E_1,\ldots, E_m \subseteq E$ $S \subseteq V$ $G_S$ $E_i$ $i=1,\ldots, m$

Actualmente, sé que este problema está cubierto de forma difícil. También tengo una aproximación no completamente obvia (aproximadamente) . $O(\sqrt{n})$

Esto parece un problema natural: ¿alguien conoce alguna referencia relevante o algún algoritmo mejor?

ds.algorithms graph-theory optimization Sariel Har-Peled
fuente

esto tiene el leve aroma de una variante grupal steiner-tree, pero no tengo una buena intuición de si las diferencias son cosméticas o reales.

Suresh Venkat

Para la versión donde cada borde en

está en alguna

, busque el Subgrafo de arcoíris mínimo.

E

$E$

E_{i}

$E_i$

Andreas Björklund

@ AndreasBjörklund si pones tu comentario como respuesta, lo marcaría como la respuesta correcta. ¡Gracias!

Sariel Har-Peled

Respuestas:

Busque el subgrafo arcoiris mínimo.

Andreas Björklund
fuente

El MRS parece requerir "exactamente uno" en lugar de "al menos uno" según este documento: sciencedirect.com/science/article/pii/S0020019010003339

Suresh Venkat

Sí, pero al menos el resumen (no tengo acceso al artículo) dice subgrafo, no subgrafo inducido, así que pensé que eran lo mismo.

Andreas Björklund

Esto es lo mismo, ya que no insisten en que el gráfico sea inducido por subgrafo.

Sariel Har-Peled

ah ok Mi error entonces.

Suresh Venkat