Conjunto máximo independente de um gráfico bipartido

19

Estou tentando encontrar o conjunto independente máximo de um gráfico biparito.

Encontrei o seguinte em algumas notas "13 de maio de 1998 - Universidade de Washington - CSE 521 - Aplicações de fluxo de rede" :

Problema:

Dado um bipartido gráfico G=(U,V,E) , encontrar um conjunto independente UV que é tão grande quanto possível, em que UU e VV . Um conjunto é independente se não houver arestas de E entre os elementos do conjunto.

Solução:

Construa um gráfico de fluxo nos vértices UV{s,t} . Para cada aresta (u,v)E há uma aresta de capacidade infinita de u até v . Para cada uU , existe uma margem de capacidade unitária de s para u , e para cada vV , existe uma margem de capacidade unitária de v até t .

Encontrar um corte capacidade finita (S,T) , com sS e tT . Deixe que U=US e V=VT . O conjunto UV é independente, pois não há arestas de capacidade infinita cruzando o corte. O tamanho do corte é |UU|+|VV|=|U|+|V||UV|. Isso, para tornar o conjunto independente o maior possível, tornamos o corte o menor possível.

Então, vamos considerar isso como o gráfico:

A - B - C
    |
D - E - F

Podemos dividir isso em um gráfico bipartido da seguinte forma (U,V)=({A,C,E},{B,D,F})

Podemos ver pela busca por força bruta que o único máximo conjunto independente é A,C,D,F . Vamos tentar trabalhar com a solução acima:

Portanto, a matriz de adjacência da rede de fluxo construída seria:

stABCDEFs00101010t00010101A1000000B01000C1000000D0100000E10000F0100000

Aqui é onde estou preso, o menor corte de capacidade finita que vejo é trivial: (S,T)=({s},{t,A,B,C,D,E,F}) com capacidade de 3)

O uso desse corte leva a uma solução incorreta de:

U=US={}
V=VT={B,D,F}
UV={B,D,F}

Enquanto esperávamos UV={A,C,D,F} ? Alguém pode identificar onde eu errei no meu raciocínio / trabalho?

Andrew Tomazos
fonte
(S, T) = ({s, A, B, C}, {t, D, E, F}) tem capacidade 2
1
@ Brian, há uma borda de capacidade infinita de B a E em todo o seu corte, portanto é uma capacidade infinita.
Andrew Tomazos
se eu entendi isso corretamente, com base na solução de força bruta, você precisa de um corte em que S contenha A e C e T contenha D e F, o que torna seu corte {s, A, C}, {t, D, F} . Agora, como você constrói o corte?
Njzk2
Além disso, isso se parece com o Ford-Fulkerson, no qual as bordas têm capacidade para um.
Njzk2
Procure o algoritmo húngaro.
Patrik Vörös

Respostas:

14

O complemento de um conjunto independente máximo é uma cobertura mínima de vértice.

Para encontrar uma cobertura mínima de vértices em um gráfico bipartido, consulte o teorema de König .

Jukka Suomela
fonte
2
Isso (talvez) resolve o problema, mas não responde à pergunta.
Raphael
2
@ Rafael: Eu concordo se você remover a palavra "talvez". :)
Jukka Suomela
1
Tenho certeza de que resolve o problema, mas não sei se isso ajuda Andrew a resolver o problema.
Raphael
3
Eu resolvi isso como você sugere: HopcroftKarp -> correspondência máxima -> Konigs Thereom -> Capa mínima de vértice -> Complemento -> Conjunto máximo independente. Eu ainda gostaria de saber por que o método de fluxo descrito na minha pergunta não parece funcionar.
Andrew Tomazos
5

A solução fornecida está claramente incorreta, como você demonstra no contra-exemplo. Observe que o gráfico U + V é um componente conectado pelas arestas de capacidade infinita. Portanto, todo corte válido deverá conter todos os A, B, C, D, E, F do mesmo lado.

Tentando rastrear de onde veio a solução: http://www.cs.washington.edu/education/courses/cse521/01sp/flownotes.pdf cita Network Flows, de Ahuja, Magnanti e Orlin, para alguns dos problemas. Este livro não possui direitos autorais e pode ser baixado em http://archive.org/details/networkflows00ahuj, mas parece não conter esse problema e solução (procure todas as ocorrências de "bipartido").

Observe que o parágrafo de explicação da solução não mostra que o menor corte do gráfico que ele constrói corresponde ao conjunto independente máximo . Apenas mostra uma maneira de obter um conjunto independente.

E, no entanto, você pode ver o que o algoritmo está tentando fazer. Aqui está o que o conjunto independente máximo real corresponde em termos de seu corte s, t:

Gráfico

A borda de capacidade infinita que quebra o algoritmo é enfatizada.

Não sei como consertar o algoritmo para o que foi planejado. Talvez o custo de uma aresta infinita deva ser zero se retroceder (ou seja, para onde vai de S para T, mas passa do lado t para o lado s)? Mas ainda é fácil encontrar o min-cut / max-flow com essa não linearidade? Além disso, pensando em uma maneira de fazer a ponte entre a solução de @Jukka Suomela e o algoritmo da pergunta, há uma dificuldade em irmos da correspondência máxima para a cobertura mínima de vértices: encontrar a correspondência máxima pode ser feito por um fluxo máximo como o algoritmo, como você recupera a cobertura mínima de vértice usando um algoritmo semelhante ao fluxo? Conforme descrito aqui, depois que a correspondência máxima for encontrada, as arestas entre U e V serão direcionadas para encontrar a cobertura mínima de vértice. Portanto, novamente, isso não mostra que basta uma aplicação simples de min-cut / max-flow para resolver esse problema.

Evgeni Sergeev
fonte
2

STS

yu25x
fonte
1
Concordo com você, mas você poderia adicionar mais detalhes, por exemplo, uma prova completa de correção do algoritmo de fluxo e como o algoritmo se aplica ao exemplo do OP?
xskxzr 10/06
A nota neste documento tem uma prova curta de correção. cs.washington.edu/education/courses/cse521/01sp/flownotes.pdf Por exemplo, se você observar a figura de Evgeni Sergeev acima, as bordas devem estar todas voltadas para baixo. Então, as únicas duas arestas de S são (s, e) e (b, t), a aresta vermelha em negrito entra em S e não deve ser contada no valor de corte.
yu25x 15/06
0

O corte deve estar no fluxo real, não nas capacidades. Como o fluxo de s é finito, qualquer corte {S, T} será finito. O resto é explicado acima.

Talmon
fonte
1
Você tem certeza? Os cortes geralmente têm capacidade e, de qualquer forma, já sabemos que o corte mínimo é finito, portanto, cortes infinitos não parecem ser o problema.
David Richerby
0

UV

G{A,C,D,F}

Ajit Kumar
fonte