Trouver un bon sous-graphique induit

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

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

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

ds.algorithms graph-theory optimization 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

Pour la version où chaque bord de

est dans un certain

, recherchez Minimum Rainbow Subgraph.

E

$E$

E_{i}

$E_i$

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:

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

Andreas Björklund
la source

Le MRS semble exiger «exactement un» au lieu de «au moins un» selon ce document: sciencedirect.com/science/article/pii/S0020019010003339

Suresh Venkat

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

Ah ok. mon erreur alors.

Suresh Venkat