Dominierende Menge - Dominating set

Informationen zu Dominator in Kontrollflussdiagrammen finden Sie unter Dominator (Graphentheorie) .
Image
Dominierende Mengen (rote Ecken).

In der Graphentheorie ist eine dominierende Menge für einen Graphen G  = ( V ,  E ) eine Teilmenge D von V, so dass jeder Knoten, der nicht in D ist, zu mindestens einem Mitglied von D benachbart ist . Die Dominanzzahl γ( G ) ist die Anzahl der Knoten in einer kleinsten dominierenden Menge für  G .

Das dominierende Mengenproblem betrifft das Testen, ob γ( G ) ≤  K für einen gegebenen Graphen G und Eingabe K ; es ist ein klassisches NP-vollständiges Entscheidungsproblem in der Berechnungskomplexitätstheorie . Daher wird angenommen, dass es möglicherweise keinen effizienten Algorithmus gibt , der eine kleinste dominierende Menge für alle Graphen findet, obwohl es effiziente Approximationsalgorithmen sowie sowohl effiziente als auch exakte Algorithmen für bestimmte Graphenklassen gibt.

Die Abbildungen (a)–(c) auf der rechten Seite zeigen drei Beispiele für dominierende Mengen für einen Graphen. In jedem Beispiel grenzt jeder weiße Scheitel an mindestens einen roten Scheitel, und es wird gesagt, dass der weiße Scheitel von dem roten Scheitel dominiert wird. Die Dominanzzahl dieses Graphen ist 2: Die Beispiele (b) und (c) zeigen, dass es eine dominierende Menge mit 2 Knoten gibt, und es kann überprüft werden, dass es für diesen Graphen keine dominierende Menge mit nur 1 Knoten gibt.

Geschichte

Das Herrschaftsproblem wurde ab den 1950er Jahren untersucht, aber Mitte der 1970er Jahre nahm die Forschungsrate zur Herrschaft deutlich zu. Im Jahr 1972 Richard Karp bewies das Set Cover Problem seiner NP-vollständig . Dies hatte unmittelbare Auswirkungen auf das Problem der dominierenden Menge, da es zwischen den beiden Problemen geradlinige Vertex-zu-Set-Bijektionen und Kanten zu nicht-disjunkten Schnittpunkten gibt. Dies bewies, dass auch das dominierende Mengenproblem NP-vollständig ist .

Dominierende Sets sind in mehreren Bereichen von praktischem Interesse. In drahtlosen Netzwerken werden dominierende Sets verwendet, um effiziente Routen innerhalb von Ad-hoc-Mobilnetzen zu finden. Sie wurden auch bei der Dokumentenzusammenfassung und beim Entwurf sicherer Systeme für Stromnetze verwendet.

Dominierende und unabhängige Sets

Dominierende Mengen sind eng mit unabhängigen Mengen verwandt : Eine unabhängige Menge ist genau dann auch eine dominierende Menge, wenn sie eine maximale unabhängige Menge ist , also ist jede maximale unabhängige Menge in einem Graphen notwendigerweise auch eine minimale dominierende Menge.

Dominanz durch unabhängige Sets

Eine dominierende Menge kann eine unabhängige Menge sein oder nicht. Zum Beispiel zeigen die Abbildungen (a) und (b) oben unabhängige dominierende Mengen, während Abbildung (c) eine dominierende Menge darstellt, die keine unabhängige Menge ist.

Die unabhängige Dominanzzahl i ( G ) eines Graphen G ist die Größe der kleinsten dominierenden Menge, die eine unabhängige Menge ist. Äquivalent ist es die Größe der kleinsten maximalen unabhängigen Menge. Das Minimum in i ( G ) wird über weniger Elemente genommen (es werden nur die unabhängigen Mengen betrachtet), also ( G ) ≤  i ( G ) für alle Graphen G .

Die Ungleichung kann streng sein - es gibt Graphen G, für die γ( G ) <  i ( G ) ist. Sei beispielsweise G der Doppelsterngraph bestehend aus den Knoten x 1 , ..., x p , a , b , y 1 , ..., y q , wobei p , q > 1 ist. Die Kanten von G sind definiert wie folgt: jedes x i grenzt an a an , a grenzt an b an und b grenzt an jedes b j . Dann ist γ( G ) = 2, da { a , b } eine kleinste dominierende Menge ist. Wenn p  ≤  q ist , dann ist i ( G ) = p + 1, da { x 1 , ..., x p , b} eine kleinste dominierende Menge ist, die auch unabhängig ist (es ist eine kleinste maximale unabhängige Menge).

