Algorithmus, um ein zweifaches Diagramm in Untergraphen aufzuteilen

Question

Ich suche nach einem Algorithmus, um ein zweiköpfiges Diagramm mit einer bestimmten Einschränkung in Untergraphen aufzuteilen. Ich bin nicht sicher, ob alle vorhandenen Algorithmen mein Problem lösen oder nicht.

Ich habe ein ungerechtigtes zweifaches Diagramm, in dem die Knoten Kunden sind ( $ C $ ) und Dienste ( $ s $ < / span>). Ich möchte dies in mehrere kleinere Untergraphen aufteilen, wobei die Anzahl der Dienste in jedem Untergraphen in einigen maximalen Anzahl $ N $ eingeschränkt wird. Leider ist die Suche nach getrennten Untergraphen nicht ausreichend, da die Graph-Verbindung zu hoch ist, also denke ich, dass ich doppelte Dienste brauchen muss.

förmlich möchte ich einen Satz von Untergraphen so, dass:

• Jeder Kunde $ C \ in C $ erscheint in genau einem Untergraphen
• Alle Kanten erscheinen in genau einem Untergraphen (derjenige, in dem ihr Kunde erscheint)
• Jeder Service $ s \ in S $ kann in einer beliebigen Anzahl von Untergraphen angezeigt werden (es ist in Ordnung, doppelte Dienste, um den Split doppelt zu werden)
• Jeder Untergraphen sollte höchstens $ N $ dienste (wobei $ n $ eine gegebene Konstante ist das ist garantiert größer als die höchste Anzahl von Diensten, die mit einem einzelnen Kunden verbunden sind)
• Die Untergraphen sollten so viele Kunden wie möglich aufweisen (ohne diese Einschränkung ist es allerdings lösbar, indem er jeden Kunden in einen eigenen Untergrund mit einer Kopie ihrer Dienste einfügt). Das kann eher heuristisch sein als formal bewährt.

Kann jemand einen Algorithmus dafür vorschlagen, dies zu tun? Die Anzahl der Knoten ist nicht riesig (rund 1000 Kunden, 100 Dienste, bei jedem Kunden, der mit 5 oder weniger Dienstleistungen verbindet), so dass rohe Kraftansätze oder solche mit schlechter Big-O-Skalierung geeignet sein können.

Answer 1

Es riecht, als könnte es np-hart sein.

Ein plausibierbarer Ansatz ist, einen Sat-Solver oder einen ILP-Solver zu verwenden.Angenommen, Sie entscheiden, dass Sie höchstens $ M $ Untergraphen haben möchten.Dann können Sie boolesche Variablen $ X_ {i, k}, y_ {j, k} $ angeben, an dass der Kunde $ i angezeigt wird$ geht in subgraph $ k $ und service $ j $ geht in den subgraph $ K $ .Sie können eine Reihe von Beschränkungen (Klauseln) basierend auf Ihren Anforderungen erhalten und dann den Sat-Solver oder den Sat-Solver bitten, eine realisierbare Lösung zu finden.Die schlimmste Laufzeit ist exponentiell.Dies könnte in Ihrer Situation gut genug funktionieren oder nicht gut genug funktionieren.