Hallitseva sarja

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 24. helmikuuta 2021 tarkistetusta versiosta . vahvistus vaatii 1 muokkauksen .

Graafiteoriassa graafin G = ( V , E ) dominanttijoukko on kärkijoukon V osajoukko D siten , että mikä tahansa kärki, joka ei ole D :ssä, on vähintään yhden D :n elementin vieressä . Dominanssiluku γ( G ) on pisteiden lukumäärä pienimmässä hallitsevassa joukossa G .

Dominoiva joukkoongelma on tarkistaa, onko epäyhtälö γ( G ) ≤ K totta tietylle graafille G ja luvulle K . Ongelma on klassinen NP -täydellinen ratkaistavuusongelma laskennallisessa monimutkaisuusteoriassa [1] . Näin ollen uskotaan, ettei ole olemassa tehokasta algoritmia pienimmän hallitsevan joukon löytämiseksi tietylle graafille.

Kuvat (a)-(c) oikealla esittävät kolme esimerkkiä hallitsevista graafijoukoista. Näissä esimerkeissä jokainen valkoinen kärki on vähintään yhden punaisen kärjen vieressä, ja valkoisten kärkipisteiden sanotaan hallitsevan punaisia. Tämän graafin hallitseva luku on 2 - esimerkit (b) ja (c) osoittavat, että on olemassa hallitseva joukko, jossa on 2 kärkeä, ja voidaan tarkistaa, että tälle graafille ei ole hallitsevaa joukkoa, jossa on vain yksi kärki.

Historia

Kuten Hedeenimi ja Laskar [2] totesivat , dominanssiongelmaa on tutkittu 1950-luvulta lähtien, mutta määräävää asemaa koskevien tutkimusten määrä lisääntyi huomattavasti 1970-luvun puolivälissä. Heidän bibliografiansa sisältää yli 300 graafisen dominanssiin liittyvää artikkelia.

Reunat

Olkoon G  graafi, jossa on n ≥ 1 kärkeä, ja olkoon Δ graafin maksimiaste. Seuraavat rajat γ( G ) [3] tunnetaan :

Itsenäinen ylivalta

Dominanttijoukot liittyvät läheisesti riippumattomiin joukkoihin  – riippumaton joukko on hallitseva silloin ja vain, jos se on suurin itsenäinen joukko , joten mikä tahansa suurin riippumaton joukko [4] graafissa on myös pienin hallitseva joukko. G : n riippumaton dominanssiluku i ( G )  on pienimmän riippumattoman hallitsevan joukon koko (tai vastaavasti suurimpien riippumattomien joukkojen minimikoko).

Graafin minimidominanttijoukko ei välttämättä ole itsenäinen, mutta minimidominoivan joukon koko on aina pienempi tai yhtä suuri kuin suurimman riippumattoman minimijoukon koko, eli γ( G ) ≤ i ( G ).

On olemassa graafiperheitä, joissa pienin suurin itsenäinen joukko on vähimmäisdominoiva joukko. Esimerkiksi Allan ja Lascar [5] osoittivat, että γ( G ) = i ( G ), jos G : llä ei ole kynsiä .

Graafia G kutsutaan dominoivasti täydelliseksi graafiksi , jos γ( H ) = i ( H ) missä tahansa G : n generoidussa osagraafissa H. Koska kynsittömän graafin generoitu aligraafi on kynsitön, tästä seuraa, että mikä tahansa kynsitön graafi on hallitsevasti täydellinen [6] .

Esimerkkejä

Kuvat (a) ja (b) esittävät riippumattomia hallitsevia joukkoja, kun taas kuva (c) esittää joukkoa, joka ei ole riippumaton.

Minkä tahansa graafin G kohdalla sen viivakaavio L ( G ) on kynsitön, ja siksi L:n (G) pienin suurin itsenäinen joukko on myös L ( G ) hallitseva pienin joukko . Riippumaton joukko L ( G ):ssä vastaa sovitusta G : ssä ja hallitseva joukko L ( G ):ssä vastaa reunadominoivaa joukkoa G :ssä . Siten pienin suurin sovitus on samankokoinen kuin minimireunadominoiva joukko.

Algoritmit ja laskennallinen monimutkaisuus

Minimidominoivan joukkotehtävän ja joukon peittotehtävän välillä on pari polynomiaikaista L-pelkistystä [7] . Nämä vähennykset (katso alla) osoittavat, että tehokas algoritmi hallitsevan vähimmäisjoukon ongelmalle antaisi tehokkaan algoritmin peittävälle joukko-ongelmalle ja päinvastoin. Lisäksi vähennykset säilyttävät approksimaatiokertoimen  — mille tahansa α:lle polynomiajan α-approksimaatioalgoritmi hallitsevan vähimmäisjoukon löytämiseksi tarjoaisi polynomiaikaisen α-approksimaatioalgoritmin joukon peittävälle ongelmalle ja päinvastoin. Molemmat tehtävät ovat itse asiassa Log-APX-täydellisiä [8] .

