Najmniejszy zbiór, który przecina niektóre podane zbiory

16

Niech będą zestawami, które mogą mieć wspólne elementy. Szukam najmniejszego zestawu takiego, że . $S_1,S_2,\ldots,S_n$ $X$ $\forall i,\,X\cap S_i \ne \emptyset$

Czy ten problem ma nazwę? Czy może sprowadza się to do znanego problemu?

W moim kontekście opisują elementarne cykle silnie połączonego komponentu i szukam najmniejszego zestawu wierzchołków który przecina wszystkie cykle. $S_1,\ldots,S_n$ $X$

ds.algorithms graph-algorithms

— adl
źródło

25

Twój pierwszy problem to problem przekrojowy hipergrafu (zwany także problemem HITTING SET ). Drugi problem to problem ZESTAWU OPINII VERTEX . Oba problemy są zakończone NP .

— Yota Otachi
źródło

6

Jeśli chcesz rozwiązać rzeczywiste instancje, prawdopodobnie polubisz to:

http://www.sagemath.org/doc/reference/sage/graphs/digraph.html#sage.graphs.digraph.DiGraph.feedback_vertex_set

Nathann

— Nathann Cohen
źródło

1

Dziękuję za ten mile widziany wskaźnik. Korzystanie z Sage nie jest dla mnie opcją, ale miło jest przeczytać szczegółowe informacje na temat rzeczywistej implementacji.

— adl

-3

Jeśli weźmiemy pod uwagę S1, S2 ... Sn jako różne sekwencje i jeśli potrzebujemy najdłuższej podsekwencji, która jest wspólna w tych sekwencjach, wówczas ten typ problemu nazywamy „najdłuższą wspólną podsekwencją (LCS)”. Możemy zmienić warunek, aby był to najmniejszy wspólny podsekwencja, w którym pojedynczy element z zestawu będzie znajdował się jako najmniejszy podsekwencja.

Zobacz przykłady programowania dynamicznego, a otrzymasz szczegółowe informacje ...

— Diplav
źródło

1

czas będzie wykładniczy za

n

$n$

— Sasho Nikolov