Es gibt Graphfamilien, in denen γ( G ) =  i ( G ), dh jede minimale maximale unabhängige Menge ist eine minimale dominierende Menge. Beispielsweise gilt γ( G ) =  i ( G ), falls G ein klauenfreier Graph ist .

Ein Graph G heißt herrschaftsperfekter Graph, wenn γ( H ) =  i ( H ) in jedem induzierten Teilgraphen H von G . Da ein induzierter Teilgraph eines klauenfreien Graphen klauenfrei ist, folgt daraus, dass jeder klauenfreie Graph auch dominanzperfekt ist.

Für jeden Graphen G ist sein Liniengraph L ( G ) klauenfrei, und daher ist eine minimale maximale unabhängige Menge in L ( G ) auch eine minimale dominierende Menge in L ( G ). Eine unabhängige Menge in L ( G ) entspricht einer passenden in G , und eine dominierende Menge in L ( G ) einem Rand dominierende Menge in G . Daher hat ein minimales maximales Matching die gleiche Größe wie ein minimaler kantendominierender Satz.

Dominanz von unabhängigen Sätzen

Die Unabhängigkeitsdominanzzahl iγ ( G ) eines Graphen G ist das Maximum über alle unabhängigen Mengen A von G der kleinsten Menge, die A dominiert . Das Dominieren von Teilmengen von Knoten erfordert potentiell weniger Knoten als das Dominieren aller Knoten, also ist iγ( G ) ≤  γ ( G ) für alle Graphen G .

Die Ungleichung kann streng sein - es gibt Graphen G für die iγ( G ) <  γ ( G ) ist. Zum Beispiel sei G für eine ganze Zahl n ein Graph, in dem die Knoten die Zeilen und Spalten eines n- mal- n- Bretts sind, und zwei solcher Knoten sind genau dann verbunden, wenn sie sich schneiden. Die einzigen unabhängigen Mengen sind Mengen von nur Zeilen oder Mengen von nur Spalten, und jede von ihnen kann von einem einzelnen Knoten (einer Spalte oder einer Reihe) dominiert werden, also ist iγ ( G )=1. Allerdings dominieren alle Vertices wir mindestens eine Zeile und eine Spalte benötigen, so γ ( G ) = 2. Darüber hinaus kann das Verhältnis zwischen γ ( G )/ iγ ( G ) beliebig groß sein. Wenn beispielsweise die Ecken von G alle Teilmengen von Quadraten eines n- mal- n- Bretts sind, dann ist immer noch iγ ( G )=1, aber γ ( G )= n .

Die bi-unabhängige Dominanzzahl iγi ( G ) eines Graphen G ist das Maximum über alle unabhängigen Mengen A von G der kleinsten unabhängigen Menge, die A dominiert . Für jeden Graphen G gelten die folgenden Beziehungen :

Algorithmen und Rechenkomplexität

Das Mengenüberdeckungsproblem ist ein bekanntes NP-schweres Problem – die Entscheidungsversion der Mengenüberdeckung war eines von Karps 21 NP-vollständigen Problemen . Es gibt ein Paar von Polynomialzeit- L-Reduktionen zwischen dem minimalen dominierenden Mengenproblem und dem Mengenüberdeckungsproblem . Diese Reduktionen ( siehe unten ) zeigen, dass ein effizienter Algorithmus für das Problem der minimalen dominierenden Menge einen effizienten Algorithmus für das Problem der Mengenüberdeckung liefern würde und umgekehrt. Darüber hinaus bewahren die Reduktionen das Approximationsverhältnis : für jedes α würde ein α-Approximationsalgorithmus mit polynomialer Zeit für minimal dominierende Mengen einen α-Approximationsalgorithmus mit polynomialer Zeit für das Mengenüberdeckungsproblem bereitstellen und umgekehrt. Beide Probleme sind nämlich Log-APX-komplett .

