Dominierender Satz

Für Dominator in Kontrollflussgraphen siehe Dominator (Graphentheorie).
Beispiel: Jeder weiße Scheitelpunkt befindet sich an mindestens einem roten Scheitelpunkt und soll es sein dominiert vom roten Scheitelpunkt. Die Herrschaftsnummer γ Von diesem Diagramm lautet 2: (b) und (c) zeigen, dass es einen dominierenden Satz mit 2 Scheitelpunkten gibt, und es kann überprüft werden, dass es für dieses Diagramm keinen dominierenden Satz mit nur 1 Scheitelpunkt gibt.

Im Graphentheorie, a dominierender Satz Für ein Graph G = (V, E) ist ein Teilmenge D des Eckpunkte V so dass jeder Scheitelpunkt nicht in D ist neben mindestens einem Mitglied von angrenzend D. Das Herrschaftsnummer γ (G) ist die Anzahl der Eckpunkte in einem kleinsten dominierenden Satz für G.

Das Dominierender Satzproblem Bedenken, ob γ (G) ≤ K Für eine bestimmte Grafik G und Eingabe K; Es ist klassisch NP-Complete Entscheidungsproblem in Computerkomplexitätstheorie.[1] Daher wird angenommen, dass es keine geben kann Effizienter Algorithmus Das findet einen kleinsten dominierenden Satz für alle Grafiken, obwohl es effizient gibt Näherungsalgorithmensowie sowohl effiziente als auch genaue Algorithmen für bestimmte Grafikklassen.

Geschichte

Das Herrschaftsproblem wurde ab den 1950er Jahren untersucht, aber die Forschungsrate der Herrschaft mitte Mitte der 1970er Jahre stieg signifikant an. 1972,, Richard Karp bewiesen das Stellen Sie das Cover -Problem fest sein NP-Complete. Dies hatte unmittelbare Auswirkungen auf das dominierende Problem, da es einen einfachen Scheitelpunkt gibt, der zwischen den beiden Problemen auf Nicht-Disjoint-Intersection-Bijiziteen festgelegt ist. Dies bewies das dominierende Problem mit dem dominierenden Problem NP-Complete auch.[2]

Dominierende Sets sind in mehreren Bereichen von praktischem Interesse. Im Drahtlose Vernetzung, dominierende Sets werden verwendet, um effiziente Routen in Ad-hoc-Mobilfunknetzen zu finden. Sie wurden auch in der Zusammenfassung der Dokumente und zur Gestaltung sicherer Systeme für elektrische Netze verwendet.

Dominierende und unabhängige Sätze

Die dominierenden Sets sind eng mit dem verwandt mit unabhängige Sets: Ein unabhängiger Satz ist auch ein dominierender Satz, wenn es nur ist, wenn es a ist Maximaler unabhängiger SatzDaher ist ein maximaler unabhängiger Satz in einem Diagramm notwendigerweise auch ein minimaler dominierender Satz.

Herrschaft durch unabhängige Sets

Ein dominierender Satz kann ein unabhängiger Satz sein oder nicht. Beispielsweise zeigen die oben genannten Abbildungen (a) und (b) unabhängige dominierende Sätze, während Abbildung (c) einen dominierenden Satz zeigt, der kein unabhängiger Satz ist.

Das unabhängige Herrschaftsnummer i(G) einer Grafik G ist die Größe des kleinsten dominierenden Satzes, der ein unabhängiger Satz ist. Äquivalent ist es die Größe des kleinsten maximalen unabhängigen Satzes. Das Minimum in i(G) wird über weniger Elemente übernommen (nur die unabhängigen Sets werden berücksichtigt), also γ(G) ≤ i(G) Für alle Grafiken G.

Die Ungleichheit kann streng sein - es gibt Grafiken G für welche γ(G) < i(G). Zum Beispiel lassen G sei der Doppelsterndiagramm bestehend aus Scheitelpunkten , wo p, q > 1. Die Kanten von G werden wie folgt definiert: jeder xi ist neben a, a ist neben b, und b ist neben jedem angrenzend yj. Dann γ (G) = 2 seit {a, b} ist ein kleinster dominierender Satz. Wenn p ≤ q, dann i(G) = p + 1 seit ist ein kleinster dominierender Satz, der auch unabhängig ist (es ist ein kleinster maximaler unabhängiger Satz).

