Encontrando um bom subgrafo induzido

19

Você recebe um gráfico com n vértices. Pode ser bipartido, se você quiser. Existem m conjuntos de arestas E 1 , , E mE (digamos disjuntos). Estou interessado no problema de encontrar um subconjunto S V , o menor possível (ou até menor), de modo que o gráfico induzido G S tenha pelo menos uma aresta de cada classe E i , para i = 1 , , m .G=(V,E)nmE1,,EmESVGSEii=1,,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(n)

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

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
11
Para a versão em que cada aresta em é, de alguma E eu , olhar para o mínimo do arco-íris subgráfico. EEi
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:

14

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

Andreas Björklund
fonte
2
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
3
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
11
Ah ok. meu erro então.
Suresh Venkat