Die Näherungsfähigkeit der Mengenüberdeckung ist ebenfalls gut verstanden: Ein logarithmischer Näherungsfaktor kann mit einem einfachen Greedy-Algorithmus gefunden werden , und das Finden eines sublogarithmischen Näherungsfaktors ist NP-schwer. Genauer gesagt liefert der Greedy-Algorithmus einen Faktor 1 + log | V | Approximation einer minimalen dominierenden Menge, und kein Polynomialzeitalgorithmus kann einen besseren Approximationsfaktor als c  log | . erreichen V | für einige c  > 0 außer P = NP .

L-Reduzierungen

Die folgenden beiden Reduktionen zeigen, dass das Problem der minimalen dominierenden Menge und das Problem der Mengenüberdeckung unter L-Reduktionen äquivalent sind : Wenn eine Instanz eines Problems gegeben ist, können wir eine äquivalente Instanz des anderen Problems konstruieren.

Von dominierendem Set zu Set-Deckung. Konstruieren Sie für einen gegebenen Graphen G  = ( V ,  E ) mit V  = {1, 2, ...,  n } eine Mengenüberdeckungsinstanz ( U ,  S ) wie folgt: Das Universum U ist V , und die Familie der Teilmengen ist S  = { S 1 , S 2 , ..., S n } so dass S v aus der Ecke v und allen zu v benachbarten Ecken in G besteht .

Ist nun D eine dominierende Menge für G , dann ist C  = { S v  :  v  ∈  D } eine zulässige Lösung des Mengenüberdeckungsproblems, mit | C | = | D |. Umgekehrt, wenn C  = { S v  :  v  ∈ D } eine zulässige Lösung des Mengenüberdeckungsproblems  ist, dann ist D eine dominierende Menge für G mit | D | = | C |.

Daher ist die Größe einer minimalen dominierenden Menge für G gleich der Größe einer minimalen Mengenabdeckung für ( U ,  S ). Darüber hinaus gibt es einen einfachen Algorithmus, der eine dominierende Menge auf eine gleich große Mengenabdeckung abbildet und umgekehrt. Insbesondere stellt ein effizienter α-Approximationsalgorithmus zur Mengenüberdeckung einen effizienten α-Approximationsalgorithmus für minimal dominierende Mengen bereit.

Dominating-set-2.svg
Für den rechts gezeigten Graphen G konstruieren wir beispielsweise eine Mengenüberdeckungsinstanz mit dem Universum U  = {1, 2, ..., 6} und den Teilmengen S 1  = {1, 2, 5}, S 2  = {1, 2, 3, 5}, S 3  = {2, 3, 4, 6}, S 4  = {3, 4}, S 5  = {1, 2, 5, 6} und S 6  = {3, 5, 6}. In diesem Beispiel ist D  = {3, 5} eine dominierende Menge für G – dies entspricht der Mengenüberdeckung C  = { S 3 ,  S 5 }. Zum Beispiel wird die Ecke 4  V von der Ecke 3 ∈ D dominiert  und das Element 4 ∈  U ist in der Menge S 3  ∈  C enthalten .

Von der Setabdeckung zum dominierenden Set. Sei ( S ,  U ) eine Instanz des Mengenüberdeckungsproblems mit dem Universum U und der Familie der Teilmengen S  = { S i  :  i  ∈  I }; wir nehmen an, dass U und die Indexmenge I disjunkt sind. Konstruieren Sie einen Graphen G  = ( V ,  E ) wie folgt: die Menge der Knoten ist V  =  I  ∪  U , es gibt eine Kante { i ,  j } ∈  E zwischen jedem Paar i ,  j  ∈  I , und es gibt auch eine Kante { i ,  u } für jedes i  ∈  I und u  ∈  S i . Das heißt, G ist ein geteilter Graph : I ist eine Clique und U ist eine unabhängige Menge .

Ist nun C  = { S i  :  i  ∈  D } eine zulässige Lösung des Mengenüberdeckungsproblems für eine Teilmenge D  ⊆  I , dann ist D eine dominierende Menge für G mit | D | = | C |: Erstens, für jedes u  ∈  U gibt es ein i  ∈  D , so dass u  ∈  S i und durch die Konstruktion, u und i in benachbarten G ; daher wird u von i dominiert . Zweitens, da D nicht leer sein muss, grenzt jedes i  ∈  I an einen Knoten in D an .

