Encontrando um bom subgrafo induzido

Você recebe um gráfico com vértices. Pode ser bipartido, se você quiser. Existem conjuntos de arestas (digamos disjuntos). Estou interessado no problema de encontrar um subconjunto , o menor possível (ou até menor), de modo que o gráfico induzido tenha pelo menos uma aresta de cada classe , para . $G = (V,E)$ $n$ $m$ $E_1,\ldots, E_m \subseteq E$ $S \subseteq V$ $G_S$ $E_i$ $i=1,\ldots, m$

Atualmente, eu sei que esse problema está definido como difícil. Eu também tenho um não completamente óbvio (aproximadamente) aproximação. $O(\sqrt{n})$

Isso parece um problema natural - alguém está ciente de referências relevantes ou algoritmos melhores?

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

isso tem o leve aroma de uma variante de árvore steiner de grupo, mas não tenho uma boa intuição sobre se as diferenças são cosméticas ou reais.

Suresh Venkat

Para a versão em que cada aresta em

é, de alguma

, olhar para o mínimo do arco-íris subgráfico.

E

$E$

E_{i}

$E_i$

Andreas Björklund 23/02

@ AndreasBjörklund se você colocar seu comentário como resposta, eu o marcaria como a resposta correta. Obrigado!

Sariel Har-Peled

Respostas:

Procure pelo subgráfico mínimo do arco-íris.

Andreas Björklund
fonte

O MRS parece exigir "exatamente um" em vez de "pelo menos um", de acordo com este documento: sciencedirect.com/science/article/pii/S0020019010003339

Suresh Venkat

Sim, mas pelo menos o resumo (não tenho acesso ao artigo) diz subgráfico, não subgráfico induzido, então pensei que eram os mesmos?

Andreas Björklund

É o mesmo, pois eles não insistem em que o gráfico seja induzido no subgrafo.

Sariel Har-Peled

Ah ok. meu erro então.

Suresh Venkat