conjunto de batidas mínimas de todas as bases de um matróide

Nos é dado um matróide. Nosso objetivo é encontrar um conjunto de elementos de tamanho mínimo que possua uma interseção não vazia com todas as bases do matróide. O problema já foi estudado? Está em P? Por exemplo, em um matróide de spanning tree, o conjunto de batidas mínimo deve ser um corte mínimo. Obrigado.

Eu pretendia deixar isso como um comentário, mas ainda não tenho reputação de fazê-lo. Esta questão foi cruzada no Mathoverflow, onde mencionei que o problema é NP-completo.

Veja aqui .

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

Atualização : o argumento está incorreto, conforme indicado. O erro está na última linha em que pensei que se obtém total dualidade total, mas o primal está cobrindo LP e não funciona.

$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$é integral, o dual é integral. Isso implica que o primal é integral.

Contanto que você possa, no tempo polinomial em número de elementos, verifique se um conjunto H de elementos é um conjunto de batidas e, se não for, encontre uma base que não seja atingida, o problema cai no domínio dos problemas do Conjunto de Batidas Implícitas . Veja o documento a seguir para algoritmos e discussões.