¿Qué es un algoritmo para encontrar una cobertura mínima de vértice en un gráfico bipartito con vértices ponderados?

10

Sé que para un gráfico bipartito no ponderado, puedo encontrar la cobertura de vértice mínima al encontrar primero la coincidencia máxima y convertirla en una cubierta de vértice usando el Teorema de König. ¿Hay alguna modificación que se pueda usar si los nodos están ponderados?

ds.algorithms graph-theory Andrey Fedorov
fuente
1
Aunque la solución dada por Shiva Kintali resuelve su problema, me gustaría agregar un comentario rápido: el teorema de König tiene que ver con la cardinalidad. Podría agregar pesos, encontrando una coincidencia bipartita máxima de costo mínimo (hay algoritmos para esto con pesos de borde; pesos de nodo fáciles de usar en su lugar), pero aún así obtendría la cobertura mínima de vértice de costo mínimo, que podría no ser la cobertura de vértice de costo mínimo (es decir, que podría consistir en más nodos). Una coincidencia de costo mínimo sin restricciones de cardinalidad / optimización simplemente estaría vacía (para pesos positivos) ...
Magnus Lie Hetland

Respuestas:

18

El problema de la cobertura del vértice ponderado se puede formular como un programa entero (consulte http://en.wikipedia.org/wiki/Vertex_cover ). Cuando el gráfico de entrada es bipartito, la matriz de restricción de esta IP es totalmente unimodular. Por lo tanto, esta IP se puede resolver en tiempo polinómico.

Para obtener más detalles sobre las matrices unimodulares totales y los algoritmos correspondientes, consulte el excelente libro (de tres volúmenes) de Alexander Schrijver .

Shiva Kintali
fuente
66
Para ser más precisos, la IP se puede resolver simplemente resolviendo la relajación LP. Además, se puede notar que el dual del LP es una generalización de la coincidencia (con capacidades correspondientes a los pesos de los vértices en la instancia de la cubierta del vértice) y se puede resolver reduciendo al flujo máximo de la manera habitual.
Chandra Chekuri
El peudocódigo de @ChandraChekuri de la reducción de flujo máximo se puede encontrar en la Figura 4 en Cálculo incremental de envolturas de recursos en modelos de productor-consumidor
xuhdev