Es gibt Graphfamilien, in denen γ (G) = i(G)Das heißt, jeder minimale maximale unabhängige Satz ist ein minimaler dominierender Satz. Zum Beispiel, γ (G) = i(G) wenn G ist ein klauenfreie Grafik.[3]

Ein Graph G wird als a genannt Dominal-Perfekt-Diagramm wenn γ(H) = i(H) in jedem induzierter Untergraph H von G. Da ein induzierter Untergraphen eines klauenfreien Diagramms krallenfrei ist, ist folgt, dass jede klauenfreie Grafiken auch die Herrschaftsartikel ist.[4]

Für jede Grafik G, es ist Liniendiagramm L(G) ist krallenfrei und daher ein minimaler maximaler unabhängiger Satz in L(G) ist auch ein minimaler dominierender Satz in L(G). Ein unabhängiger Set in L(G) entspricht a Matching in Gund ein dominierender Satz in L(G) entspricht einem Randdominiersatz in G. Deshalb a minimales maximales Matching hat die gleiche Größe wie ein minimaler Kanten -Dominationssatz.

Herrschaft von unabhängige Sets

Das Dominanznummer der Unabhängigkeit Iγ(G) einer Grafik G ist das Maximum über alle unabhängigen Sets A von G, des kleinsten Satzes dominieren A.[5] Die dominierenden Untergruppen von Scheitelpunkten erfordert potenziell weniger Scheitelpunkte als alle Scheitelpunkte zu dominieren. Iγ(G) ≤ γ(G) Für alle Grafiken G.

Die Ungleichheit kann streng sein - es gibt Grafiken G für welche Iγ(G) < γ(G). Zum Beispiel für eine Ganzzahl n, Lassen G Seien Sie ein Diagramm, in dem die Eckpunkte die Zeilen und Spalten von einem sind n-durch-n Board und zwei solcher Scheitelpunkte sind nur dann angeschlossen, wenn sie sich kreuzen. Die einzigen unabhängigen Sets sind Sätze nur Zeilen oder Sätze nur von Spalten, und jeder von ihnen kann von einem einzelnen Scheitelpunkt (einer Spalte oder einer Zeile) dominiert werden. Iγ(G) = 1. Um jedoch alle Scheitelpunkte zu dominieren, brauchen wir mindestens eine Zeile und eine Spalte, also γ(G) = 2. Darüber hinaus das Verhältnis zwischen γ(G) / Iγ(G) kann willkürlich groß sein. Zum Beispiel, wenn die Eckpunkte von G sind alle Teilmengen von Quadraten von einem n-durch-n Board, dann noch Iγ(G) = 1, aber γ(G) = n.[5]

Das Bi-unabhängige Herrschaftsnummer i & ggr ;i(G) einer Grafik G ist das Maximum über alle unabhängigen Sets A von G, des kleinsten unabhängigen Satzes dominieren A. Die folgenden Beziehungen halten für jede Grafik G:

Algorithmen und rechnerische Komplexität

Das festgelegte Problem ist ein bekanntes Problem Np-harte Problem - Die Entscheidungsversion von Set Covering war eine von Karps 21 NP-Complete-Probleme. Es gibt ein Paar Polynomzeit L-Reduktionen zwischen dem Mindestproblem der dominierenden Set und dem Stellen Sie das Cover -Problem fest.[6] Diese Reduktionen (siehe unten) Zeigen Sie, dass ein effizienter Algorithmus für das Mindestdominierproblem einen effizienten Algorithmus für das festgelegte Abdeckproblem liefern würde und umgekehrt. Darüber hinaus bewahren die Reduktionen die Annäherungsverhältnis: für jedes α, eine Polynomzeit α-Anerkennung Der Algorithmus für minimale Dominationssätze würde eine Polynomzeit liefern α-Anerkennung Algorithmus für das festgelegte Cover -Problem und umgekehrt. Beide Probleme sind in der Tat Log-apx-complete.[7]

Die Annäherung an die festgelegte Abdeckung ist ebenfalls gut verstanden: Ein logarithmischer Approximationsfaktor kann durch Verwendung von a gefunden werden Einfacher gieriger Algorithmusund das Finden eines unterschließenden Annäherungsfaktors ist np-hard. Insbesondere bietet der gierige Algorithmus einen Faktor 1 + log |V| Näherung eines minimalen dominierenden Satzes und kein Polynomzeitalgorithmus kann einen Annäherungsfaktor besser erreichen als c Protokoll |V| für einige c > 0 wenn nicht P = np.[8]

L-Reduktionen

