Applications de Vertex Cover dans le monde réel

22

Quelles sont les applications du problème de couverture Vertex dans le monde réel?

Quels projets industriels ou de recherche utilisent des logiciels réellement mis en œuvre basés sur des résultats théoriques pour le problème Vertex Cover? En particulier, l'un des résultats théoriques suivants est-il mis en œuvre dans les logiciels utilisés?

  • Algorithmes d'approximation pour Vertex Cover
  • Algorithmes à temps exponentiel pour Vertex Cover
  • Algorithmes tractables à paramètres fixes pour Vertex Cover
  • Algorithmes de noyauisation pour Vertex Cover
ds.algorithms graph-theory graph-algorithms scatman
la source
6
l'un des bons exemples est sur wiki sur les conditions de compétition : en.wikipedia.org/wiki/Vertex_cover#Examples Aussi comme motivation, les gens donnent un exemple de surveillance. À chaque sommet de la solution, nous gardons un moniteur. Personnellement, je pense que googler cette réponse est une meilleure option que de la poser ici.
singhsumit
5
Pourquoi pensez-vous que la couverture vertex a des applications réelles?
Jukka Suomela,
3
Je suppose que la réponse est que les couvertures de sommets n'ont pas d'applications importantes. Mais les gens les étudient parce que les couvertures de sommets sont un cas spécial simple du problème de couverture d'ensemble. Les couvertures d'ensemble ont des applications. Et vous ne pouvez pas vraiment comprendre la complexité de calcul du problème de la couverture d'ensemble si vous ne comprenez pas d'abord les cas spéciaux simples (et pas si simples) tels que les couvertures de sommets, les couvertures de bords, les ensembles dominants, etc.
Jukka Suomela
3
Comme indiqué sur en.wikipedia.org/wiki/Vertex_cover#Properties, les sommets qui ne sont pas dans la plus petite couverture de sommets forment un ensemble indépendant le plus important, ce sont donc essentiellement le même problème. Il existe de nombreuses applications réelles du problème des ensembles indépendants, par exemple parce que tout problème de satisfaction de contraintes peut y être directement réduit.
András Salamon,
5
@ András: C'est un bon point, mais la correspondance ne vaut que pour la plus petite couverture de sommets et le plus grand ensemble indépendant. Du point de vue des algorithmes exacts, il s'agit essentiellement du même problème, mais si nous nous intéressons aux algorithmes efficaces, nous nous contentons généralement d'une sorte d'approximations. Et puis, il s'avère que le problème de couverture de vertex a des propriétés uniques qui ne sont pas partagées avec le problème d'ensemble indépendant. Mon exemple préféré vient de l'informatique distribuée: les petites couvertures de sommets ne nécessitent pas de rupture de symétrie, les grands ensembles indépendants le nécessitent.
Jukka Suomela

Réponses:

13

Certains problèmes dans le domaine de la biologie computationnelle semblent convenir à des applications pratiques qui ne sont pas artificielles - ou du moins pas aussi artificielles que les problèmes mentionnés par Jukka Suomela.

Par exemple, les gens mentionnent souvent les travaux de F. Abu-Khzam, R. Collins, M. Fellows, M. Langston, W. Suters C. Symons, Kernelization Algorithms for the Vertex Cover Problem: Theory and Experiments , Proceedings of the 6th Atelier sur l'ingénierie algorithmique et les expériences (ALENEX), ACM / SIAM, Proc. Mathématiques appliquées 115, 2004.

Comme le déclarent les auteurs, "L'une des applications auxquelles nous avons appliqué nos méthodes consiste à trouver des arbres phylogénétiques basés sur des informations sur le domaine des protéines, ..." (section 8 de l'article ci-dessus).

Un sous-ensemble des auteurs a des articles similaires sur ce sujet, voir, par exemple, Faisal N. Abu-Khzam, Michael A. Langston, Pushkar Shanbhag et Christopher T. Symons, Scalable Parallel Algorithms for FPT Problems , Algorithmica, Volume 45, Number 3 , 269-284.

Je ne sais pas si les instances utilisées dans les expériences étaient des instances réelles ou artificielles, mais j'espère que les deux références vous donneront un bon point de départ.

Alexander Langer
la source
4
"du moins pas aussi artificiel que les problèmes mentionnés par Jukka Suomela" - et j'ai essayé de faire attention à ne pas mentionner de problèmes ici!
Jukka Suomela
9

Un exemple pourrait être que les bords du graphique représentent des routes tandis que les sommets représentent le carrefour. La tâche consiste à placer des caméras de sécurité au carrefour de manière à vous permettre de voir toute la ville, mais il est souhaitable d'utiliser le moins de caméras possible afin d'économiser de l'argent.

galbarm
la source
21
Le problème avec des exemples comme celui-ci est qu'ils ont tendance à être des exemples de jouets. Ils peuvent être utilisés pour illustrer la définition, mais je ne pense pas qu'il soit possible de trouver des références à des exemples du monde réel où les gens ont effectivement choisi l'emplacement des caméras de sécurité en trouvant une couverture de sommet minimale. Des problèmes réels comme celui-ci ont tendance à avoir des contraintes supplémentaires, dont beaucoup ne sont même pas bien définies, et les solutions ont tendance à être gourmandes et incrémentielles (installez d'abord quelques caméras de sécurité dans les endroits les plus critiques, puis mettez-en plus lorsque nous obtenons plus de fonds).
Jukka Suomela
Je repousserais un peu l'objection de Jukka. Il est utile de distiller un problème à la partie centrale qui est difficile à calculer ou à concevoir. Malgré toutes les contraintes supplémentaires du monde réel, je pense que la principale difficulté de calcul dans la sélection de caméras pour couvrir un espace dans le monde réel est, essentiellement, un problème de couverture de vertex. Bien sûr, dans ce cas, un algorithme d'approximation est parfaitement fin; il n'est pas nécessaire de trouver la meilleure couverture de vertex. Et dans ce cas les graphes seront assez simples, peut-être plans par exemple.
6005
8

Vous pouvez également consulter http://www.dharwadker.org/pirzada/applications/ . Il s'agit des applications de la théorie des graphes. Il indique également certaines applications pour la couverture de sommets, comme en biochimie et en résolvant le problème d'assemblage SNP ou dans un problème de sécurité de réseau informatique.

saeedn
la source
1

Pour moi, il était quelque peu surprenant que la couverture minimale des sommets soit un sous-problème de l' algorithme hongrois , à savoir lors de la détermination d'un ensemble minimal de lignes horizontales ou verticales qui couvrent tous les zéros générés par la soustraction des minima de lignes et de colonnes.

Cela revient à trouver une couverture minimale des sommets dans un graphe bipartite qui, aussi étonnamment, peut être résolu en temps polynomial bien décrit ici

Manfred Weis
la source