мин, поражающий множество каждой базы матроида

Нам дают матроида. Наша цель - найти набор элементов минимального размера, который имеет непустое пересечение с каждой базой матроида. Проблема изучалась раньше? Это в P? Например, в матроиде остовного дерева минимальный набор попаданий должен быть минимальным срезом. Спасибо.

Я хотел оставить это как комментарий, но у меня пока нет репутации. Этот вопрос был задан в Mathoverflow, где я упоминаю, что проблема является NP-полной.

Смотрите здесь .

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

Обновление : аргумент неверен, как указано. Ошибка в последней строке, где я думал, что получается полная двойная интегральность, но первичное - это LP, и оно не работает.

$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$является интегральным, двойственное является интегральным. Это означает, что первичное является интегральным.

До тех пор, пока вы можете за полиномиальное время по количеству элементов проверить, является ли набор H элементов ударным набором, и если нет, найти одну базу, которая не является хитовой, тогда проблема попадает в сферу задач неявного ударного набора. , См. Следующую статью для алгоритмов и обсуждений.