Die Äquivalenzbeziehungen decken das Problem ab (in der Graphentheorie)

Eine Äquivalenzbeziehung auf einer endlichen Scheitelpunktmenge kann durch einen ungerichteten Graphen dargestellt werden, der eine disjunkte Vereinigung von Cliquen darstellt. Die Scheitelpunktmenge repräsentiert die Elemente und eine Kante repräsentiert, dass zwei Elemente äquivalent sind.

Wenn ich einen Graphen und Graphen , sagen wir, dass durch abgedeckt ist wenn die Menge der Kanten von gleich der Vereinigung der Mengen der Kanten von . Die von müssen nicht disjunkt sein. Es ist zu beachten, dass jeder ungerichtete Graph durch eine endliche Anzahl von Äquivalenzrelationen abgedeckt werden kann (dh disjunkte Vereinigung von Cliquendiagrammen). $G$ $G_1,\dots,G_k$ $G$ $G_1,\dots,G_k$ $G$ $G_1,\dots,G_k$ $G_1,\dots,G_k$ $G$

Ich habe mehrere Fragen:

Was kann über die minimale Anzahl von Äquivalenzrelationen gesagt werden, die erforderlich sind, um einen Graphen abzudecken ? $G$
Wie können wir diese minimale Zahl berechnen?
Wie können wir eine explizite Mindestdeckung von berechnen , dh eine Menge von Äquivalenzbeziehungen, deren Größe minimal ist und die abdecken ? $G$ $G$
Hat dieses Problem andere Anwendungen als die Partitionslogik (das Duale der Logik von Teilmengen )?
Hat dieses Problem einen gut etablierten Namen?

Angesichts der verschiedenen Missverständnisse, auf die in den Kommentaren hingewiesen wird, sind hier einige Bilder aufgeführt, um diese Konzepte zu veranschaulichen. Wenn Sie eine Idee für eine leichter verständliche Terminologie haben (anstelle von "Deckung", "Äquivalenzbeziehung", "disjunkte Vereinigung von Cliquen" und "nicht unbedingt disjunkte" Vereinigung von Kantenmengen), können Sie mich dies gerne wissen lassen.

Hier ist ein Bild eines Graphen und eine Äquivalenzbeziehung, die ihn abdeckt: Grafik und eine Äquivalenzbeziehung, die sie abdeckt

Hier ist ein Bild eines Graphen und zwei Äquivalenzrelationen, die es abdecken: Graph und zwei Äquivalenzrelationen, die ihn abdecken
Es sollte ziemlich offensichtlich sein, dass mindestens zwei Äquivalenzrelationen erforderlich sind.

Hier ist ein Bild eines Graphen und drei Äquivalenzrelationen: Grafik und drei Äquivalenzrelationen, die sie abdecken
Es ist weniger offensichtlich, dass mindestens drei Äquivalenzrelationen erforderlich sind. Lemma 1.9 aus Dual der Logik von Teilmengen kann verwendet werden, um zu zeigen, dass dies wahr ist. Die Verallgemeinerung dieses Lemmas auf nand-Operationen mit mehr als zwei Eingaben war die Motivation für diese Frage.

algorithms graph-theory clique Thomas Klimpel
quelle

Es ist ein bekanntes NP-Complete- Problem. en.wikipedia.org/wiki/Clique_cover_problem

Gardenhead

@StephenBly Vielleicht ist es ein bekanntes Problem, aber der Wikipedia-Link, den Sie angegeben haben, hilft mir nicht wirklich. Der Artikel spricht über ein Vertex-Cover-Problem, aber die Frage hier betrifft ein Edge-Cover-Problem. Beachten Sie auch, dass eine Äquivalenzbeziehung keine Clique ist, sondern eine disjunkte Vereinigung von Cliquen.

Thomas Klimpel

Was meinst du damit, dass eine Äquivalenzbeziehung eine getrennte Vereinigung von Cliquen ist? Die Scheitelpunktmenge repräsentiert die Elemente und eine Kante repräsentiert, dass zwei Elemente äquivalent sind. Wenn dies nicht die Darstellung ist, die Sie verwenden, sollten Sie dies klarstellen.

Gardenhead

@StephenBly Ich denke nicht, dass es das gleiche Problem ist. Das Problem der Cliquenabdeckung fragt nach der Mindestanzahl von Cliquen, die die Eckpunkte des Diagramms abdecken. Hier suchen wir die Mindestanzahl von Äquivalenzbeziehungen, um die Kanten des Diagramms abzudecken. Es ist leicht zu erkennen, dass die Obergrenze in diesem Fall ist, da wir jeden Graphen von Eckpunkten in höchstens Übereinstimmungen unterteilen können.

