Finden der längsten Ketten von passenden Geräten

Question

Set a hat n Geräte. Set B hat M -Geräte. Einige Geräte in A sind mit den Geräten in B kompatibel, und einige Geräte in B sind mit denen in A kompatibel.

Ich möchte so viele kompatible Geräte, die wie möglich miteinander verbunden sind. (Es ist nicht erforderlich, dass das Gerät A in A und B in B gegenseitig kompatibel ist.)

Für Klarheit bearbeiten: Jedes Gerät kann mit 0, 1 oder 2 anderen Geräten verknüpft werden, aber nicht mit sich selbst.

Schließlich sollten alle Geräte (oder alle bis auf zwei, wenn sich die "Enden" nicht treffen) miteinander verbunden sein 1 auf 1. Es ist möglich, ein Gerät mit einem anderen Gerät zu verbinden. Aber kein Gerät in einem ist mit jedem Gerät in einem kompatibel (aber sie sind es verknüpfbar) und das gleiche gilt für Geräte in B.

If I have A = {a1,a2,a3}, B = {b1,b2,b3} and n=m=3

a1 is compatible with b1,b2
a2 is compatible with b1
a3 is compatible with b1
b1 is compatible with a1,a3
b2 is compatible with a1
b3 is compatible with a1

Dann der Diagramm g

a1 <-> b2 <-> a2 <-> b1 <-> a3 <-> b3 <-> a1

ist eine optimale Grafik.

G muss nicht zyklisch sein, aber es kann sein.

Gibt es clevere Möglichkeiten, dies zu nähern?

Answer 1

Ich glaube, dass dieses Problem durch eine Verringerung des nicht längsten Pfadproblems von undirected Längsträger np-hard ist, von dem bekannt ist Einführung in die Berechnungstheorie für Details darüber, warum).

Im Problem des ungerichteten längsten Pfades werden wir als Eingabe ein ungerichteter Diagramm g = (v, e) zusammen mit einem Paar Knoten u und v und einer Nummer k angegeben und möchten feststellen, ob es ein einfaches gibt (nein Der Knoten erscheint zweimal) Pfad von u zu v der Länge mindestens k. Wir können dies mit einer Polynomzeitreduzierung wie folgt in Ihr Problem umwandeln:

• Für jeden Knoten V_ich ∈ V, es gibt ein Gerät in a (nennen Sie es D._ich).
• Für jede Kante {v_ich, v_j} ∈ V, es gibt ein Gerät in B (nennen Sie es e_{Ich, j}).
• Für jeden Knoten V_ich und Edge {v_ich, v_j}, Gerät D._ich ist kompatibel mit dem Gerät e_{Ich, j}.

Diese Reduktion hat eine Polynomgröße, da die Gesamtzahl der generierten Geräte von Größe | V | ist + | E | und die Anzahl der Verbindungen beträgt 2 | e |. Darüber hinaus können wir sehen, dass es einen Weg der Länge k von V gibt_ich an v_j In Graph G IFF gibt es eine Kette von Geräten mit Länge 2k + 1 von D._ich zu d_j. Insbesondere wenn ((v)_ich1, v_ich2), (v_ich2, v_ich3), ..., (v_{ichK - 1}, v_ichk)) ist ein einfacher Weg von v_ich an v_j, dann die Kette d_ich1 → e_{ich1, ich2} → d_ich2 → e_{ich2, ich3} → d_ich3 → ... → e_{ichK - 1, ichk} → d_ichk und umgekehrt. Wir haben daher eine Polynomzeitverkleinerung vom ungerichteten längsten Weg zu Ihrem Problem wie folgt:

• Als Eingabe angegeben (g, v_ich, v_j, k) zum ungerichteten längsten Pfadproblem:
  • Konstruieren Sie die Mengen A und B wie oben, wobei die Kompatibilitäten c wie oben sind.
  • Überprüfen Sie, ob es eine Gerätekette von 2K + 1 aus D gibt_ich zu d_j.
  • Wenn ja, geben Sie "Ja" aus.
  • Wenn nicht, geben Sie "Nein" aus.

Diese Reduktion löst das nicht längste Pfadproblem in nicht-öfter Polynomzeiten mit einem Löser für Ihr Problem. Daher ist Ihr Problem NP-HART. Infolgedessen sollten Sie nicht erwarten, einen Polynom-Zeitalgorithmus für Ihr Problem zu finden. Eine genaue Antwort zu finden, ist wahrscheinlich die Exponentialzeit in Anspruch, es sei denn, P = NP.

Tut mir leid, eine negative Antwort zu geben, aber ich hoffe, das hilft!

Answer 2

Dies ist NP-HART, aber ich denke dieses Papier: Annäherung der maximalen Gewichtszyklusabdeckungen in gerichteten Graphen mit Gewicht Null und einem wird dir helfen.