Reduzierung des maximalen Durchflusses auf zweiteilige Anpassung?

9

Es gibt eine berühmte und elegante Reduktion vom Problem der maximalen zweiteiligen Anpassung zum Problem des maximalen Durchflusses: Wir erstellen ein Netzwerk mit einem Quellknoten , einem Endknoten und einem Knoten für jedes zuzuordnende Element und fügen dann geeignete Kanten hinzu.st

Es gibt sicherlich eine Möglichkeit, den maximalen Fluss auf die maximale zweiteilige Anpassung in der Polynomzeit zu reduzieren, da beide einzeln in der Polynomzeit gelöst werden können. Gibt es jedoch eine "schöne" Polynomzeitverkürzung vom maximalen Durchfluss (in allgemeinen Diagrammen) zum maximalen zweigliedrigen Matching?

templatetypedef
quelle
Fragen Sie nach dem Netzwerkfluss in einem zweigeteilten Diagramm oder in allgemeinen Diagrammen?
DW
Ich habe über den maximalen Durchfluss in allgemeinen Diagrammen nachgedacht.
Templatetypedef
1
Mehrfachzeitverkürzungen in P sind langweilig: Lösen Sie einfach die Instanz und wählen Sie eine von zwei fest codierten Instanzen aus. Ich weiß, dass Sie das nicht wollen, aber können Sie genauer angeben, was das ist?
Raphael
@ Raphael Der letzte Absatz meiner Frage spielte auf das an, was Sie erwähnt haben, da es eindeutig eine uninteressante Reduzierung in Anlehnung an das gibt, was Sie gesagt haben. Ich bin auf der Suche nach einer Reduzierung, die eher der Reduzierung von Matching zu Max-Flow entspricht - einer strukturellen Transformation, bei der die wesentlichen Eigenschaften erhalten bleiben. Denken Sie etwas in Anlehnung an die Reduktionen, die durchgeführt wurden, um die NP-Härte zu beweisen, und nicht an die triviale Reduktion von "Lösen Sie das Problem und geben Sie eine Instanz aus".
Templatetypedef
Sind Gadget-Reduzierungen nicht normalerweise linear? Das meine ich: Versuchen Sie, eine eingeschränktere Klasse zu finden, die uns daran hindert, zu "schummeln". (Es ist nicht klar, was "die wesentlichen Eigenschaften bewahren" bedeuten soll.)
Raphael

Antworten:

7

Seltsamerweise ist eine solche Reduzierung nicht bekannt. In einem kürzlich erschienenen Artikel zeigte Madry (FOCS 2013) jedoch, wie der maximale Durchfluss in Einheitenkapazitätsgraphen auf (logarithmisch viele Fälle von) maximale Übereinstimmung in zweigeteilten Graphen reduziert werden kann.b

Falls Sie mit dem Problem der maximalen Übereinstimmung nicht vertraut sind , ist dies eine Verallgemeinerung der Übereinstimmung, die wie folgt definiert ist: Die Eingabe ist ein Graph (in unserem Fall ein zweigeteilter Graph), und a Satz integraler Anforderungen für jeden Scheitelpunkt, wobei die Anforderung des Scheitelpunkts mit bezeichnet wird . Das Ziel ist es, einen größtmöglichen Satz von Kanten so dass kein Scheitelpunkt mehr als Kanten in , die auf . Es ist eine einfache Übung, die Reduktion von der zweiteiligen Anpassung auf die maximalen Flüsse zu verallgemeinern und eine ähnliche Reduktion von der zweiteiligenbG=(V,E)vbvSvbvSvb-matching zu maximalen Flüssen. (Eines der) überraschenden Ergebnisse von Madrys Artikel ist, dass diese Probleme in gewissem Sinne gleichwertig sind, was eine einfache Reduzierung ergibt, die den maximalen Durchfluss in Einheitenkapazitätsgraphen (im Allgemeinen Graphen, in denen die Summe der Kapazitäten verringert ist linear in der Anzahl der Kanten, ) zu einem passenden Problem in einem Graphen mit Knoten, Eckpunkten und Summe der Anforderungen.|u|1mbO(m)

Wenn Sie in Details interessiert sind, Abschnitt 3, bis zu Satz 3.1 und Abschnitt 4 (und den Nachweis der Richtigkeit in Anhang C) der ArXiv Version von Madry Papier sehen, hier . Wenn die Terminologie nicht selbstverständlich ist, finden Sie in Abschnitt 2.5 eine Zusammenfassung des Übereinstimmungsproblems. Beachten Sie, dass die Kapazität der Kante in der ursprünglichen Max-Flow-Instanz ist.buee