Sei umgekehrt D eine dominierende Menge für G . Dann ist es möglich, eine andere dominierende Menge X zu konstruieren, so dass | X | | D | und X  ⊆  I :  Ersetze einfach jedes u  ∈  D ∩  U durch einen Nachbarn i  ∈  I von u . Dann ist C  = { S i  :  i  ∈  X } eine zulässige Lösung des Mengenüberdeckungsproblems, mit | C | = | X | | D |.

Dominating-Set-Reduction.svg
Die Abbildung rechts zeigt die Konstruktion für U  = { a ,  b ,  c ,  d ,  e }, I  = {1, 2, 3, 4}, S 1  = { a ,  b ,  c }, S 2  = { a ,  b }, S 3  = { b ,  c ,  d } und S 4  = { c ,  d ,  e }.
In diesem Beispiel ist C  = { S 1 ,  S 4 } eine Mengenüberdeckung; dies entspricht der dominierenden Menge D  = {1, 4}.
D  = { a , 3, 4} ist eine weitere dominierende Menge für den Graphen G . Gegeben D können wir eine dominierende Menge X  = {1, 3, 4} konstruieren , die nicht größer als D ist und eine Teilmenge von I ist . Die dominierende Menge X entspricht der Mengenabdeckung C  = { S 1 ,  S 3 ,  S 4 }.

Sonderfälle

Wenn der Graph den maximalen Grad Δ hat, dann findet der Greedy-Approximationsalgorithmus eine O (log Δ)-Approximation einer minimalen dominierenden Menge. Sei d g die Kardinalität der dominierenden Menge, die unter Verwendung der gierigen Näherung erhalten wird, dann gilt die folgende Beziehung , wobei N die Anzahl der Knoten und M die Anzahl der Kanten in einem gegebenen ungerichteten Graphen ist. Für feste Δ qualifiziert dies als dominierendes Set für die APX- Mitgliedschaft; Tatsächlich ist es APX-vollständig.

Das Problem lässt ein Polynomial-Time-Approximation-Schema (PTAS) für Spezialfälle wie Einheitsscheibengraphen und planare Graphen zu . Eine minimale dominierende Menge findet sich in linearer Zeit in seriell-parallelen Graphen .

Genaue Algorithmen

Eine minimale dominierende Menge eines n- Scheitelpunkt-Graphen kann in der Zeit O (2 n n ) gefunden werden, indem alle Scheitelpunkt-Untermengen untersucht werden. Fomin, Grandoni & Kratsch (2009) zeigen, wie man eine minimale dominierende Menge in Zeit O (1.5137 n ) und Exponentialraum und in Zeit O (1.5264 n ) und Polynomraum findet. Ein schnellerer Algorithmus mit O (1.5048 n ) Zeit wurde von van Rooij, Nederlof & van Dijk (2009) gefunden , die auch zeigen, dass die Anzahl der minimalen dominierenden Mengen in dieser Zeit berechnet werden kann. Die Anzahl der minimalen dominierenden Mengen beträgt höchstens 1.7159 n und alle diese Mengen können in der Zeit O (1.7159 n ) aufgelistet werden .

Parametrisierte Komplexität

Das Finden einer dominierenden Menge der Größe k spielt eine zentrale Rolle in der Theorie der parametrisierten Komplexität. Es ist das bekannteste Problem für die Klasse W[2] und wird in vielen Reduktionen verwendet, um die Unlösbarkeit anderer Probleme zu zeigen. Insbesondere ist das Problem nicht mit festen Parametern behandelbar in dem Sinne, dass kein Algorithmus mit Laufzeit f ( k ) n O(1) für irgendeine Funktion f existiert, es sei denn, die W-Hierarchie kollabiert auf FPT=W[2].

