---

Geschrieben von Damasus am 02.08.2013 um 10:07:

  3D-Matching und Max-Flow

Guten morgen zusammen,

ich interessiere mich, ohne eine relavanten Hintergrund, für folgendes Problem. Es geht um die Probleme 3D-Matching (NP-vollständig) und Max-Flow (liegt in P).
Angenommen ich habe nun ein 3D-Matching Problem vor mir liegen (Mengen X, Y, Z). Was ist der Unterschied zu Max-Flow? Könnte ich nicht einfach eine Quelle und Senke einfügen. Quelle mit den Elementen aus X verbinden und die Senke mit Elementen aus Z. Als Kapazität wähle ich 1 und die Elemente aus Y verdoppele ich und füge eine Kante mit Kapazität 1 dazu, d.h. ich garantiere damit, dass nur eine Einheit über diesen Knoten geht (Stichwort: Knotenkapazität). Nun bestimme ich den maximalen Fluss.

Irgendwo ist natürlich ein Denkfehler, aber wo? Oder ist P=NP? ;-p

---

Geschrieben von ed209 am 03.08.2013 um 16:01:

 

Hi Damasus,

Bei solchen Problemen ist es immer gut, die Definitionen mit anzugeben, oder zu verlinken. Ich bezieh mich mal auf die Definitionen der englischen Wikipedia: https://en.wikipedia.org/wiki/3-dimensional_matching und https://en.wikipedia.org/wiki/Maximum_flow_problem

Um Dich zu widerlegen brauchen wir nur ein einziges Gegenbeispiel bei dem dein Problem und das Problem auf das du abbildest nicht dasselbe Ergebnis hervorbringen. Das hier ist das simpelste 3D-Matching Problem auf das ich gekommen bin.

X = (x0, x1), Y = (y0, y1) und Z = (z0, z1)

T = { (x0, y0, z0), (x0, y1, z1), (x1, y1, z0) }

Da jeweils zwei Tripel immer eine Überschneidung haben, enthält das beste Matching nur ein Tripel.

Wenn wir das jetzt nach deiner Methode (wenn ich sie richtig verstanden habe) auf ein Maxflow problem abbilde, dann ist der Maxflow 2

Gruß,
ED

---

Geschrieben von Damasus am 04.08.2013 um 12:03:

 

Das ist natürlich absolut richtig. Vielen Dank dafür schonmal.

Siehst du eine Verbindung zwischen den zwei Problemen? Ist das 3D-Matching in irgendeiner Form eine Verallgemeinerung des Max-Flow Problems oder sind das doch zwei ganz unterschiedliche Probleme?

---

Geschrieben von ed209 am 04.08.2013 um 14:58:

 

Hi

Wenn man ein bisschen in der Wikipedia schnüffel ist das 3D Matching eine erweiterung vom Bipartite Graph Matching problem, das in der tat auf Maxflow abgebildet werden kann.

https://en.wikipedia.org/wiki/Bipartite_matching#Maximum_matchings_in_bipartite_graphs

Aber im Endeffekt bleibt 3D Matching NP-Schwer und Maxflow liegt in P, da wirst du nicht so schnell auf eine Lösung kommen. (Ja ich hab es in meiner Jugend auch probiert zu zeigen daß P = NP oder das Gegenteil, aber es hat nie egklappt )

ED