Trouver un bon sous-graphique induit

19

On vous donne un graphe avec n sommets. Il peut être bipartite si vous le souhaitez. Il existe m ensembles d'arêtes E 1 , , E mE (disons disjoints). Je m'intéresse au problème de trouver un sous-ensemble S V , aussi petit que possible (ou même plus petit), tel que le graphe induit G S ait au moins un front de chaque classe E i , pour i = 1 , , m .G=(V,E)nmE1,,EmESVGSEii=1,,m

Actuellement, je sais que ce problème est réglé durement. J'ai aussi un O pas complètement évident (à peu près) ( approximation.O(n)

Cela semble être un problème naturel - quelqu'un connaît-il des références pertinentes ou de meilleurs algorithmes?

Sariel Har-Peled
la source
cela a le faible arôme d'une variante de groupe steiner-tree, mais je n'ai pas une bonne intuition pour savoir si les différences sont cosmétiques ou réelles.
Suresh Venkat
1
Pour la version où chaque bord de est dans un certain E i , recherchez Minimum Rainbow Subgraph. EEi
Andreas Björklund
@ AndreasBjörklund si vous mettez votre commentaire comme réponse, je le marquerais comme la bonne réponse. Merci!
Sariel Har-Peled

Réponses:

14

Recherchez le sous-graphique arc-en-ciel minimum.

Andreas Björklund
la source
2
Le MRS semble exiger «exactement un» au lieu de «au moins un» selon ce document: sciencedirect.com/science/article/pii/S0020019010003339
Suresh Venkat
3
Oui, mais au moins l'abrégé (je n'ai pas accès à l'article) dit sous-graphe, pas sous-graphe induit donc j'ai pensé qu'ils étaient les mêmes?
Andreas Björklund
C'est la même chose, car ils n'insistent pas pour que le graphe soit induit sous-graphe.
Sariel Har-Peled
1
Ah ok. mon erreur alors.
Suresh Venkat