Vertex Cover-Anwendungen in der realen Welt

22

Welche Anwendungen hat das Vertex Cover Problem in der realen Welt?

Welche Industrie- oder Forschungsprojekte verwenden tatsächlich implementierte Software, die auf theoretischen Ergebnissen für das Vertex-Cover-Problem basiert? Werden bestimmte der folgenden theoretischen Ergebnisse in der verwendeten Software umgesetzt?

  • Approximationsalgorithmen für Vertex Cover
  • Exponentialzeit-Algorithmen für Vertex Cover
  • Traktierbare Algorithmen mit festen Parametern für Vertex Cover
  • Kernelisierungsalgorithmen für Vertex Cover
ds.algorithms graph-theory graph-algorithms Scatman
quelle
6
Eines der guten Beispiele ist im Wiki unter Rennbedingungen: en.wikipedia.org/wiki/Vertex_cover#Examples Auch als Motivation geben die Leute ein Beispiel für die Überwachung. An jedem Scheitelpunkt der Lösung behalten wir einen Monitor. Ich persönlich halte es für besser, diese Antwort zu googeln, als hier nachzufragen.
singhsumit
5
Warum hat Vertex Cover Ihrer Meinung nach echte Anwendungen?
Jukka Suomela
3
Ich denke, die Antwort ist, dass Vertex-Cover keine signifikanten Anwendungen haben. Aber die Leute studieren sie, weil Vertex-Covers ein einfacher Spezialfall des Set-Cover-Problems sind. Set Covers haben Anwendungen. Und Sie können die rechnerische Komplexität des Set-Cover-Problems nicht wirklich verstehen, wenn Sie nicht zuerst die einfachen (und nicht so einfachen) Spezialfälle wie Vertex-Cover, Edge-Cover, dominierende Sets usw.
verstehen
3
Wie unter en.wikipedia.org/wiki/Vertex_cover#Properties angegeben, bilden die Scheitelpunkte, die sich nicht in einem kleinsten Scheitelpunkt-Cover befinden, eine größte unabhängige Menge, sodass dies im Wesentlichen dasselbe Problem darstellt. Es gibt viele reale Anwendungen des Problems der unabhängigen Menge, zum Beispiel, weil jedes Problem der Beschränkungszufriedenheit direkt darauf reduziert werden kann.
András Salamon
5
@ András: Das ist ein guter Punkt, aber die Entsprechung gilt nur für die kleinste Vertex-Abdeckung und die größte unabhängige Menge. Aus der Sicht der genauen Algorithmen handelt es sich im Wesentlichen um dasselbe Problem. Wenn wir jedoch an effizienten Algorithmen interessiert sind, begnügen wir uns normalerweise mit einer Art von Annäherungen. Und dann stellt sich heraus, dass das Vertex-Cover-Problem eindeutige Eigenschaften hat, die nicht mit dem Independent-Set-Problem geteilt werden. Mein Lieblingsbeispiel stammt aus der verteilten Datenverarbeitung: Kleine Scheitelpunktabdeckungen erfordern keine Symmetrieunterbrechung, große unabhängige Mengen erfordern dies.
Jukka Suomela

Antworten:

13

Einige Probleme auf dem Gebiet der Computational Biology scheinen für praktische Anwendungen geeignet zu sein, die nicht künstlich sind - oder zumindest nicht so künstlich wie die von Jukka Suomela erwähnten Probleme.

Beispielsweise erwähnen die Leute häufig die Arbeiten von F. Abu-Khzam, R. Collins, M. Fellows, M. Langston, W. Suters, C. Symons, Kernelisierungsalgorithmen für das Vertex-Cover-Problem: Theorie und Experimente , Proceedings of the 6th Workshop zu Algorithm Engineering und Experimenten (ALENEX), ACM / SIAM, Proc. Angewandte Mathematik 115, 2004.

Wie die Autoren feststellen, "besteht eine der Anwendungen, auf die wir unsere Methoden angewendet haben, darin, phylogenetische Bäume auf der Grundlage von Proteindomäneninformationen zu finden, ..." (Abschnitt 8 des obigen Papiers).

