Dominant set

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 24 februari 2021; verifiering kräver 1 redigering .

I grafteorin är den dominerande mängden för en graf G = ( V , E ) en delmängd D av vertexmängden V , så att varje vertex som inte är i D ligger intill åtminstone ett element i D. Dominanstalet γ( G ) är antalet hörn i den minsta dominerande mängden G .

Det dominerande mängdproblemet är att kontrollera om olikheten γ( G ) ≤ K är sann för en given graf G och ett tal K . Problemet är ett klassiskt NP-komplett lösbarhetsproblem inom beräkningskomplexitetsteori [1] . Man tror alltså att det inte finns någon effektiv algoritm för att hitta den minsta dominerande uppsättningen för en given graf.

Figurerna (a)-(c) till höger visar tre exempel på dominerande grafuppsättningar. I dessa exempel ligger varje vit hörn intill minst en röd hörn, och de vita hörnen sägs domineras av de röda hörnen. Det dominerande talet för denna graf är 2 - exemplen (b) och (c) visar att det finns en dominerande mängd med 2 hörn, och det kan kontrolleras att det för denna graf inte finns någon dominerande mängd med bara en vertex.

Historik

Som Hedeenimi och Laskar [2] noterade har dominansproblematiken studerats sedan 1950-talet, men antalet studier om dominans ökade avsevärt i mitten av 1970-talet. Deras bibliografi innehåller över 300 artiklar relaterade till grafdominans.

Gränser

Låt G  vara en graf med n ≥ 1 hörn, och låt Δ vara den maximala graden av grafen. Följande gränser γ( G ) [3] är kända :

Oberoende dominans

Dominanta mängder är nära besläktade med oberoende mängder  — en oberoende mängd är dominant om och endast om den är den största oberoende mängden , så varje största oberoende mängd [4] i en graf är också den minsta dominanta mängden. Det oberoende dominanstalet i ( G ) för G  är storleken på den minsta oberoende dominerande mängden (eller, på motsvarande sätt, minimistorleken för de största oberoende uppsättningarna).

Den minsta dominanta mängden i en graf är inte nödvändigtvis oberoende, men storleken på den minsta dominanta mängden är alltid mindre än eller lika med storleken på den minsta största oberoende mängden, det vill säga γ( G ) ≤ i ( G ).

Det finns graffamiljer där den minsta största oberoende uppsättningen är den minsta dominerande uppsättningen. Till exempel visade Allan och Lascar [5] att γ( G ) = i ( G ) om G inte har klor .

En graf G kallas en dominant perfekt graf om γ( H ) = i ( H ) i någon genererad subgraf H av G . Eftersom den genererade subgrafen i en klofri graf är klofri, följer det att vilken klofri graf som helst är dominerande perfekt [6] .

Exempel

Figurerna (a) och (b) visar oberoende dominerande mängder, medan figur (c) visar en mängd som inte är oberoende.

För varje graf G är dess linjegraf L ( G ) klofri, och därför är den minsta största oberoende mängden i L ( G ) också den minsta dominerande mängden i L ( G ). En oberoende mängd i L ( G ) motsvarar en matchning i G , och en dominerande mängd i L ( G ) motsvarar en kantdominerande mängd i G . Således har den minsta största matchningen samma storlek som den minsta kantdominerande uppsättningen.

Algoritmer och beräkningskomplexitet

Det finns ett par polynom-tid L-reduktioner mellan det minsta dominerande mängdproblemet och det mängdtäckande problemet [7] . Dessa reduktioner (se nedan) visar att en effektiv algoritm för det minsta dominerande uppsättningsproblemet skulle ge en effektiv algoritm för täckningsuppsättningsproblemet och vice versa. Dessutom bevarar reduktionerna approximationsfaktorn  - för varje α, skulle en polynom-tid α-approximationsalgoritm för att hitta en minsta dominerande mängd tillhandahålla en polynom-tid α-approximationsalgoritm för mängden som täcker problemet , och vice versa. Båda uppgifterna är i själva verket Log-APX-kompletta [8] .

