min uderzenie zestawu każdej podstawy matroidu

Dostajemy matroida. Naszym celem jest znalezienie zestawu elementów o minimalnym rozmiarze, który ma niepuste przecięcie z każdą podstawą matroidu. Czy problem był już badany? Czy to jest w P? Na przykład w matroidach drzew przestawnych minimalny zestaw uderzeń powinien być minimalnym cięciem. Dzięki.

Chciałem zostawić to jako komentarz, ale nie mam jeszcze takiej reputacji. To pytanie zostało poruszone w Mathoverflow, gdzie wspominam, że problem jest NP-zupełny.

Zobacz tutaj .

$U_{k,n}$ $k$$n$$(1/k, 1/k, \dots, 1/k)$$c$$n/k$$U_{k,n}$$n-k+1$

Aktualizacja : Jak wskazano, argument jest niepoprawny. Błąd jest w ostatnim wierszu, w którym myślałem, że można uzyskać całkowitą podwójną integralność, ale pierwotne obejmuje LP i nie działa.

$x(e)$$e$$\min \sum_e c(e) x(e)$$\sum_{e \in B} x(e) \ge 1$$B$$x(e) \ge 0$$e$$c$$c$jest integralną podwójnością jest integralną. Oznacza to, że pierwotność jest całką.

Tak długo, jak możesz, w czasie wielomianowym w liczbie elementów, sprawdź, czy zestaw H elementów jest zestawem uderzeń, a jeśli nie, znajdź jedną bazę, która nie jest trafiona, wtedy problem wchodzi w zakres problemów z niejawnym zestawem uderzeń. . Zobacz następujący artykuł dotyczący algorytmów i dyskusji.