Die folgenden zwei Reduktionen zeigen, dass das Mindestproblem der Mindestdominanz und die Stellen Sie das Cover -Problem fest sind äquivalent unter L-Reduktionen: Bei einer Instanz eines Problems können wir eine äquivalente Instanz des anderen Problems erstellen.[6]

Vom dominierenden Set bis zum Einstellen der Abdeckung

Bei einer Grafik G = (V, E) mit V = {1, 2, ...,, n}, Konstruieren Sie eine festgelegte Deckungsinstanz (U, S) wie folgt: die Universum U ist Vund die Familie der Untergruppen ist S = {{S1, S2, ..., Sn} so dass Sv besteht aus dem Scheitelpunkt v und alle Scheitelpunkte neben v in G.

Nun, wenn D ist ein dominierender Satz für G, dann C = {{Sv: v ∈ D} ist eine praktikable Lösung des festgelegten Abdeckproblems mit |C| = |D|. Umgekehrt, wenn C = {{Sv: v ∈ D} ist dann eine praktikable Lösung des festgelegten Abdeckproblems D ist ein dominierender Satz für G, mit |D| = |C|.

Daher die Größe eines minimalen dominierenden Satzes für G entspricht der Größe einer Mindestabdeckung für Mindestabdeckung für (U, S). Darüber hinaus gibt es einen einfachen Algorithmus, der einen dominierenden Satz auf eine festgelegte Abdeckung der gleichen Größe ordnet und umgekehrt. Insbesondere eine effiziente α-Anerkennung Der Algorithmus für die SET -Abdeckung bietet eine effiziente α-Anerkennung Algorithmus für minimale dominierende Sätze.

Dominating-set-2.svg
Zum Beispiel angegeben die Grafik G Auf der rechten Seite erstellen wir eine festgelegte Deckungsinstanz mit dem Universum U = {1, 2, ..., 6} und die Untergruppen S1 = {1, 2, 5}, S2 = {1, 2, 3, 5}, S3 = {2, 3, 4, 6}, S4 = {3, 4}, S5 = {1, 2, 5, 6}, und S6 = {3, 5, 6}. In diesem Beispiel, D = {3, 5} ist ein dominierender Satz für G - Dies entspricht der festgelegten Abdeckung C = {{S3, S5}. Zum Beispiel der Scheitelpunkt 4 ∈ V wird vom Scheitelpunkt dominiert 3 ∈ Dund das Element 4 ∈ U ist im Satz enthalten S3 ∈ C.

Vom Set -Abdeckung bis zum dominierenden Satz

Lassen (S, U) Seien Sie eine Instanz des festgelegten Cover -Problems mit dem Universum U und die Familie der Untergruppen S = {{Si: i ∈ I}; Wir nehmen an, dass U und der Indexsatz I sind disjunkt. Konstruieren Sie eine Grafik G = (V, E) wie folgt: Der Satz von Scheitelpunkten ist V = I ∪ U, Es gibt eine Kante {i, j} ∈ E zwischen jedem Paar i, j ∈ Iund es gibt auch eine Kante {i, u} für jeden i ∈ I und u ∈ Si. Das ist, G ist ein Split Graph: I ist ein Clique und U ist ein unabhängiger Satz.

Nun, wenn C = {{Si: i ∈ D} ist eine praktikable Lösung des festgelegten Abdeckproblems für eine Teilmenge D ⊆ I, dann D ist ein dominierender Satz für G, mit |D| = |C|: Erstens für jeden u ∈ U Da ist ein i ∈ D so dass u ∈ Siund durch Bau, u und i sind benachbart in G; somit u wird dominiert von i. Zweitens seit D muss jeweils nicht leer sein i ∈ I ist neben einem Scheitelpunkt in angrenzend D.

Umgekehrt lassen Sie D dominierende Set für sein G. Dann ist es möglich, einen anderen dominierenden Satz zu konstruieren X so dass |X| ≤ |D| und X ⊆ I: Ersetzen Sie einfach jeden u ∈ D ∩ U von einem Nachbarn i ∈ I von u. Dann C = {{Si: i ∈ X} ist eine praktikable Lösung des festgelegten Abdeckproblems mit |C| = |X| ≤ |D|.

Dominating-set-reduction.svg
Die Illustration auf der rechten Seite zeigt die Konstruktion für U = {{a, b, c, d, e}, I = {1, 2, 3, 4}, S1 = {{a, b, c}, S2 = {{a, b}, S3 = {{b, c, d}, und S4 = {{c, d, e}.
In diesem Beispiel, C = {{S1, S4} ist eine festgelegte Abdeckung; Dies entspricht dem dominierenden Satz D = {1, 4}.
D = {{a, 3, 4} ist ein weiterer dominierender Satz für die Grafik G. Gegeben DWir können einen dominierenden Satz erstellen X = {1, 3, 4} das ist nicht größer als D und welches eine Teilmenge von ist I. Der dominierende Satz X entspricht der festgelegten Abdeckung C = {{S1, S3, S4}.

Spezialfälle

Wenn die Grafik maximal Grad δ hat, findet der gierige Annäherungsalgorithmus eine O(log δ)-Abuchs einer minimalen dominierenden Menge. Lass es auch dg Seien Sie die Kardinalität des dominierenden Satzes, das unter Verwendung gierig Annäherung erhalten wird und dann die Relation befolgt. , wo N ist die Anzahl der Knoten und M ist die Anzahl der Kanten in gegebener ungerichteter Graph.[9] Für fest δ qualifiziert sich dies als dominierender Satz für APX Mitgliedschaft; Tatsächlich ist es APX-Complete.[10]

Das Problem gibt a zu Polynom-Zeit-Approximationsschema (PTAs) für Sonderfälle wie z. Einheiten -Festplatten -Diagramme und Planare Graphen.[11] Ein minimaler dominierender Satz finden Sie in der linearen Zeit in Serie -Parallel -Diagramme.[12]

Exakte Algorithmen

Ein minimaler dominierender Satz von a n-Vertex -Diagramme finden Sie rechtzeitig O(2nn) Durch die Überprüfung aller Scheitelpunktuntergruppen. Fomin, Grandoni & Kratsch (2009) Zeigen Sie, wie Sie einen minimalen dominierenden Satz rechtzeitig finden O(1.5137n) und exponentieller Raum und rechtzeitig O(1.5264n) und Polynomraum. Ein schnellerer Algorithmus verwendet O(1.5048n) Die Zeit wurde von gefunden von Van Rooij, Nederlof & Van Dijk (2009), die auch zeigen, dass in dieser Zeit die Anzahl der minimalen dominierenden Sets berechnet werden kann. Die Anzahl der minimalen dominierenden Sets ist höchstens 1.7159n und alle dieser Sets können rechtzeitig aufgeführt werden O(1.7159n).[13]

Parametrisierte Komplexität

Finden eines dominierenden Satzes von 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 verwendet in vielen Reduktionen, um die Unverdierbarkeit anderer Probleme zu zeigen. Insbesondere ist das Problem nicht Fix-Parameter-Traktable in dem Sinne, dass kein Algorithmus mit Laufzeit f(k)nO (1) für jede Funktion f existiert, es sei denn, die W-hierarchie bricht zu fpt = w [2] zusammen.

Wenn sich das Eingangsgraphen hingegen planar handelt, bleibt das Problem NP-HART, aber ein fester Parameteralgorithmus ist bekannt. Tatsächlich hat das Problem einen Kern der Größe linear in k,[14] und laufende Zeiten, die exponentiell sind √k und kubisch in n kann durch Bewerbung erhalten werden Dynamische Programmierung zu einem Branchenabbau des Kernels.[15] Im Allgemeinen sind das dominierende Satzproblem und viele Varianten des Problems mit fester Parametern genau bei der Parametrialisierung sowohl durch die Größe des dominierenden Satzes als auch durch die Größe des kleinsten Traktsabschnitts. verboten Vollständiger zweipartnerer Untergraphen; Das heißt, das Problem ist FPT auf biclique-freie Grafiken, eine sehr allgemeine Klasse von spärlichen Graphen, die die planaren Graphen enthalten.[16]

Der ergänzende Set auf einen dominierenden Satz a Nichtblocker, kann durch einen Fix-Parameter-Algorithmus in jedem Diagramm gefunden werden.[17]

Varianten

Eine wichtige Unterklasse der dominierenden Sets ist die Klasse von Verbundene dominierende Sätze. Wenn S ist ein verbundenes dominierender Satz, man kann a bilden Spannungsbaum von G in welchem S bildet den Satz nicht-blattheigerteiliger Eckpunkte des Baumes; Umgekehrt, wenn T ist jeder Spannungsbaum in einem Diagramm mit mehr als zwei Scheitelpunkten T Bildung eines verbundenen dominierenden Satzes. Daher entspricht das Finden von dominierenden Sätzen mit minimalem Verbundenen dem Finden von Bäumen mit der maximal möglichen Anzahl von Blättern.

A Gesamt dominierender Satz ist ein Satz von Scheitelpunkten, so dass alle Scheitelpunkte im Diagramm (einschließlich der Eckpunkte im dominierenden Satz selbst) einen Nachbarn im dominierenden Satz haben.[18] Abbildung (c) oben zeigt einen dominierenden Satz, der ein verbundener dominierender Satz und einen Gesamtdominiersatz ist. Die Beispiele in Abbildungen (a) und (b) sind weder.

A k-tupel dominierende Set ist ein Satz von Scheitelpunkten, so dass jeder Scheitelpunkt in der Grafik zumindest hat k Nachbarn im Set. Ein (1+log n)-Apploximation eines Minimums k-Tupel -dominierende Menge findet sich in der Polynomzeit.[19] Ebenso a k-dominierend ist ein Satz von Scheitelpunkten, so dass jeder Scheitelpunkt nicht im Set zumindest hat k Nachbarn im Set. Während jede Grafik a zulässt k-dominierend, nur Grafiken mit minimalem Grad k - 1 zugeben a k-tupel dominierende Set. Allerdings auch, wenn das Diagramm zulässt k-tupel dominierende Menge, ein Minimum k-tupel dominierende Set kann fast sein k mal so groß wie ein Minimum k-dominierend für dasselbe Diagramm;[20] Ein (1,7 + log δ)-Apploximation eines Minimums k-Dominierende Set finden Sie auch in der Polynomzeit.

A Sternendominierende Set ist ein Teilmenge D von V so dass für jeden Scheitelpunkt v in V, das Stern von v (der Satz von Kanten neben v) kreuzt den Stern einiger Scheitelpunkte in D. Klar, wenn g hat isolierte Eckpunkte Dann hat es keine sterndominierenden Sets (da der Stern der isolierten Scheitelpunkte leer ist). Wenn G keine isolierten Eckpunkte hat, ist jedes dominierende Set ein sterndominierender Satz und umgekehrt. Die Unterscheidung zwischen Sterndomination und üblicher Herrschaft ist wesentlicher, wenn ihre fraktionalen Varianten berücksichtigt werden.[21]

A Domatische Partition ist eine Partition der Eckpunkte in disjunkte dominierende Sätze. Die domatische Zahl ist die maximale Größe einer domatischen Partition.

Ein Ewiger dominierender Satz ist eine dynamische Version der Herrschaft, bei der ein Scheitelpunkt v im dominierenden Satz D wird ausgewählt und durch einen Nachbarn ersetzt u (u ist nicht in D) so dass die modifizierten D ist auch ein dominierender Satz und dieser Vorgang kann über jede unendliche Abfolge von Eckpunkten wiederholt werdenv.

Siehe auch

Anmerkungen

  1. ^ Garey & Johnson (1979).
  2. ^ Hedetniemi & Laskar (1990).
  3. ^ Allan & Laskar (1978).
  4. ^ Faudree, Flandrin & Ryjáček (1997).
  5. ^ a b Aharoni, Ron; Berger, Eli; Ziv, Ran (2007-05-01). "Unabhängige Systeme von Vertretern in gewichteten Graphen". Combinatorica. 27 (3): 253–267. doi:10.1007/s00493-007-2086-y. ISSN 1439-6912. S2CID 43510417.
  6. ^ a b Kann (1992), S. 108–109.
  7. ^ Escoffier & Paschos (2006).
  8. ^ Raz & Safra (1997).
  9. ^ Parekh (1991).
  10. ^ Papadimitriou & Yannakakis (1991).
  11. ^ Crescenzi et al. (2000).
  12. ^ Takamizawa, Nishizeki & Saito (1982).
  13. ^ Fomin et al. (2008).
  14. ^ Alber, Fellows & Nigermeier (2004).
  15. ^ Fomin & Thilikos (2006).
  16. ^ Telle & Villanger (2012).
  17. ^ Dehne et al. (2006).
  18. ^ West (2001), Abschnitt 3.1.
  19. ^ Klasing & Laforest (2004).
  20. ^ Förster (2013).
  21. ^ Meshulam, Roy (2003-05-01). "Herrschaftszahlen und Homologie". Journal of Combinatorial Theory, Serie a. 102 (2): 321–330. doi:10.1016/s0097-3165 (03) 00045-1. ISSN 0097-3165.

Verweise

Weitere Lektüre