Wenn der Eingabegraph andererseits planar ist, bleibt das Problem NP-schwer, aber ein Algorithmus mit festen Parametern ist bekannt. Tatsächlich hat das Problem , einen Kern mit einer Größe linear in k , und Laufzeiten, die in exponentiell √ k und kubischem in n durch Anwendung erhalten werden kann , die dynamische Programmierung zu einer Verzweigungs Zersetzung des Kernels. Allgemeiner ausgedrückt sind das Problem der dominierenden Menge und viele Varianten des Problems mit festen Parametern bearbeitbar, wenn sie sowohl durch die Größe der dominierenden Menge als auch durch die Größe des kleinsten verbotenen vollständigen zweiteiligen Teilgraphen parametrisiert werden ; Das heißt, das Problem ist FPT auf biclique-freien Graphen , einer sehr allgemeinen Klasse von dünn besetzten Graphen, die die planaren Graphen einschließt.

Die komplementäre Menge zu einer dominierenden Menge, ein Nichtblocker , kann durch einen Algorithmus mit festen Parametern in jedem Graphen gefunden werden.

Varianten

Eine wichtige Unterklasse der dominierenden Mengen ist die Klasse der zusammenhängenden dominierenden Mengen . Wenn S eine zusammenhängende dominierende Menge ist, kann man einen aufspannenden Baum von G bilden, in dem S die Menge der Nicht-Blatt-Eckpunkte des Baums bildet; Umgekehrt, wenn T ein aufspannender Baum in einem Graphen mit mehr als zwei Knoten ist, bilden die Nicht-Blatt-Knoten von T eine zusammenhängende dominierende Menge. Daher ist das Auffinden minimaler zusammenhängender dominierender Mengen gleichbedeutend mit dem Auffinden von aufspannenden Bäumen mit der maximal möglichen Anzahl von Blättern.

Eine total dominierende Menge ist eine Menge von Scheitelpunkten, bei der alle Scheitelpunkte im Graphen (einschließlich der Scheitelpunkte in der dominierenden Menge selbst) einen Nachbarn in der dominierenden Menge haben. (c) oben zeigt eine dominierende Menge, die eine zusammenhängende dominierende Menge und eine insgesamt dominierende Menge ist; die Beispiele in den Abbildungen (a) und (b) sind keines von beiden.

Eine k- Tupel dominierende Menge ist eine Menge von Scheitelpunkten, so dass jeder Scheitelpunkt im Graphen mindestens k Nachbarn in der Menge hat. Eine (1+log n)-Approximation einer minimalen k- Tupel dominierenden Menge kann in polynomieller Zeit gefunden werden. In ähnlicher Weise ist eine k- dominante Menge eine Menge von Scheitelpunkten, so dass jeder Scheitelpunkt, der nicht in der Menge ist, mindestens k Nachbarn in der Menge hat. Während jeder Graph eine k- dominante Menge zulässt, haben nur Graphen mit minimalem Grad k  − 1 eine k- Tupel-dominante Menge. Doch selbst wenn die Graph k-Tupel zugibt Satz dominiert, ein Minimum k - tupel Satz dominiert fast werden kann k als Mindest mal so groß k Satz für die gleiche grafische Darstellung -dominating; Eine (1.7 + log Δ)-Approximation einer minimal k -dominierenden Menge findet sich auch in polynomieller Zeit.

Eine sterndominierende Menge ist eine Teilmenge D von V, so dass für jede Ecke v in V der Stern von v (die Menge von Kanten neben v ) den Stern einer Ecke in D schneidet . Wenn G isolierte Ecken hat, hat es natürlich keine sterndominierenden Mengen (da der Stern der isolierten Ecken leer ist). Wenn G keine isolierten Knoten hat, dann ist jede dominierende Menge eine sterndominierende Menge und umgekehrt. Der Unterschied zwischen Star-Dominanz und üblicher Dominanz ist substanzieller, wenn ihre Bruchvarianten betrachtet werden.

Eine domatische Partition ist eine Partition der Knoten in disjunkte dominierende Mengen. Die domatic-Nummer ist die maximale Größe einer domatic-Partition.

Eine ewige dominierende Menge ist eine dynamische Version der Herrschaft, bei der ein Knoten v in der dominierenden Menge D gewählt und durch einen Nachbarn u ersetzt wird ( u ist nicht in D ), sodass das modifizierte D auch eine dominierende Menge ist und dieser Prozess wiederholt werden kann über jede unendliche Folge von Wahlmöglichkeiten von Knoten  v .

Siehe auch

Anmerkungen

Verweise

Weiterlesen