Mängdtäckningsproblemet är ett välkänt NP-hårt problem - mängdtäckningsproblemet i en variant av lösbarhetsproblemet var ett av Karps 21 NP-komplettproblem , för vilket NP-fullständighet bevisades redan 1972. Reducerbarheten visar att det dominerande setproblemet också är NP-hårt.

Approximabiliteten för uppsättningsomslagsproblemet är också väl förstått - den logaritmiska approximationsfaktorn kan hittas med en enkel girig algoritm , och att hitta den sublogaritmiska och logaritmiska faktorn är ett NP-hårt problem. Mer specifikt ger den giriga algoritmen en approximationsfaktor på 1 + log | v | för den minsta dominerande uppsättningen, och Raz och Safra [9] visade att ingen algoritm ger en approximationsfaktor bättre än C *log | v | för vissa C > 0 om inte P = NP .

L-casts

Nästa par reduktioner [7] visar att det minsta dominerande mängdproblemet och mängdtäckningsproblemet är ekvivalenta i L-reduktion  — givet ett problem kan vi konstruera ett ekvivalent uttalande av det andra problemet.

Från dominerande set till täckande set. Givet en graf G = ( V , E ) med V = {1, 2, …, n } konstruerar vi en täckning av mängden ( U , S ) enligt följande: Mängden U är lika med V , och familjen av delmängder är lika med S = { S 1 , S 2 , …, S n }, där Sv består av vertex v och alla hörn som gränsar till v hörn från G .

Nu, om D är en dominerande mängd i G , så är C = { S v  : v ∈ D } en möjlig lösning för täckningsproblemet med | c | = | D |. Omvänt, om C = { S v  : v ∈ D } är en möjlig lösning för täckningsproblemet, då är D en dominerande mängd för G med | D | = | C |.

Följaktligen är storleken på den minsta dominerande uppsättningen för G lika med storleken av den minsta uppsättningen täckning för ( U , S ). Dessutom finns det en enkel algoritm som mappar en dominerande uppsättning till en täckande uppsättning av samma storlek, och vice versa. I synnerhet ger en effektiv a-approximationsalgoritm för uppsättningstäckning en effektiv a-approximationsalgoritm för minimala dominerande uppsättningar.

Till exempel, givet grafen G som visas till höger, bygger vi ett uppsättningsomslag med uppsättningen U = {1, 2, …, 6} och delmängder 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} och S 6 = {3, 5, 6}. I det här exemplet är D = {3, 5} den dominanta mängden för G  - den motsvarar omslaget C = { S 3 , S 5 }. Till exempel domineras vertex 4 ∈ V av vertex 3 ∈ D , och element 4 ∈ U ingår i mängden S 3 ∈ C .

Från att täcka ett set till ett dominant set. Låt ( S , U ) vara en lösning på det mängd som täcker problemet med samling U och familj av delmängder S = { Si  : i ∈ I } . Vi antar att U och indexmängden I inte skär varandra. Vi bygger grafen G = ( V , E ) enligt följande. Ta V = I ∪ U som uppsättningen av hörn . Vi definierar en kant { i , j } ∈ E mellan varje par i , j ∈ I , samt en kant { i , u } för varje i ∈ I och u ∈ Si . Det vill säga, G är en delad graf  - I är en klick och U är en oberoende mängd .

Nu, om C = { Si  : i ∈ D } är en möjlig lösning på det mängdtäckande problemet för någon delmängd D ⊆ I , då är D en dominerande mängd för G med | D | = | C |: För det första, för varje hörn u ∈ U , finns det i ∈ D så att u ∈ Si , och, genom konstruktion, u och i är intilliggande i G . Därför domineras -u av vertex i . För det andra, eftersom D måste vara icke-tom, är varje i ∈ I intill en vertex i D .

Omvänt, låt D vara en dominerande mängd för G . Sedan kan vi konstruera en annan dominerande mängd X så att | x | ≤ | D | och X ⊆ I  ersätter helt enkelt varje vertex u ∈ D ∩ U med en vertex i ∈ I intill u . Då är C = { Si  : i ∈ X } en genomförbar lösning på täckningsproblemet med | c | = | x | ≤ | D |.