Dwajc
quelle
-2

Hier ist ein Versuch, Ihre Frage zu beantworten:

Konigs Satz über zweigliedrige Übereinstimmungen wurde unter Verwendung des Max-Flow-Min-Cut-Satzes bewiesen und folglich reduziert. Der Satz von Konig besagt Folgendes. Wenn G ein zweigeteilter Graph ist, dann ist max {| M | : M ist eine Übereinstimmung} = min {| C | : C ist ein Cover}. Beweis. Der Teil max {| M |} ≤ {| C |} ist trivial. Sei P und Q die Bipartitionsklasse von G. Wir addieren zwei Eckpunkte r und s zu G und die Bögen rp für jedes und qs für jedes und die direkte Kante pq von bis . Dies ist ein Digraph . Wir definieren Kapazitäten u (rp) = 1, u (pq) = , u (qs) = 1. Sei x ein realisierbarer Integralfluss x, dann x (e) = 0 oder 1, damit wir M = definieren können { : x (e) = 1}. M ist eine Übereinstimmung mit | M | =q Q p P q Q G *e E f x G * f x p q M G *( Q R ) | Q R |pPqQpPqQGeEfx . Als nächstes führt ein übereinstimmendes M in G zu einem möglichen integralen Fluss x in mit dem Flusswert = | M | wie folgt. Definiere x (pq) = 1, wenn , x (rp) = 1, wenn p auf eine Kante in M ​​fällt, x (qs) = 1, wenn q auf eine Kante in M ​​fällt, in allen anderen Fällen x (e) = 0. Somit entspricht eine maximale Größenanpassung M in G einem maximalen Fluss in , dessen Größe der eines minimalen Schnitts nach dem Max-Flow-Min-Cut-Theorem entspricht. Betrachten Sie einen minimalen r - s-Schnitt δ (R). Es hat eine endliche Kapazität, enthält also keinen Bogen pq. Dann fällt jede Kante von G mit einem Element von C = (P \ R) , dh C ist eine Abdeckung. Darüber hinaus ist u (C) = | P \ R | +und so ist C eine Abdeckung der Größe | M |.GfxpqMG(QR)|QR|

Ich meine, das ist alles meiner Meinung nach, was Sie in der Frage gestellt haben, und dies ist meine mögliche Antwort :).

Marcincuber
quelle
2
Beachten Sie, dass Sie hier LaTeX verwenden können, um die Mathematik besser lesbar zu setzen. Sehen Sie hier eine kurze Einführung.
DW
1
Können Sie klären, wie dies die Frage beantwortet? Konstruieren Sie einen Algorithmus zur Lösung des Max-Flow-Problems in allgemeinen Diagrammen unter Verwendung eines Algorithmus für die maximale zweiteilige Übereinstimmung? Wenn ja, wie lautet der Algorithmus? Es scheint, als ob Sie nur zeigen, wie Sie das Max-Flow-Problem für den Sonderfall von zweigeteilten Graphen in dem Sonderfall lösen können, in dem alle Kapazitäten 1 sind . Aber natürlich ist dieses Problem trivial gleichbedeutend mit maximaler Übereinstimmung, wie die Frage bereits erklärt, sodass ich nicht sehe, wie dies etwas Neues hinzufügt. Ich sehe auch nicht, wie Konigs Theorem- oder Vertex-Cover relevant sind.
DW
Die Reduzierung in diesem Fall ist der Schlüssel zur Beantwortung des Fragensatzes. Und ich glaube genau das, wonach @templatetypedef sucht. Ich glaube nicht, dass die Reduzierung der Polynomzeit vom Max-Flow (in allgemeinen Graphen) anders wäre. Ich werde noch einmal darüber nachdenken und vielleicht etwas extra hinzufügen, aber ich kann kaum verstehen, warum wir verschiedene Instanzen benötigen würden, um eine allgemeinere Reduzierung zu erreichen. Aber faire Punkte.
Marcincuber
Dies ist die Standard-Schulbuchreduktion VON zweiteiliger Anpassung auf maximalen Durchfluss. Die Frage lautet nach einer Reduzierung in die entgegengesetzte Richtung: VOM maximalen Durchfluss zum zweigliedrigen Matching.
JeffE