min memukul set setiap basis matroid

Kami diberi matroid. Tujuan kami adalah untuk menemukan serangkaian elemen ukuran minimum yang memiliki persimpangan non-kosong dengan setiap pangkalan matroid. Apakah masalah dipelajari sebelumnya? Apakah dalam P? Misalnya, dalam matroid spanning tree, hitting set minimum harus berupa minimum cut. Terima kasih.

Saya bermaksud meninggalkan ini sebagai komentar, tetapi saya belum memiliki reputasi untuk melakukannya. Pertanyaan ini diajukan silang di Mathoverflow, di mana saya menyebutkan bahwa masalahnya adalah NP-complete.

Lihat di sini .

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

Pembaruan : Argumen salah seperti yang ditunjukkan. Kesalahannya adalah pada baris terakhir di mana saya berpikir bahwa seseorang mendapatkan integral ganda total tetapi yang terpenting menutupi LP dan tidak berfungsi.

$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 adalah dual integral. Ini menyiratkan bahwa primal adalah integral.

Selama Anda bisa, dalam waktu polinomial dalam jumlah elemen, periksa apakah set H elemen adalah hitting set dan jika tidak, cari satu pangkalan yang tidak mengenai, maka masalahnya jatuh ke dalam bidang masalah Hitting Set Implisit . Lihat makalah berikut untuk algoritma dan diskusi.