Figuren till höger visar konstruktionen för U = { a , b , c , d , e }, I = {1, 2, 3, 4}, S 1 = { a , b , c }, S 2 = { a , b }, S3 = { b , c , d } och S4 = { c , d , e }. I det här exemplet är C = { S 1 , S 4 } omslaget till uppsättningen. Det motsvarar den dominerande mängden D = {1, 4}. D = { a , 3, 4} är ​​en annan dominerande uppsättning för grafen G . Givet D kan vi konstruera en dominerande mängd X = {1, 3, 4} som inte överstiger D och är en delmängd av I . Den dominerande mängden X motsvarar omslaget till mängden C = { S 1 , S 3 , S 4 }.

Särskilda tillfällen

Om grafen har en maximal grad Δ, så hittar den giriga approximationsalgoritmen en O (log Δ)-approximation av den minsta dominerande mängden. Låt också d g vara styrkan för den dominerande mängden erhållen med den giriga approximationsalgoritmen, då gäller följande relation: d g ≤ N+1 - , där N är antalet noder och M är antalet kanter i en given given oriktad graf [10] . För en fast Δ betyder detta att problemet med att hitta den dominanta mängden tillhör klassen APX . Faktum är att problemet är APX-komplett [11] .

Algoritmen tillåter PTAS för speciella fall som enhetscirkelgrafer och plana grafer [12] . Den minsta dominerande mängden kan hittas i linjär tid i parallell-sekventiella grafer [13] .

Exakta algoritmer

Den minsta dominerande uppsättningen av en graf med n hörn kan hittas i O (2 n n ) tid genom att titta på alla delmängder av hörn. Fomin, Grandoni och Kratch visade [14] hur man hittar den minsta dominerande mängden i O (1,5137 n ) tid med exponentiellt minne och O (1,5264 n ) tid med polynomminne. En snabbare algoritm som körs i O (1,5048 n ) tid hittades av von Roy, Nederlof och von Dijk [15] , som visade att antalet minsta dominerande uppsättningar kan beräknas inom den angivna tiden. Antalet minimala dominerande uppsättningar överstiger inte 1,7159 n och alla sådana uppsättningar kan räknas upp i tiden O (1,7159 n ) [16] .

Parametrisk komplexitet

Sökandet efter en dominerande uppsättning av storlek k spelar en central roll i parametrisk komplexitetsteori. Problemet är det mest välkända W[2]-kompletta problemet och används i många fall för att visa problemets svårhanterliga problem genom att reducera det till problemet att hitta den dominerande mängden. I synnerhet är problemet inte lösbart med fast parametrisk (FPR) i den meningen att det inte finns någon algoritm med körtid f ( k ) n O(1) för någon funktion f , såvida inte W-hierarkin kollapsar till FPT =W[2].

Å andra sidan, om ingångsgrafen är plan förblir problemet NP-hårt, men algoritmen med en fast parameter är känd. Faktum är att problemet har en kärna med en storlek linjär i k [17] , och en körtid som är exponentiell i √ k och kubik i n kan uppnås genom att tillämpa dynamisk programmering för att förgrena kärnan [18] . Mer generellt är problemet med den dominerande mängden och många varianter av problemet fast-parametriskt lösbara om parametriseringen utförs både när det gäller storleken på den dominerande mängden och när det gäller storleken på den minsta förbjudna fullständiga tvådelade subgrafen . Det vill säga, problemet är en FPR på grafer utan bicliques , en ganska allmän klass av glesa grafer, som inkluderar plana grafer [19] .

Alternativ

Vizings gissning relaterar dominanstalet för en direkt produkt av grafer till dominanstalen för dess faktorer.

Det finns många artiklar om anslutna dominerande uppsättningar . Om S är en ansluten dominerande mängd, kan man bilda ett spännande träd av G där S bildar uppsättningen av icke-bladiga hörn av trädet . Omvänt, om T är ett spännande träd i en graf med mer än två hörn, bildar de icke-bladiga hörn av T en sammankopplad dominerande mängd. Sålunda är sökandet efter minimalt sammankopplade dominerande uppsättningar ekvivalent med sökandet efter spännande träd med maximalt möjliga antal löv.

