Minimum Vertex Abdeckung

Question

Ich versuche, eine Vertex-Abdeckung für einen "fast" Baum mit 50.000 Vertices zu bekommen. Das Diagramm wird als ein Baum mit zufälligen Kanten erzeugt, die hinzugefügt werden, um es "fast" zu einem Baum zu machen.

Ich verwendete die Approximationsmethode, bei der Sie zwei Scheitelpunkte miteinander verbinden, sie dem Cover hinzufügen und sie aus dem Diagramm entfernen und dann zu einem anderen Satz von Scheitelpunkten übergehen. Danach habe ich versucht, die Anzahl der Scheitelpunkte zu reduzieren, indem ich die Scheitelpunkte entferne, die alle ihre Nachbarn innerhalb der Scheitelpunktabdeckung haben.

Meine Frage ist, wie würde ich die Vertex Cover noch kleiner machen? Ich versuche, so niedrig wie möglich zu gehen.

Answer 1

Hier ist eine Idee, aber ich habe keine Ahnung, ob es eine Verbesserung in der Praxis:

Von https://en.wikipedia.org/wiki/Biconnected_component „Jeder zusammenhängenden Graph zerfällt in einen Baum von Gelenkpunkt des Block-gefällter Baum des Graphen genannt.“ Außerdem können Sie eine solche Zerlegung in linearer Zeit berechnen.

Ich schlage vor, dass wenn Sie zwei Scheitelpunkte heiraten und entfernen, Sie dies nur für zwei Scheitelpunkte innerhalb der gleichen zweifach verbundenen Komponente tun. Wenn Sie die Scheitelpunkte zum Zusammenführen nicht mehr benötigen, haben Sie eine Reihe von Bäumen, die nicht miteinander verbunden sind. Das Vertex-Coverage-Problem bei Bäumen ist über dynamische Programmierung steuerbar: Berechnen Sie für jeden Knoten die Kosten für die beste Antwort, wenn dieser Knoten zum Cover hinzugefügt wird und dieser Knoten nicht zum Cover hinzugefügt wird. Sie können die Antworten für einen Knoten mit den besten Antworten für seine Kinder berechnen. Ein anderer Weg - ich würde es besser wissen - wäre, den minimalen Spannbaum des Graphen zu berechnen und dynamische Programmierung zu verwenden, um die beste Vertexabdeckung für diesen Baum zu berechnen, die Verbindungen außerhalb des Baums zu vernachlässigen und die abgedeckten Verbindungen zu entfernen aus dem Graphen und dann weiter, indem Sie die Scheitelpunkte wie zuvor heiraten.

Ich denke, ich bevorzuge den minimalen Spannbaum. Beim Erstellen des minimalen Spannbaums löschen Sie eine kleine Anzahl von Links. Ein Baum mit N Knoten hatte N-1 Links, also erhalten Sie, wenn Sie nicht den ursprünglichen Baum zurückbekommen, einen mit so vielen Links wie er. Eine Vertex-Abdeckung für den vollständigen Graph ist auch eine Vertex-Abdeckung für den minimalen Spannbaum. Wenn also die richtige Antwort für den gesamten Graph V Vertices hat, gibt es eine Antwort für den minimalen Spannbaum mit höchstens V Vertices. Wenn dem Baum k zufällige Flanken hinzugefügt wurden, gibt es k Kanten (nicht notwendigerweise die gleichen), die hinzugefügt werden müssen, um den minimalen Spannbaum in den vollständigen Graphen zu verwandeln. Sie können sicher stellen, dass diese neuen Kanten mit höchstens k Ecken bedeckt sind. Wenn also die optimale Antwort V Ecken hat, erhalten Sie eine Antwort mit höchstens V + k Ecken.

Answer 2

Minimum Vertex Cover ist ein NP-vollständiger Algorithmus, was bedeutet, dass Sie es nicht in einer angemessenen Zeit selbst für so etwas wie 100 Vertices lösen können (ganz zu schweigen von 50k).

Für einen Baum gibt es einen polynomischen Zeit-Greedy-Algorithmus, der auf DFS basiert, aber die Tatsache, dass Sie "zufällige Kanten hinzugefügt" haben, verschraubt alles und macht diesen Algorithmus unbrauchbar.

Wikipedia has an article about approximation algorithm, behauptet, dass es Faktor 2 erreicht und behauptet, dass kein besserer Algorithmus bekannt ist, was es unwahrscheinlich macht, dass Sie einen finden werden.

Answer 3

Hier ist ein Versuch auf eine genaue Antwort, die nur mit einer kleinen Anzahl von Links durchgeführt werden kann, oder wenn sie die Inter-Knoten-Abstände nicht sehr ändern.

Suchen Sie einen minimalen Spannbaum, und teilen Sie Kanten in "Baumkanten" und "hinzugefügte Kanten", wobei die Baumkanten einen minimalen Spannbaum bilden und die hinzugefügten Kanten nicht dafür ausgewählt wurden. Sie sind vielleicht nicht die Kanten, die während der Konstruktion tatsächlich hinzugefügt werden, aber das macht nichts.Alle Bäume auf N Knoten haben N-1 Kanten, also haben wir die gleiche Anzahl von Kanten, die während der Erstellung verwendet wurden, auch wenn sie nicht die gleichen Kanten haben.

Nun täuschen Sie vor, Sie können auf die Antwort im hinteren Teil des Buches nur genug zu sehen, für einen Scheitelpunkt von jeder hinzugefügten Kante, ob dieser Scheitelpunkt Teil der besten Vertex-Abdeckung war. Wenn dies der Fall ist, können Sie diesen Scheitelpunkt und seine Verknüpfungen aus dem Problem entfernen. Wenn nicht, muss der andere Knoten so sein, dass Sie ihn und seine Links aus dem Problem entfernen können.

Sie müssen jetzt eine minimale Vertex-Abdeckung für einen Baum oder eine Anzahl von getrennten Bäumen finden, und wir wissen, wie das geht - siehe meine andere Antwort für ein bisschen mehr Handwaving.

Wenn Sie nicht auf der Rückseite des Buches nach einer Antwort suchen können, und es gibt k addierte Kanten, versuchen Sie alle 2^k mögliche Antworten, die auf der Rückseite des Buches gewesen sein könnten und das beste finden. Wenn Sie Glück haben, dann wird der Link A in einem anderen Teilbaum als der Link B hinzugefügt. In diesem Fall können Sie die beiden Berechnungen für die beiden Möglichkeiten für den hinzugefügten Link A (oder B) auf die dynamischen Programmierungsberechnungen für den entsprechenden Teilbaum beschränken Sie haben die Arbeit nur verdoppelt statt vervierfacht. Im Allgemeinen, wenn Ihre k addierten Kanten in k verschiedenen Teilbäumen sind, die sich nicht gegenseitig stören, werden die Kosten mit 2 anstelle von 2^k multipliziert.