Joukon peittotehtävä on hyvin tunnettu NP-kova tehtävä - joukon peittotehtävä ratkaistavuusongelman muunnelmassa oli yksi Karpin 21 NP-täydestä tehtävästä, jolle NP-täydellinen tehtävä on todistettu jo vuonna 1972. Pelkistyvyys osoittaa että hallitseva joukko-ongelma on myös NP-kova.

Asetetun peittotehtävän approksimaatio on myös hyvin ymmärretty – logaritminen approksimaatiokerroin löytyy yksinkertaisella ahneella algoritmilla , ja sublogaritmisen ja logaritmisen tekijän löytäminen on NP-kova ongelma. Tarkemmin sanottuna ahne algoritmi antaa approksimaatiokertoimen 1 + log | v | vähimmäisdominoivalle joukolle, ja Raz ja Safra [9] osoittivat, että mikään algoritmi ei tuota parempaa approksimaatiokerrointa kuin C *log | v | joillekin C > 0 ellei P = NP .

L-casts

Seuraava pelkistyspari [7] osoittaa, että minimidominoiva joukko -ongelma ja joukon peittotehtävä ovat ekvivalentteja L-pelkistykseen  – yhden tehtävän perusteella voimme rakentaa vastaavan lauseen toiselle ongelmalle.

Hallitsevasta setistä peittosarjaan. Kun graafi G = ( V , E ), jossa V = {1, 2, …, n }, rakennamme joukon ( U , S ) peitteen seuraavasti: Joukko U on yhtä suuri kuin V , ja joukon perhe osajoukot on yhtä suuri kuin S = { S 1 , S 2 , …, S n }, missä S v koostuu pisteestä v ja kaikista G :n v :n pisteistä .

Nyt, jos D on hallitseva joukko G :ssä , niin C = { S v  : v ∈ D } on toteuttamiskelpoinen ratkaisu peittotehtävälle | c | = | D |. Kääntäen, jos C = { S v  : v ∈ D } on käyttökelpoinen ratkaisu peittotehtävälle, niin D on hallitseva joukko G :lle , jossa | D | = | C |.

Näin ollen G :n hallitsevan vähimmäisjoukon koko on yhtä suuri kuin ( U , S ) minimijoukon kannen koko . Lisäksi on olemassa yksinkertainen algoritmi, joka kartoittaa hallitsevan joukon samankokoiseksi peittäväksi joukoksi ja päinvastoin. Erityisesti tehokas a-approksimaatioalgoritmi joukon kattavuudelle tuottaa tehokkaan a-approksimaatioalgoritmin minimaalisille hallitseville joukoille.

Esimerkiksi, kun otetaan huomioon oikealla oleva kaavio G , rakennamme joukon kannen, jossa joukko U = {1, 2, …, 6} ja osajoukot 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} ja S 6 = {3, 5, 6}. Tässä esimerkissä D = {3, 5} on G :n hallitseva joukko  - se vastaa kantta C = { S 3 , S 5 }. Esimerkiksi kärkeä 4 ∈ V hallitsee kärki 3 ∈ D , ja alkio 4 ∈ U sisältyy joukkoon S 3 ∈ C .

Sarjan peittämisestä hallitsevaan sarjaan. Olkoon ( S , U ) ratkaisu joukon peittoongelmaan joukolla U ja osajoukkojen perheellä S = { S i  : i ∈ I }. Oletetaan, että U ja indeksijoukko I eivät leikkaa. Rakennamme graafin G = ( V , E ) seuraavasti. Otetaan V = I ∪ U kärkijoukoksi . Määritämme reunan { i , j } ∈ E kunkin parin i , j ∈ I välille sekä reunan { i , u } kullekin i ∈ I :lle ja u ∈ S i :lle . Eli G on jaettu graafi  - I on klikki ja U on itsenäinen joukko .

Nyt, jos C = { S i  : i ∈ D } on toteuttamiskelpoinen ratkaisu joukon peittoongelmaan jollekin osajoukolle D ⊆ I , niin D on hallitseva joukko G :lle , jossa | D | = | C |: Ensinnäkin mille tahansa pisteelle u ∈ U on olemassa i ∈ D siten, että u ∈ S i , ja konstruktion mukaan u ja i ovat G :ssä vierekkäisiä . Näin ollen - u hallitsee kärki i . Toiseksi, koska D : n täytyy olla ei-tyhjä, mikä tahansa i ∈ I on D :n kärjen vieressä .

