min frappant ensemble de chaque base d'un matroïde

On nous donne un matroïde. Notre objectif est de trouver un ensemble d'éléments de taille minimale ayant une intersection non vide avec chaque base du matroïde. Le problème est-il étudié auparavant? Est-ce en P? Par exemple, dans un matroïde couvrant un arbre, l'ensemble de frappe minimum doit être une coupe minimale. Merci.

Je voulais laisser cela comme un commentaire, mais je n'ai pas encore la réputation de le faire. Cette question a été transposée à Mathoverflow, où je mentionne que le problème est NP-complet.

Voyez ici .

Pour éviter une contradiction avec la réponse de Chandra Chekuri, je ne pense pas que le LP donné dans sa réponse soit intégral. Pour le voir, considérons les matroïdes uniformes , où les bases sont toutes des ensembles d'un ensemble. Notez que le vecteur est une solution réalisable pour le LP. Ainsi, si est identique à 1, alors la valeur minimale de LP est au plus . En revanche, un minimum de frappe pour a la taille .$U_{k,n}$ $k$$n$$(1/k, 1/k, \dots, 1/k)$$c$$n/k$$U_{k,n}$$n-k+1$

Mise à jour : l'argument est incorrect comme indiqué. L'erreur est dans la dernière ligne où je pensais que l'on obtient une double intégrité totale, mais le primal couvre LP et cela ne fonctionne pas.

Écrivons un LP pour le problème avec la variable pour chaque élément . Nous voulons telle sorte que pour toutes les bases et pour tout . La première observation est que ce LP peut être résolu en temps polynomial parce que l'oracle de séparation pour le LP est simplement le problème de trouver une base de poids minimum du matroïde donné. Nous voulons affirmer que ce polytope est intégral. Si vous regardez le dual, cela correspond aux bases de remplissage du matroïde dans le vecteur de capacité donné par . Le chapitre 42 de Schrijver montre que lorsque$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$est intégrale le double est intégral. Cela implique que le primal est intégral.

Tant que vous le pouvez, en temps polynomial en nombre d'éléments, vérifiez si un ensemble H d'éléments est un ensemble frappant et sinon, trouvez une base qui n'est pas touchée, puis le problème tombe dans le domaine des problèmes implicites de jeu de frappe . Voir le document suivant pour les algorithmes et les discussions.