Eine Untergruppe der Autoren hat ähnliche Veröffentlichungen zu diesem Thema, siehe z. B. Faisal N. Abu-Khzam, Michael A. Langston, Pushkar Shanbhag und Christopher T. Symons, Skalierbare parallele Algorithmen für FPT-Probleme , Algorithmica, Band 45, Nummer 3 269-284.

Ich bin nicht sicher, ob die in den Experimenten verwendeten Instanzen reale oder künstliche Instanzen waren, aber ich hoffe, die beiden Referenzen geben Ihnen einen guten Ausgangspunkt.

Alexander Langer
quelle
4
"Zumindest nicht so künstlich wie die von Jukka Suomela erwähnten Probleme" - und ich habe versucht, hier keine Probleme zu erwähnen !
Jukka Suomela
9

Ein Beispiel könnte sein, dass die Kanten des Graphen Straßen darstellen, während die Eckpunkte die Kreuzungen darstellen. Die Aufgabe besteht darin, Überwachungskameras so an der Kreuzung zu platzieren, dass Sie die ganze Stadt sehen können. Es ist jedoch wünschenswert, so wenig Kameras wie möglich zu verwenden, um Geld zu sparen.

Galbarm
quelle
21
Das Problem bei Beispielen wie diesem ist, dass es sich in der Regel um Spielzeugbeispiele handelt. Sie können verwendet werden , um die Definition zu veranschaulichen, aber ich glaube nicht , ist es möglich, Hinweise auf finden reale Beispiele , bei denen , wo die Menschen tatsächlich die Standorte der Überwachungskameras ausgewählt durch eine minimale Knotenüberdeckung zu finden. Bei solchen Problemen in der realen Welt treten in der Regel zusätzliche Einschränkungen auf, von denen viele nicht genau definiert sind, und die Lösungen sind in der Regel gierig und inkrementell wenn wir mehr Geld bekommen).
Jukka Suomela
Ich würde Jukkas Einwand ein wenig zurückdrängen. Es ist wertvoll, ein Problem auf den Kernteil zu beschränken, der rechnerisch oder konzeptionell herausfordernd ist. Trotz all der zusätzlichen Einschränkungen der realen Welt denke ich, dass die Hauptschwierigkeit bei der Auswahl von Kameras zur Abdeckung eines Raums in der realen Welt im Wesentlichen ein Problem der Scheitelpunktabdeckung ist. Natürlich ist in diesem Fall ein Approximationsalgorithmus vollkommen in Ordnung; Es ist nicht erforderlich, die beste Scheitelpunktabdeckung zu finden. In diesem Fall sind die Grafiken recht einfach, beispielsweise eben.
6005,
8

Sie können auch einen Blick auf http://www.dharwadker.org/pirzada/applications/ werfen . Es geht um Anwendungen der Graphentheorie. Es werden auch einige Anwendungen für die Scheitelpunktabdeckung aufgeführt, beispielsweise in der Biochemie und bei der Lösung des SNP-Montageproblems oder bei einem Computer-Netzwerksicherheitsproblem.

saeedn
quelle
1

Für mich war es etwas überraschend, dass die minimale Scheitelpunktabdeckung ein Unterproblem des ungarischen Algorithmus ist , und zwar beim Bestimmen einer minimalen Menge horizontaler oder vertikaler Linien, die alle Nullen abdecken, die durch Subtrahieren von Zeilen- und Spaltenminima erzeugt wurden.

Dies läuft darauf hinaus, in einem zweigliedrigen Graphen eine minimale Scheitelpunktabdeckung zu finden , die sich überraschenderweise auch in der hier gut beschriebenen Polynomzeit lösen lässt

Manfred Weis
quelle
0

Scheitelpunktabdeckung (stattdessen verschiedene Berechnungen / Annäherungen) war die wichtigste algorithmische Engine in unserem Artikel über die Klassifizierung des nächsten Nachbarn: http://ieeexplore.ieee.org/document/6867374/

Aryeh
quelle