Kääntäen, olkoon D hallitseva joukko G :lle . Sitten voimme rakentaa toisen hallitsevan joukon X siten, että | x | ≤ | D | ja X ⊆ I  yksinkertaisesti korvaa jokaisen kärjen u ∈ D ∩ U u : n vieressä olevalla kärjellä i ∈ I. Tällöin C = { S i  : i ∈ X } on toteuttamiskelpoinen ratkaisu peittotehtävään | c | = | x | ≤ | D |.

Oikeanpuoleinen kuva esittää U = { a , b , c , d , e }, I = {1, 2, 3, 4}, S 1 = { a , b , c }, S 2 = { konstruktion a , b }, S3 = { b , c , d } ja S4 = { c , d , e }. Tässä esimerkissä C = { S 1 , S 4 } on joukon kansi. Se vastaa hallitsevaa joukkoa D = {1, 4}. D = { a , 3, 4} on toinen hallitseva joukko graafille G . Kun D , voimme rakentaa hallitsevan joukon X = {1, 3, 4}, joka ei ylitä D :tä ja on I :n osajoukko . Dominoiva joukko X vastaa joukon C = { S 1 , S 3 , S 4 } peittoa.

Erikoistilaisuudet

Jos graafin maksimiaste on Δ, niin ahne approksimaatioalgoritmi löytää O (log Δ) -approksimaation minimidominoivalle joukolle. Olkoon d g myös ahneella approksimaatioalgoritmilla saadun hallitsevan joukon potenssi, jolloin pätee seuraava suhde: d g ≤ N+1 - , missä N on solmujen lukumäärä ja M on reunojen lukumäärä tietyssä suuntaamaton graafi [10] . Kiinteälle Δ:lle tämä tarkoittaa, että hallitsevan joukon löytämisongelma kuuluu luokkaan APX . Itse asiassa ongelma on APX-täydellinen [11] .

Algoritmi mahdollistaa PTAS :n erikoistapauksissa, kuten yksikköympyräkaavioissa ja tasokaavioissa [12] . Dominoiva minimijoukko löytyy lineaarisessa ajassa rinnakkaisista peräkkäisistä kuvaajista [13] .

Tarkat algoritmit

Graafin, jossa on n pistettä , vähimmäisdominoiva joukko löytyy O (2 n n ) -ajassa tarkastelemalla kaikkia kärkien osajoukkoja. Fomin, Grandoni ja Kratch osoittivat [14] kuinka löytää hallitseva minimijoukko O (1.5137 n ) ajassa käyttämällä eksponentiaalista muistia ja O (1.5264 n ) ajassa polynomimuistia käyttäen. Nopeamman O (1,5048 n ) -ajassa ajavan algoritmin löysivät von Roy, Nederlof ja von Dijk [15] , jotka osoittivat, että määräävässä ajassa voidaan laskea hallitsevien vähimmäisjoukkojen määrä. Minimaalisten hallitsevien joukkojen määrä ei ylitä 1,7159 n ja kaikki tällaiset joukot voidaan laskea ajassa O (1,7159 n ) [16] .

Parametrinen monimutkaisuus

K -koon hallitsevan joukon etsimisellä on keskeinen rooli parametrisessa kompleksisuusteoriassa. Ongelma on tunnetuin W[2]-täydellinen -ongelma, ja sitä käytetään monissa tapauksissa osoittamaan ongelman ratkaisemattomuutta vähentämällä se hallitsevan joukon löytämisen ongelmaksi. Erityisesti ongelma ei ole kiinteäparametrinen ratkaistava (FPR) siinä mielessä, että millekään funktiolle f ei ole algoritmia, jonka suoritusaika on f ( k ) n O(1) , ellei W-hierarkia romahda FPT:ksi. =W[2].

Toisaalta, jos syötekaavio on tasomainen, ongelma jää NP-kovaksi, mutta algoritmi kiinteällä parametrilla tunnetaan. Itse asiassa ongelmassa on ydin, jonka koko on lineaarinen k :ssä [17] , ja käyntiaika, joka on eksponentiaalinen √ k :ssä ja kuutio n :ssä, voidaan saavuttaa soveltamalla dynaamista ohjelmointia ytimen haaroittamiseen [ 18] . Yleisemmin dominoiva joukko-ongelma ja monet ongelman muunnelmat ovat kiinteäparametrisesti ratkaistavissa, jos parametrisointi suoritetaan sekä hallitsevan joukon koon että pienimmän kielletyn täydellisen kaksiosaisen aligraafin koon suhteen . Toisin sanoen ongelmana on FPR graafisille ilman biklikejä , melko yleinen harvalukuisten graafien luokka, joka sisältää tasomaiset graafit [19] .

