conjunto de golpes mínimos de cada base de un matroide

Nos dan un matroid. Nuestro objetivo es encontrar un conjunto de elementos de tamaño mínimo que tenga una intersección no vacía con cada base del matroide. ¿El problema se estudió antes? ¿Está en P? Por ejemplo, en un árbol de expansión matroide, el conjunto de golpes mínimos debe ser un corte mínimo. Gracias.

Tenía la intención de dejar esto como un comentario, pero todavía no tengo la reputación de hacerlo. Esta pregunta fue cruzada en Mathoverflow, donde menciono que el problema es NP-completo.

Ver aquí .

Para evitar una contradicción con la respuesta de Chandra Chekuri, no creo que el LP dado en su respuesta sea integral. Para ver esto, considere los matroides uniformes , donde las bases son todos los subconjuntos de un conjunto . Tenga en cuenta que el vector es una solución factible para el LP. Por lo tanto, si es idénticamente 1, entonces el valor mínimo de LP es como máximo . Por otro lado, un golpe mínimo para tiene un tamaño .$U_{k,n}$ n ( 1 / k , 1 / k , … , 1 / k ) c n / k U k , n n - k + $k$$n$$(1/k, 1/k, \dots, 1/k)$$c$$n/k$$U_{k,n}$$n-k+1$

Actualización : el argumento es incorrecto como se señaló. El error está en la última línea donde pensé que uno tiene integralidad dual total, pero el primario está cubriendo LP y no funciona.

Escribamos un LP para el problema con la variable para cada elemento . Queremos modo que para todas las bases y para todas las . La primera observación es que este LP se puede resolver en tiempo polinómico porque el oráculo de separación para el LP es simplemente el problema de encontrar una base de peso mínimo del matroide dado. Queremos afirmar que este politopo es integral. Si observa el doble, corresponde a las bases de empaque del matroide en el vector de capacidad dado por . El Capítulo 42 de Schrijver muestra que cuando$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$es integral el dual es integral. Esto implica que lo primario es integral.

Siempre que pueda, en tiempo polinómico en número de elementos, verifique si un conjunto H de elementos es un conjunto de bateo y si no, encuentre una base que no sea golpeada, entonces el problema cae en el ámbito de los problemas del conjunto de bateo implícito . Consulte el siguiente documento para ver algoritmos y debates.