En komplett dominerande mängd  är en uppsättning av hörn så att alla hörn i grafen (inklusive hörn i den dominerande mängden själv) har grannar i den dominerande mängden. Figur (c) ovan visar en dominerande uppsättning som är både en ansluten dominerande uppsättning och en komplett dominerande uppsättning samtidigt. I figurerna (a) och (b) är de dominerande uppsättningarna ingendera.

En k-tuppeldominerande uppsättning  är en uppsättning av hörn så att varje vertex i grafen har minst k grannar i mängden. (1+log n) approximationen av en minimal k-tupeldominerande mängd kan hittas i polynomtid [20] . På liknande sätt är en k-dominant mängd  en uppsättning av hörn så att varje hörn som inte ingår i mängden har åtminstone k grannar i mängden. Medan vilken graf som helst tillåter en k-dominant uppsättning, tillåter endast grafer med en lägsta grad av k-1 en k-tuppeldominerande uppsättning. Men även om grafen tillåter en dominerande uppsättning av k-tuppel, kan den minsta dominerande uppsättningen för k-tuppel vara nästan k gånger den minsta dominerande uppsättningen för k-tuppel för samma graf [21] . (1,7+log Δ)-approximationen av den minimala k-dominerande mängden kan också hittas i polynomtid.

En domatisk nedbrytning  är en nedbrytning av hörn till icke-överlappande dominerande uppsättningar. Ett domatiskt nummer är den maximala storleken på en domatisk expansion.

Den evigt dominerande mängden  är en dynamisk version av dominans där ett hörn v i den dominerande mängden D väljs och ersätts av ett angränsande u ( u inte i D ) på ett sådant sätt att den modifierade mängden D också dominerar och denna process kan upprepas för valfri ändlig sekvens av vertexval v.

Programvara för att hitta den minsta dominerande uppsättningen

namn Licens Användarspråk kort information
öppna opt BSD Pytonorm Använder NetworkX- grafer . Kan använda gratisprogram och kommersiella paket. Se den dominerande uppsättningssidan för detaljer och exempel .

Se även

Anteckningar

  1. ↑ Gary, Johnson, 1982 , sid. 235, Uppgift TG2.
  2. ↑ Hedetniemi, Laskar, 1990 .
  3. ↑ Haynes, Hedetniemi, Slater, 1998a , sid. kapitel 2.
  4. ↑ Det finns ofta förvirring med termerna största mängd och maximal mängd . I den här artikeln förstås den största uppsättningen som en uppsättning som inte kan förlängas med bibehållen egendom. En maximal uppsättning är en uppsättning med en given egenskap som har en maximal storlek.
  5. ↑ Allan, Laskar, 1978 .
  6. ↑ Faudree, Flandrin, Ryjaček, 1997 .
  7. ↑ 1 2 Kann, 1992 , sid. 108–109.
  8. ↑ Escoffier, Paschos, 2006 , sid. 369–377.
  9. ↑ Raz, Safra, 1997 .
  10. ↑ Parekh, 1991 , sid. 237-240.
  11. ↑ Papadimitriou, Yannakakis, 1991 , sid. 425–440.
  12. ↑ Crescenzi, Kann, Halldorsson, Karpinski, 2000 .
  13. ↑ Takamizawa, Nishizeki, Saito, 1982 .
  14. ↑ Fomin, Grandoni, Kratsch, 2009 .
  15. ↑ van Rooij, Nederlof, van Dijk, 2009 .
  16. ↑ Fomin, Grandoni, Pyatkin, Stepanov, 2008 .
  17. ↑ Alber, Fellows, Niedermeier, 2004 .
  18. ↑ Fomin, Thilikos, 2006 .
  19. ↑ Telle, Villanger, 2012 .
  20. ↑ Klasing, Laforest, 2004 .
  21. ↑ Forster, 2013 .

Litteratur