Vaihtoehdot

Visingin olettamus yhdistää graafien suoran tulon dominanssiluvun sen tekijöiden dominanssilukuihin.

On olemassa monia papereita yhdistetystä hallitsevasta sarjasta . Jos S on yhdistetty hallitseva joukko, voidaan muodostaa G :n virittävä puu , jossa S muodostaa puun ei-lehtipisteiden joukon . Päinvastoin, jos T on graafin virittävä puu, jossa on enemmän kuin kaksi kärkeä, T :n ei-lehtipisteet muodostavat yhdistetyn hallitsevan joukon. Siten minimaalisten toisiinsa liittyvien hallitsevien joukkojen etsiminen vastaa mahdollisimman suuren lehtimäärän sisältävien puiden etsimistä.

Täydellinen hallitseva joukko  on joukko pisteitä siten, että kaikilla graafin pisteillä (mukaan lukien itse hallitsevan joukon kärjet) on naapureita hallitsevassa joukossa. Yllä oleva kuva (c) esittää hallitsevaa joukkoa, joka on samanaikaisesti sekä yhdistetty hallitseva joukko että täydellinen hallitseva joukko. Kuvissa (a) ja (b) hallitsevat joukot eivät ole kumpaakaan.

K-tuple hallitseva joukko  on joukko pisteitä siten, että jokaisella graafin kärjellä on vähintään k naapuria joukossa. Minimaalisen k-monikon hallitsevan joukon (1+log n) approksimaatio löytyy polynomiajassa [20] . Vastaavasti k-dominanttijoukko  on joukko pisteitä siten, että jokaisella joukossa olevalla kärjellä on vähintään k naapuria joukossa. Vaikka mikä tahansa graafi sallii k-dominoivan joukon, vain graafit, joiden vähimmäisaste on k-1, sallivat k-monikon hallitsevan joukon. Kuitenkin, vaikka graafi sallii k-monikon hallitsevan joukon, k-monikon hallitseva vähimmäisjoukko voi olla lähes k kertaa saman graafin k-monikon hallitseva minimijoukko [21] . Minimaalisen k-dominoivan joukon (1,7+log Δ)-approksimaatio löytyy myös polynomiajasta.

Domaattinen hajottelu on kärkien hajoamista  ei-päällekkäisiksi hallitseviksi joukoiksi. Domaattinen numero on domaattisen laajennuksen enimmäiskoko.

Ikuinen hallitseva joukko  on dominanssin dynaaminen versio, jossa dominoivan joukon D kärki v valitaan ja korvataan viereisellä u :lla ( u ei D :ssä) siten, että myös modifioitu joukko D on hallitseva ja tämä prosessi voi toistetaan mille tahansa äärelliselle kärkivaihtoehtojen sarjalle v.

Ohjelmisto hallitsevan vähimmäisjoukon löytämiseen

Nimi Lisenssi Käyttäjän kieli lyhyttä tietoa
openopt BSD Python Käyttää NetworkX- kaavioita . Voi käyttää ilmaisohjelmia ja kaupallisia paketteja. Katso yksityiskohtia ja esimerkkejä hallitsevalta sarjasivulta.

Katso myös

Muistiinpanot

  1. ↑ Gary, Johnson, 1982 , s. 235, Tehtävä TG2.
  2. ↑ Hedetniemi, Laskar, 1990 .
  3. ↑ Haynes, Hedetniemi, Slater, 1998a , s. kappale 2.
  4. ↑ Usein sekoitetaan termien suurin joukko ja maksimijoukko . Tässä artikkelissa suurin joukko ymmärretään joukoksi, jota ei voida laajentaa säilyttäen sen omaisuutta. Maksimijoukko on tietyn ominaisuuden omaava joukko, jolla on enimmäiskoko.
  5. ↑ Allan, Laskar, 1978 .
  6. ↑ Faudree, Flandrin, Ryjaček, 1997 .
  7. ↑ 1 2 Kann, 1992 , s. 108-109.
  8. ↑ Escoffier, Paschos, 2006 , s. 369-377.
  9. ↑ Raz, Safra, 1997 .
  10. ↑ Parekh, 1991 , s. 237-240.
  11. ↑ Papadimitriou, Yannakakis, 1991 , s. 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, Kyläläinen, 2012 .
  20. ↑ Klasing, Laforest, 2004 .
  21. ↑ Forster, 2013 .

Kirjallisuus