Aplicaciones de Vertex Cover en el mundo real

22

¿Qué aplicaciones tiene el Vertex Cover Problem en el mundo real?

¿Qué industria o proyectos de investigación utilizan software implementado realmente que se basa en resultados teóricos para el problema de Vertex Cover? En particular, ¿se implementa alguno de los siguientes resultados teóricos en el software usado?

  • Algoritmos de aproximación para Vertex Cover
  • Algoritmos de tiempo exponencial para Vertex Cover
  • Algoritmos manejables de parámetros fijos para Vertex Cover
  • Algoritmos de kernelización para Vertex Cover
ds.algorithms graph-theory graph-algorithms scatman
fuente
66
Uno de los buenos ejemplos es el wiki en condición de carrera: en.wikipedia.org/wiki/Vertex_cover#Examples También como motivación, las personas dan ejemplos de monitoreo. En cada vértice de la solución, mantenemos un monitor. Personalmente, creo que buscar en Google esta respuesta es una mejor opción que preguntarla aquí.
singhsumit
55
¿Por qué crees que la cubierta de vértice tiene aplicaciones del mundo real?
Jukka Suomela
3
Supongo que la respuesta es que las cubiertas de vértices no tienen aplicaciones significativas. Pero la gente los estudia porque las cubiertas de vértices son un caso especial simple del problema de la cubierta del conjunto. Las fundas de juegos tienen aplicaciones. Y realmente no puede comprender la complejidad computacional del problema de la cubierta del conjunto si no comprende primero los casos especiales simples (y no tan simples) como cubiertas de vértices, cubiertas de bordes, conjuntos dominantes, etc.
Jukka Suomela
3
Como se señaló en en.wikipedia.org/wiki/Vertex_cover#Properties, los vértices que no están en una cubierta de vértice más pequeña forman un conjunto independiente más grande, por lo que estos son esencialmente el mismo problema. Existen muchas aplicaciones en el mundo real del problema de conjunto independiente, por ejemplo, porque cada problema de satisfacción de restricciones puede reducirse directamente a él.
András Salamon
55
@ András: Este es un buen punto, pero la correspondencia solo se cumple para la cubierta de vértice más pequeña y el conjunto independiente más grande. Desde la perspectiva de algoritmos exactos, estos son esencialmente el mismo problema, pero si estamos interesados ​​en algoritmos eficientes, generalmente estamos contentos con algún tipo de aproximaciones. Y luego resulta que el problema de la cubierta del vértice tiene propiedades únicas que no se comparten con el problema del conjunto independiente. Mi ejemplo favorito proviene de la computación distribuida: las cubiertas de vértices pequeñas no requieren ruptura de simetría, los conjuntos independientes grandes lo requieren.
Jukka Suomela

Respuestas:

13

Algunos problemas en el área de la biología computacional parecen adecuados para aplicaciones prácticas que no son artificiales, o al menos no tan artificiales como los problemas mencionados por Jukka Suomela.

Por ejemplo, las personas a menudo mencionan el trabajo de F. Abu-Khzam, R. Collins, M. Fellows, M. Langston, W. Suters C. Symons, Algoritmos de kernelización para el problema de la cubierta de vértices: teoría y experimentos , procedimientos del sexto Taller sobre Algoritmo de Ingeniería y Experimentos (ALENEX), ACM / SIAM, Proc. Matemática Aplicada 115, 2004.

Como afirman los autores, "una de las aplicaciones a las que hemos aplicado nuestros métodos consiste en encontrar árboles filogenéticos basados ​​en información de dominio de proteínas, ..." (sección 8 del documento anterior).

Un subconjunto de autores tiene documentos similares sobre este tema, ver, por ejemplo, Faisal N. Abu-Khzam, Michael A. Langston, Pushkar Shanbhag y Christopher T. Symons, Algoritmos paralelos escalables para problemas de FPT , Algorithmica, Volumen 45, Número 3 269-284.

No estoy seguro de si las instancias utilizadas en los experimentos fueron instancias del mundo real o artificiales, pero espero que las dos referencias le den un buen punto de partida.

Alexander Langer
fuente
44
"al menos no tan artificial como los problemas mencionados por Jukka Suomela" - y traté de tener cuidado de no mencionar ninguno problema aquí!
Jukka Suomela
9

Un ejemplo podría ser que los bordes del gráfico representan caminos, mientras que los vértices representan los cruces. La tarea es colocar cámaras de seguridad en la encrucijada de una manera que le permita ver toda la ciudad, pero es deseable usar la menor cantidad de cámaras posible para ahorrar dinero.

galbarm
fuente
21
El problema con ejemplos como este es que tienden a ser ejemplos de juguetes. Se pueden usar para ilustrar la definición, pero no creo que sea posible encontrar referencias a ejemplos del mundo real en los que las personas realmente hayan elegido las ubicaciones de las cámaras de seguridad al encontrar una cobertura mínima de vértice. Los problemas del mundo real como este tienden a tener restricciones adicionales, muchas de las cuales ni siquiera están bien definidas, y las soluciones tienden a ser ambiciosas e incrementales (primero instale un par de cámaras de seguridad en los lugares más críticos, y luego coloque algunas más cuando tengamos más fondos).
Jukka Suomela
Rechazaría un poco la objeción de Jukka. Es valioso destilar un problema a la parte central que es computacional o conceptualmente desafiante. A pesar de todas las restricciones adicionales del mundo real, creo que la dificultad computacional central en la selección de cámaras para cubrir un espacio en el mundo real es, esencialmente, un problema de cobertura de vértices. Por supuesto, en este caso, un algoritmo de aproximación está perfectamente bien; no es necesario encontrar la mejor cubierta de vértice. Y en este caso los gráficos serán bastante simples, tal vez planos, por ejemplo.
6005
8

También puedes echar un vistazo a http://www.dharwadker.org/pirzada/applications/ . Se trata de aplicaciones de la teoría de grafos. Establece algunas aplicaciones para la cobertura de vértices también, como en bioquímica y para resolver el problema de ensamblaje de SNP o en un problema de seguridad de la red informática.

saeedn
fuente
1

Para mí fue algo sorprendente que la cobertura mínima de vértices es un subproblema de la algoritmo húngaro , es decir, al determinar un conjunto mínimo de líneas horizontales o verticales que cubren todos los ceros generados al restar los mínimos de fila y columna.

Eso equivale a encontrar una cobertura mínima de vértice en un gráfico bipartito que, sorprendentemente, también se puede resolver en un tiempo polinómico muy bien descrito aquí.

Manfred Weis
fuente
0

La cubierta del vértice (más bien, varios cálculos / aproximaciones de la misma) fue el principal motor algorítmico en nuestro artículo sobre la clasificación del vecino más cercano: http://ieeexplore.ieee.org/document/6867374/

Aria
fuente