Minimaler äquivalenter Digraph in Bezug auf Quellen und Senken

Bei einer DAG (gerichteter azyklischer Graph) , mit den Quellen und Senken . Finden Sie eine DAG mit Quellen und Senken mit einer minimalen Anzahl von Kanten, so dass: $D$ $S$ $T$ $D'$ $S$ $T$

Für alle Paare gibt es einen Pfad von zu in , wenn und nur wenn es ein Pfad von ist zu in . $u \in S, v \in T$ $u$ $v$ $D$ $u$ $v$ $D'$

Eine Anwendung hierfür ist die Darstellung einer Mengenfamilie durch eine DAG. Für eine solche Darstellung ist jede Quelle eine Variable im Universum und jede Senke ist eine Menge in der Mengenfamilie, und ein Element u befindet sich genau dann in einer Menge S, wenn es einen Pfad vom Scheitelpunkt gibt, der u darstellt, zu dem Scheitelpunkt, der das darstellt setze S.

Ist dieses Problem bekannt? Gibt es einen Polynomalgorithmus für dieses Problem?

graph-theory graph-algorithms Martin Vatshelle
quelle

Ich denke, die Lösung muss ein Untergraph des Originaldiagramms sein, oder? Wenn ja, denke ich, dass dieses Problem die Set-Abdeckung durch die Standardreduktion erfasst, die zeigt, dass der gerichtete Steiner-Baum schwierig ist: Erstellen Sie einen Scheitelpunkt für jedes Element, einen Scheitelpunkt für jede Menge und eine gerichtete Kante (S, u), wenn die Menge S. enthält Element u. Fügen Sie dann allen festgelegten Scheitelpunkten einen neuen Scheitelpunkt und Kanten hinzu. Es gibt einen Pfad von diesem neuen Scheitelpunkt zu allen Senken (den Elementscheitelpunkten). Um alle zu erhalten, müssen wir die Mindestanzahl der festgelegten Scheitelpunkte auswählen, die alle Elemente abdecken.

Michael Lampis

Nein, im Allgemeinen würde ich sagen, dass es kein Untergraph des ursprünglichen Diagramms sein sollte. Quellen sind Elemente, und Sie benötigen ein Element genau dann, wenn ein Satz dieses Element enthält. Senken sind Mengen, und Sie können die Mengen, die Sie darstellen sollen, nicht löschen. Wenn Sie also von dem naiven Diagramm ausgehen, in dem alle Knoten entweder Senken oder Quellen sind, können Sie nur Scheitelpunkte hinzufügen und Kanten verschieben / löschen.

Martin Vatshelle

Das Problem scheint noch nicht genau definiert zu sein. Was sind die Einschränkungen für die Scheitelpunktmenge von ? Benötigen Sie, dass die Scheitelpunktmenge von dieselbe ist wie die Scheitelpunktmenge von ? Dass die Quellen und Senken von die gleichen sind wie die Quellen und Senken von ? Dass es eine Funktion die einen Scheitelpunkt von einem Scheitelpunkt von , und die Bedingung ist tatsächlich, dass es in einen Pfad von nach gibt, wenn es einen Pfad von bis in

D^{'}

$D'$

D^{'}

$D'$

D

$D$

D^{'}

$D'$

D

$D$

f : V_{D} \to V_{D^{'}}

$f:V_D \to V_{D'}$

D

$D$

D^{'}

$D'$

u

$u$

v

$v$

D

$D$

f (u)

$f(u)$

f (v)

$f(v)$

D^{'}

$D'$ ? Jeder kann zu einem etwas anderen Problem führen. Bearbeiten Sie die Frage zur Klärung?

Ich habe die Frage geklärt, in der Tat meine ich, dass die Quellen und Senken gleich sind. Ich denke, die Zuordnung ist ziemlich ähnlich. Die einzige Möglichkeit, zwei Senken demselben Knoten zuzuordnen, besteht darin, dass sie von derselben Quelle aus erreichbar sind, dh dieselbe Gruppe darstellen. Die einzige Möglichkeit, zwei Quellen demselben Knoten zuzuordnen, besteht darin, genau dieselben Senken zu erreichen. Ich denke also, nach einer einfachen Vorverarbeitung von D wären die Probleme gleichwertig.

Martin Vatshelle

Der Tag D ist für das Problem eigentlich irrelevant, nicht wahr? Sie können auch einen zweigeteilten Graphen zwischen S und T als Eingabe verwenden.

Emil Jeřábek 3.0

Nehmen wir an, dass nur Quellen und Senken enthält, da die Eingabe leicht in eine äquivalente solche Eingabe übersetzt werden kann. $D$

Beachten Sie dann, dass in jeder Lösung für jeder Scheitelpunkt einem Biclique im zugrunde liegenden ungerichteten Graphen von (dem Biclique zwischen allen Quellen, die in erreichen und allen Senken, die von in ). $D'$ $D$ $v$ $G$ $D$ $v$ $D'$ $v$ $D'$

Ich vermute, wenn optimal ist, dann enthält es einen Scheitelpunktschnitt, der 1: 1 einer optimalen Biclique-Bedeckung von . Dann wird jede minimale Scheitel-cut in entspricht einem optimalen biclique in abdecke . Da BICLIQUE COVER (auch bekannt als BIPARTITE DIMENSION) NP-vollständig ist, ist es unwahrscheinlich, dass Ihr Problem einen Polynom-Zeit-Algorithmus zulässt, es sei denn, meine Vermutung schlägt fehl. $D'$ $G$ $D'$ $G$

Beachten Sie, dass dieses Argument, selbst wenn meine Vermutung zutrifft, technisch gesehen keine NP-Härte Ihres Problems beweist, da die Reduktion keine Karp-, sondern eine Cook-Reduktion ist.

igel
quelle

Minimaler äquivalenter Digraph in Bezug auf Quellen und Senken

Antworten: