Beschneiden eines stark verbundenen Digraphen

10

Angesichts eines stark verbundenen Digraphen G mit gewichteten Kanten möchte ich Kanten identifizieren, die nachweislich nicht Teil eines minimalen stark verbundenen Teilgraphen (MSCS) von G sind.

Eine Methode zum Auffinden solcher Kanten ist ein modifizierter Floyd-Warshall-Algorithmus. Mit dem Floyd-Warshall-Algorithmus kann man identifizieren, welche Kanten niemals die beste Option sind, um vom Scheitelpunkt i nach j zu gelangen. Diese Knoten können nicht Teil eines MSCS sein, da es besser ist, sie durch zwei oder mehr andere Kanten zu ersetzen.

Die Floyd-Warshall-Schnitttechnik funktioniert recht gut, wenn die Kantengewichte erheblich variieren, aber sehr schlecht, wenn die Kantengewichte ähnlich, aber groß sind.

Kennen Sie effektive Schnittmethoden für große, ähnliche Kantengewichte? Entspricht dieses Problem einem häufigeren Problem, das ich nicht erkenne? Wurde diese Art des Beschneidens bereits in der Literatur untersucht?

ds.algorithms graph-theory graph-algorithms Nate
quelle
1
Ich kann diese Frage nicht beantworten, ohne die Literatur zu diesem Problem zu lesen. Haben Sie versucht, die Literatur selbst zu lesen? Können Sie zusammenfassen, was Sie gefunden haben?
Warren Schudy
1
Ein Großteil der Literatur befasst sich mit der Suche nach Approximationsalgorithmen, von denen einige recht gut sind. Die meisten davon arbeiten durch Zykluskontraktion mit guten Ergebnissen. Ich habe Probleme, Literatur zum Beschneiden statt zur Annäherung zu finden, weshalb ich mich frage, ob das Beschneidungsproblem eine Verallgemeinerung eines häufigeren Problems ist, über das ich nachlesen kann. Tipps, welche Literatur verwandt ist, sind willkommen.
Nate
1
Welche Funktion wird durch die Approximationsalgorithmen approximiert und wie unterscheidet sich diese vom Beschneiden?
Suresh Venkat
Die Näherungen nähern sich dem minimalen stark verbundenen Teilgraphen an. Wie gesagt, sie verwenden oft die Zykluskontraktion, um dies zu tun. Das Beschneiden über die Zykluskontraktion kann zu einem nicht optimalen Teilgraphen führen (daher eine Annäherung). Ich möchte so beschneiden, dass ich garantieren kann, dass ich keine Kanten beschnitten habe, die im MSCS angezeigt werden.
Nate

Antworten:

3

Wir nehmen an, dass Kantengewichte positive ganze Zahlen sind. Nennen Sie bei einem gerichteten Graphen G mit Kantengewichten eine Kante e redundant, wenn e nicht zu einem stark verbundenen übergreifenden Teilgraphen von G mit minimalem Gewicht gehört .

Wir behaupten, dass es keinen Polynom-Zeit-Algorithmus gibt, der immer eine redundante Kante in einem gegebenen gerichteten Graphen mit Kantengewichten findet, solange es eine gibt, es sei denn, P = NP. Etwas präziser:

Satz . Bei einem gerichteten Graphen G mit Kantengewichten ist es NP-schwer, eine redundante Kante in G zu finden oder zu erklären, dass G keine redundante Kante hat.

Beweis . Die wichtigste Beobachtung ist, dass Sie, wenn G einen eindeutigen stark verbundenen übergreifenden Teilgraphen mit minimalem Gewicht hat, diesen Teilgraphen berechnen können, indem Sie die redundanten Kanten einzeln entfernen. Daher bleibt zu zeigen, dass die Einzigartigkeit das Problem des stark verbundenen übergreifenden Teilgraphen mit minimalem Gewicht nicht einfacher macht, aber dies wird durch das nächste Lemma bewiesen. QED .

Lemma . Bei einem gerichteten Graphen G mit Kantengewichten ist es NP-schwierig, das Gewicht des stark verbundenen übergreifenden Teilgraphen von G mit minimalem Gewicht zu berechnen, selbst unter dem Versprechen, dass G einen einzigartigen stark verbundenen übergreifenden Teilgraphen mit minimalem Gewicht hat.

Beweis . Wie Sie wissen , ist das Problem ohne das Versprechen NP-schwer (selbst für den Einheitsgewichtsfall) durch eine Reduzierung des Hamiltonschen Schaltungsproblems. Wir reduzieren das Problem ohne das Versprechen auf das Problem mit dem Versprechen.

Sei G ein gerichteter Graph mit Kantengewichten. Beschriften Sie die Kanten von G mit e 0 , e 1 ,…, e m −1 , wobei m die Anzahl der Kanten in G ist . Sei w i das gegebene Gewicht der Kante e i . Das neue Gewicht w ' i = 2 m w i + 2 i . Dann ist es einfach zu überprüfen, ob G mit den neuen Gewichten einen eindeutigen stark verbundenen übergreifenden Teilgraphen mit minimalem Gewicht aufweist. Es ist auch leicht zu überprüfen, ob das MindestgewichtW eines stark verbundenen überspannenden Teilgraphen in G mit den ursprünglichen Gewichten kann aus dem Mindestgewicht W 'in G mit den neuen Gewichten als W = ⌊ W ' / 2 m ⌋ berechnet werden. QED .

Tsuyoshi Ito
quelle
2
Ja, offensichtlich ist es NP schwer, alle diese Kanten zu finden. Ich suche nicht nach all diesen Kanten, sondern nach einer Reihe von Kanten, von denen Sie feststellen können, dass sie in der Polynomzeit beschnitten werden können. Der Floyd-Warshall-Algorithmus kann verwendet werden, um einen solchen Satz von Kanten zu finden, wie oben beschrieben. Ich habe mich gefragt, ob es andere Möglichkeiten gibt, eine Teilmenge der entfernbaren Kanten in Polynomzeit zu identifizieren.
Nate