Finden eines guten induzierten Subgraphen

19

Sie erhalten einen Graphen mit n Eckpunkten. Es könnte zweiteilig sein, wenn Sie wollen. Es gibt m Sätze von Kanten E 1 , , E mE (sagen wir disjunkt). Ich interessiere mich für das Problem, eine möglichst kleine (oder noch kleinere) Teilmenge S V zu finden , so dass der induzierte Graph G S aus jeder Klasse E i mindestens eine Kante hat , für i = 1 , , m .G=(V,E)nmE1,,EmESVGSEii=1,,m

Derzeit weiß ich, dass dieses Problem nicht ganz so einfach zu lösen ist. Ich habe auch ein nicht ganz offensichtliches (ungefähr) Annäherung.O(n)

Dies scheint ein natürliches Problem zu sein - kennt jemand relevante Referenzen oder bessere Algorithmen?

Sariel Har-Peled
quelle
Dies hat das schwache Aroma einer Gruppe Steiner-Baum-Variante, aber ich habe keine gute Intuition dafür, ob die Unterschiede kosmetisch oder real sind.
Suresh Venkat
1
Suchen Sie für die Version, in der sich jede Kante in in einem E i befindet , nach Minimum Rainbow Subgraph. EEi
Andreas Björklund
@ AndreasBjörklund wenn du deinen Kommentar als Antwort setzt, würde ich ihn als die richtige Antwort markieren. Vielen Dank!
Sariel Har-Peled

Antworten:

14

Suchen Sie nach Minimum Rainbow Subgraph.

Andreas Björklund
quelle
2
Die MRS scheint "genau eine" anstelle von "mindestens einer" zu verlangen: sciencedirect.com/science/article/pii/S0020019010003339
Suresh Venkat
3
Ja, aber zumindest in der Zusammenfassung (ich habe keinen Zugriff auf das Papier) heißt es Subgraph, nicht induzierter Subgraph, also dachte ich, sie wären gleich?
Andreas Björklund
Dies ist das gleiche, da sie nicht darauf bestehen, dass der Graph als Teilgraph induziert wird.
Sariel Har-Peled
1
ach ok Mein Fehler dann.
Suresh Venkat