O que é um algoritmo para encontrar uma cobertura mínima de vértices em um gráfico bipartido com vértices ponderados?

10

Eu sei que para um gráfico bipartido não ponderado, posso encontrar a cobertura mínima de vértices, encontrando primeiro a correspondência máxima e transformando-a em uma cobertura de vértice usando o Teorema de König. Existe uma modificação que se possa usar se os nós forem ponderados?

ds.algorithms graph-theory Andrey Fedorov
fonte
11
Embora a solução dada por Shiva Kintali resolva seu problema, eu gostaria de acrescentar uma observação rápida: o teorema de König trata de cardinalidade. Você pode adicionar pesos, encontrando uma correspondência bipartida máxima de custo mínimo (existem algoritmos para isso com pesos de borda; pesos de nó fáceis de usar), mas você ainda obteria a cobertura mínima de vértice de custo mínimo - que pode não ser a cobertura de vértices de custo mínimo (ou seja, que poderia consistir em mais nós). Uma correspondência de custo mínimo sem restrições de cardinalidade / optimização apenas iria estar vazia (por pesos positivos) ...
Magnus Lie Hetland

Respostas:

18

O problema de cobertura ponderada de vértice pode ser formulado como um Programa Inteiro (consulte http://en.wikipedia.org/wiki/Vertex_cover ). Quando o gráfico de entrada é bipartido, a matriz de restrição desse IP é totalmente unimodular. Portanto, esse IP pode ser resolvido em tempo polinomial.

Para mais detalhes sobre matrizes unimodulares totais e os algoritmos correspondentes, consulte o excelente livro (três volumes) de Alexander Schrijver .

Shiva Kintali
fonte
6
Para ser mais preciso, o IP pode ser resolvido simplesmente resolvendo o relaxamento do LP. Além disso, pode-se notar que o dual do LP é uma generalização da correspondência (com capacidades correspondentes aos pesos dos vértices na instância de cobertura de vértices) e pode ser resolvido reduzindo-se o fluxo máximo da maneira usual.
Chandra Chekuri 23/03/12
@ChandraChekuri peudo-código da redução do fluxo máximo pode ser encontrado na Figura 4 em incremental Computação de recursos-Envelopes em Modelos produtores e consumidores
xuhdev