min. Schlagsatz jeder Basis einer Matroid

Wir bekommen eine Matroid. Unser Ziel ist es, eine Reihe von Elementen mit minimaler Größe zu finden, die einen nicht leeren Schnittpunkt mit jeder Basis der Matroid haben. Wird das Problem schon einmal untersucht? Ist es in P? Zum Beispiel sollte in einer Spanning Tree Matroid der minimale Schlagsatz ein minimaler Schnitt sein. Vielen Dank.

Ich wollte dies als Kommentar hinterlassen, habe aber noch nicht den Ruf, dies zu tun. Diese Frage wurde bei Mathoverflow gestellt, wo ich erwähne, dass das Problem NP-vollständig ist.

Siehe hier .

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

Update : Das Argument ist falsch, wie bereits erwähnt. Der Fehler ist in der letzten Zeile, in der ich dachte, dass man eine totale doppelte Integrität erhält, aber das Ursprüngliche deckt LP ab und es funktioniert nicht.

$x(e)$$e$∑ e ∈ B x ( e ) ≥ 1 B x ( e ) ≥ 0 e c $\min \sum_e c(e) x(e)$$\sum_{e \in B} x(e) \ge 1$$B$$x(e) \ge 0$$e$$c$$c$ist ganzzahlig das dual ist ganzzahlig. Dies impliziert, dass das Ursprüngliche ein Integral ist.

Solange Sie in der Polynomzeit der Anzahl der Elemente prüfen können, ob eine Menge H von Elementen eine Schlagmenge ist, und wenn nicht, eine Basis finden, die nicht getroffen wird, fällt das Problem in den Bereich der Probleme der impliziten Schlagmenge . Siehe das folgende Papier für Algorithmen und Diskussionen.