Aplicações Vertex Cover no mundo real

22

Quais aplicativos o problema de cobertura de vértices possui no mundo real?

Quais projetos de setor ou de pesquisa usam software realmente implementado, com base em resultados teóricos para o problema da Vertex Cover? Em particular, algum dos seguintes resultados teóricos foi implementado no software usado?

  • Algoritmos de aproximação para Vertex Cover
  • Algoritmos de tempo exponencial para Vertex Cover
  • Algoritmos tratáveis ​​de parâmetro fixo para Vertex Cover
  • Algoritmos de kernelização para Vertex Cover
ds.algorithms graph-theory graph-algorithms scatman
fonte
6
um dos bons exemplos está no wiki sobre condições de corrida: en.wikipedia.org/wiki/Vertex_cover#Examples Também como motivação, as pessoas dão exemplo de monitoramento. Em cada vértice da solução, mantemos um monitor. Pessoalmente, acho que pesquisar essa resposta no Google é uma opção melhor do que perguntar aqui.
Singlesumit
5
Por que você acha que a cobertura de vértices tem alguma aplicação no mundo real?
Jukka Suomela
3
Eu acho que a resposta é que as coberturas de vértices não têm aplicações significativas. Mas as pessoas os estudam porque as coberturas de vértices são um caso especial simples do problema de cobertura de conjunto. As capas de conjunto têm aplicativos. E você realmente não pode entender a complexidade computacional do problema de cobertura de conjunto, se não entender primeiro os casos especiais simples (e não tão simples), como coberturas de vértices, coberturas de arestas, conjuntos dominantes etc.
Jukka Suomela
3
Conforme observado em en.wikipedia.org/wiki/Vertex_cover#Properties, os vértices que não estão em uma menor cobertura de vértice formam o maior conjunto independente; portanto, esses são essencialmente o mesmo problema. Existem muitas aplicações no mundo real do problema do conjunto independente, por exemplo, porque todo problema de satisfação com restrições pode ser diretamente reduzido a ele.
András Salamon
5
@ András: Esse é um bom argumento, mas a correspondência vale apenas para a menor cobertura de vértice e o maior conjunto independente. Da perspectiva de algoritmos exatos, esses são essencialmente o mesmo problema, mas se estamos interessados ​​em algoritmos eficientes, geralmente estamos satisfeitos com algum tipo de aproximação. E então o problema de cobertura de vértices tem propriedades exclusivas que não são compartilhadas com o problema de conjunto independente. Meu exemplo favorito vem da computação distribuída: pequenas coberturas de vértices não exigem quebra de simetria, grandes conjuntos independentes exigem.
Jukka Suomela

Respostas:

13

Alguns problemas na área da biologia computacional parecem adequados para aplicações práticas que não são artificiais - ou pelo menos não tão artificiais quanto os problemas mencionados por Jukka Suomela.

Por exemplo, as pessoas freqüentemente mencionam o trabalho de F. Abu-Khzam, R. Collins, M. Fellows, M. Langston, W. Suters C. Symons, Algoritmos de Kernelization para o Problema de Cobertura de Vértices: Teoria e Experimentos , Anais do 6º. Workshop de Engenharia de Algoritmos e Experiências (ALENEX), ACM / SIAM, Proc. Matemática Aplicada 115, 2004.

Como afirmam os autores, "Uma das aplicações às quais aplicamos nossos métodos envolve encontrar árvores filogenéticas com base nas informações do domínio das proteínas ..." (seção 8 do artigo acima).

Um subconjunto dos autores tem artigos semelhantes sobre esse tópico, ver, por exemplo, Faisal N. Abu-Khzam, Michael A. Langston, Pushkar Shanbhag e Christopher T. Symons, Algoritmos Paralelos Escaláveis ​​para Problemas do FPT , Algoritmica, Volume 45, Número 3 269-284.

Não tenho certeza se as instâncias usadas nos experimentos foram instâncias do mundo real ou artificiais, mas espero que as duas referências lhe dêem um bom ponto de partida.

Alexander Langer
fonte
4
"pelo menos não tão artificial quanto os problemas mencionados por Jukka Suomela" - e tentei tomar cuidado para não mencionar nenhum problema aqui!
Jukka Suomela
9

Um exemplo pode ser que as bordas do gráfico representem estradas, enquanto os vértices representam a encruzilhada. A tarefa é colocar câmeras de segurança na encruzilhada de uma maneira que permita ver toda a cidade, mas é desejável usar o menor número possível de câmeras para economizar dinheiro.

galbarm
fonte
21
O problema com exemplos como esse é que eles tendem a ser exemplos de brinquedos. Eles podem ser usados ​​para ilustrar a definição, mas acho que não é possível encontrar referências a exemplos do mundo real onde as pessoas realmente escolheram os locais das câmeras de segurança, encontrando uma cobertura mínima de vértices. Problemas do mundo real como esse tendem a ter restrições adicionais, muitas das quais nem são bem definidas, e as soluções tendem a ser gananciosas e incrementais (primeiro instale duas câmeras de segurança nos locais mais críticos e, em seguida, coloque mais algumas quando conseguirmos mais fundos).
Jukka Suomela
Eu recuaria um pouco a objeção de Jukka. É importante destilar um problema para a parte principal que é desafiadora em termos computacionais ou conceituais. Apesar de todas as restrições adicionais do mundo real, acho que a principal dificuldade computacional na seleção de câmeras para cobrir um espaço no mundo real é, essencialmente, um problema de cobertura de vértices. Obviamente, neste caso, um algoritmo de aproximação está perfeitamente bem; não é necessário encontrar a melhor cobertura de vértice. E, neste caso, os gráficos serão bastante simples, talvez planares, por exemplo.
6005
8

Você também pode dar uma olhada em http://www.dharwadker.org/pirzada/applications/ . É sobre aplicações da teoria dos grafos. Ele também declara alguns aplicativos para cobertura de vértices, como na bioquímica e na solução do problema de montagem do SNP ou em um problema de segurança de rede de computadores.

saeedn
fonte
1

Para mim, foi um tanto surpreendente que a cobertura mínima de vértices seja um subproblema do algoritmo húngaro , ou seja, ao determinar um conjunto mínimo de linhas horizontais ou verticais que cobrem todos os zeros gerados pela subtração de mínimos de linhas e colunas.

Isso equivale a encontrar uma cobertura mínima de vértices em um gráfico bipartido que, também surpreendentemente, pode ser resolvido em tempo polinomial bem descrito aqui

Manfred Weis
fonte
0

A cobertura de vértices (em vez disso, várias computações / aproximações) foi o principal mecanismo algorítmico em nosso artigo sobre a classificação de vizinhos mais próximos: http://ieeexplore.ieee.org/document/6867374/

Aryeh
fonte