n - 1

$n-1$

n

$n$

n - 1

$n-1$

Chao Xu

@YuvalFilmus Die Frage fragt nach der geringsten Anzahl von Äquivalenzrelationen, deren Vereinigung genau die Kantenrelation des gegebenen Graphen ist, nicht deren Vereinigung lediglich den gegebenen Graphen enthält.

David Richerby

Antworten:

Das Problem ist als das Äquivalenzdeckungsproblem in der Graphentheorie bekannt. Es wird durch die Clique-Deckungsnummer (die minimale Sammlung von Cliquen, sodass sich jede Kante des Diagramms in mindestens einer Clique befindet) begrenzt. Es gibt viele ähnliche Probleme und Definitionen; man muss hier sehr vorsichtig sein. Diese beiden Zahlen werden mit bzw. bezeichnet. $\text{eq}(G)$ $\text{cc}(G)$

Es gibt spezielle Diagrammklassen, bei denen der genaue Wert oder eine gute Obergrenze für jede Zahl bekannt ist. Im Allgemeinen werden nach meinem besten Wissen die besten Grenzen von Alon angegeben [1]:

\log_{2} n - \log_{2} d \leq eq (G) \leq cc (G) \leq 2 e^{2} (Δ + 1)^{2} \ln n,

$\log_2 n - \log_2 d \leq \text{eq}(G) \leq \text{cc}(G) \leq 2e^2 (\Delta+1)^2 \ln n,$

wo ist der maximale Grad von . Übrigens ist eine Bedeckung mit Dreiecken und Kanten immer möglich (vgl. Mantels Theorem), und dies ist auch algorithmisch leicht zu finden. $\Delta$ $G$ $\lceil n^2/4 \rceil$

Es ist nicht überraschend, dass die Berechnung einer der beiden Zahlen vollständig ist. Auch für geteilte Diagramme, Berechnen ist -hard (kann aber auf eine additive Konstante 1 angenähert werden) , wie in [2] gezeigt. Es ist auch schwierig, für Graphen zu berechnen, in denen keine zwei Dreiecke einen gemeinsamen Scheitelpunkt haben [3]. $\sf NP$ $\text{eq}(G)$ $\sf NP$

[1] Alon, Noga. "Diagramme durch die minimale Anzahl von Äquivalenzrelationen abdecken." Combinatorica 6.3 (1986): 201 & ndash; 206.

[2] Blokhuis, Aart und Ton Kloks. "Über die Äquivalenz, die die Anzahl der Splitgraphen abdeckt." Information Processing Letters 54.5 (1995): 301-304.

[3] Kučera, Luděk, Jaroslav Nešetřil und Aleš Pultr. "Komplexität der Dimension drei und einige verwandte Kantenbedeckungseigenschaften von Graphen." Theoretical Computer Science 11.1 (1980): 93 & ndash; 106.

Juho
quelle

Korollar 1.3 aus [1] ist genau das, was ich brauchte (in der Version, die für die Ergänzungen eines Pfades gilt). Jetzt habe ich keine Entschuldigung mehr dafür, das Papier nicht über die allgemeine Implikation "(A, B, C, ...) implizieren (Z, Y, X, ...)" (die Folge aus der Folgerechnung) in der Partition zu schreiben Logik und ähnliche nicht klassische Logik. Aber ich denke, ich werde es noch mindestens ein halbes Jahr nicht schreiben. Und vielleicht finde ich in der Zwischenzeit sogar eine neue Ausrede.

Thomas Klimpel

@ ThomasKlimpel Das ist großartig! (Nicht die Tatsache, dass Sie eine neue Ausrede finden könnten, aber dass dies hilfreich war :-))

Juho

Obwohl ich den Namen für ein solches Problem nicht kenne, kann ich zeigen, dass dieses Problem NP-schwer ist.

Für ein dreieckfreies Diagramm müssen alle Äquivalenzklassen übereinstimmen. Die minimale Anzahl von Äquivalenzklassen, die den Graphen abdecken, entspricht dem chromatischen Index des Graphen.

Gemäß diesem Artikel ist das Ermitteln des chromatischen Index für einen dreieckfreien Graphen NP-vollständig.

Chao Xu
quelle