Itsenäisen joukon ongelma

Itsenäinen joukkotehtävä kuuluu NP-täydellisten tehtävien luokkaan graafiteorian alalla . Vastaa klikkiongelmaa .

Määritelmät

Graafin kärkijoukkoa kutsutaan itsenäiseksi , jos tämän joukon kahta kärkeä ei ole yhdistetty reunalla. Toisin sanoen tämän joukon indusoima aligraafi koostuu eristetyistä pisteistä. Joskus myös sanotaan, että graafin jokainen reuna osuu korkeintaan yhteen itsenäisen joukon kärkeen. Tunnistusongelma (ratkaisevuusongelma) näyttää tältä: onko annetulla graafilla G riippumaton joukko, jonka koko on k ? Sitä vastaava optimointitehtävä, joka tunnetaan myös nimellä riippumaton joukkoongelma , muotoillaan seuraavasti: annetussa graafissa G on löydettävä riippumaton joukko, jonka koko on maksimi. Tätä kokoa kutsutaan riippumattomuusluvuksi , sisäisen tiheyden numeroksi tai löysyysluvuksi ja sitä merkitään [1] [2] .

Tätä ongelmaa kutsutaan joskus suurimman itsenäisen joukon löytämiseksi . Tätä käsitettä ei pidä sekoittaa riippumattomaan maksimijoukkoon tai inkluusiolla olevaan enimmäisriippumattomaan joukkoon , joka määritellään sellaiseksi itsenäiseksi pistejoukoksi, että kun siihen lisätään yksi (mikä tahansa) alkuperäisen graafin kärki, se lakkaa olla riippumattomia (yleensä tällaisia ​​joukkoja voi olla useita ja eri kokoisia). Inkluusio-maksimaalinen riippumaton joukko ei suinkaan ole aina suurin. Samanaikaisesti jokainen suurin itsenäinen joukko on määritelmän mukaan myös maksimaalinen inkluusiona. Löytääkseen (jonkin) suurimman riippumattoman joukon inkluusion suhteen voidaan käyttää ahneita algoritmeja , jotka kulkevat polynomiajassa, kun taas suurimman riippumattoman joukon ongelma kuuluu NP-täydellisten tehtävien luokkaan.

Inkluusio-maksimaalinen riippumaton joukko on hallitseva joukko . Mikä tahansa graafi sisältää enintään 3 n /3 inkluusio-maksimiriippumatonta joukkoa [3] , mutta useimmissa kaavioissa niitä on paljon vähemmän.

Inkluusio-maksimiriippumattomien joukkojen lukumäärä n kärjen sykleissä on Perrin-lukuja ja inkluusio-maksimiriippumattomien joukkojen lukumäärä poluilla , joissa on n kärkeä, saadaan Padovan-sekvenssistä [4] . Siten molemmat luvut ovat verrannollisia plastisen luvun 1,324718 potenssiin .

Pienin itsenäinen osajoukko graafissa on mikä tahansa tämän graafin kärki.

Suhde muihin kaavioparametreihin

Joukko on itsenäinen silloin ja vain, jos se on klikki graafin komplementissa , joten nämä kaksi käsitettä täydentävät toisiaan. Riittävän suurilla kaavioilla ilman suuria klikkejä on suuria itsenäisiä joukkoja, mikä on Ramseyn teorian tutkimuksen aihe .

Joukko on itsenäinen silloin ja vain, jos sen komplementti on vertex cover . Riippumattomuusluvun ja kärjen peittoluvun summa on yhtä suuri kuin graafin kärkien lukumäärä (ensimmäinen Gallai-identiteetti ).

Graafin kärkien väritys vastaa sen kärkien jakoa itsenäisiin osajoukkoon. Siksi pisteiden värittämiseen vaadittava värien vähimmäismäärä, kromaattinen luku , ei ole pienempi kuin pisteiden lukumäärän ja riippumattomuusluvun osamäärä .

Kaksiosaisissa graafeissa , joissa ei ole eristettyjä pisteitä, pisteiden lukumäärä suurimmassa riippumattomassa joukossa on yhtä suuri kuin reunojen lukumäärä pienimmässä reunasuojassa ( Königin lauseen seuraus ).

Etsi itsenäisiä sarjoja

Tietojenkäsittelytieteessä tutkitaan useita riippumattomiin liittyviä laskennallisia ongelmia :

Ensimmäiset kolme ongelmaa ovat tärkeitä käytännön sovelluksissa, kun taas viimeinen on tärkeä NP-täydellisyyden teorialle itsenäisiin joukkoihin liittyvissä ongelmissa.

Riippumaton joukkoongelma ja klikkiongelma ovat duaalisia: G :n klikki  on itsenäinen joukko G :n komplementissa ja päinvastoin. Siten monia laskennallisia tuloksia voidaan soveltaa yhtä hyvin molempiin ongelmiin. Esimerkiksi klikkiongelmaan liittyvillä tuloksilla on seuraavat seuraukset:

Suurimman itsenäisen joukon löytäminen

Tätä ongelmaa kutsutaan joskus " vertex-pakkaukseksi ".

Suurin riippumaton joukko - ongelma ja suurin klikkiongelma ovat polynomiekvivalentteja – suurin riippumaton joukko löytyy etsimällä maksimiklikki graafin komplementista, joten monet kirjoittajat eivät erityisemmin välitä näiden kahden ongelman erottamisesta. Molemmat tehtävät ovat NP-täydellisiä, joten niitä ei todennäköisesti ratkaista polynomiajassa. Suurin riippumattoman joukon ongelma voidaan kuitenkin ratkaista tehokkaammin kuin O( n 2  2 n ) -ajassa, mikä tuottaa tyhjentävän haun , joka testaa kaikki pisteiden osajoukot nähdäkseen, ovatko ne riippumattomia joukkoja. Robsonin algoritmi [6] ratkaisee tehtävän O(2 0.276 n ) ajassa käyttämällä eksponentiaalista avaruutta. Jos koolle on asetettu raja (polynomiavaruus), on olemassa algoritmi ajassa O*(1,2127 n ) [7] .

Huolimatta suurimman klikkin ja suurimman riippumattoman joukon välisestä läheisestä suhteesta mielivaltaisessa graafissa, riippumattoman joukon ja klikkin löytämisen ongelmat voivat erota merkittävästi, kun ne ratkaistaan ​​erityisellä graafiluokalla. Esimerkiksi harvoille graafeille (graafit, joissa reunojen määrä missään aligraafissa ei ole suurempi kuin kärkien lukumäärä kerrottuna jollain vakiolla) suurimmalla klikkilla on rajoitettu koko ja se löytyy täsmälleen lineaarisessa ajassa [8] . Kuitenkin samoilla graafiluokilla tai jopa tiukempien rajoitusten tapauksessa graafiluokalle, jolla on rajoitettu aste, suurimman itsenäisen joukon haku on MAXSNP-täydellinen , mikä tarkoittaa, että jollekin vakiolle c (riippuen asteella) NP - on vaikea löytää likimääräistä ratkaisua, joka eroaa kertoimella c optimaalisesta [9] . Tehokkaita likimääräisiä algoritmeja kuitenkin tunnetaan, mutta niiden taattu tehokkuus on tätä kynnystä huonompi. Esimerkiksi ahne algoritmi luo inkluusio-maksimaalisen riippumattoman joukon valitsemalla jokaisessa vaiheessa minimiasteisen kärjen ja poistamalla sen naapurit. Tämä algoritmi saavuttaa taatun tehokkuuden (Δ+2)/3 kaavioissa, joiden maksimiaste on Δ [10] .

Joissakin graafiluokissa (mukaan lukien graafit ilman kynsiä [11] ja täydelliset graafit [12] ; myös puut kuuluvat jälkimmäiseen luokkaan ) suurin itsenäinen joukko löytyy polynomiajasta. Tasokaavioissa suurin itsenäinen joukkoongelma pysyy NP-täydellinen tarkalle ratkaisulle, mutta se voidaan approksimoida millä tahansa taatulla tehokkuudella c  < 1 polynomiajassa. Samanlaisia ​​likimääräisiä polynomiaikakaavioita on missä tahansa vähäsuljettujen graafien perheessä [13] [14] .

Kaksiosaisissa graafeissa kaikki kärjet, jotka eivät ole pienimmässä kärjen peitossa, voidaan sisällyttää suurimpaan riippumattomaan joukkoon (katso Königin lause ). Siksi suurin itsenäinen joukko voidaan löytää käyttämällä algoritmia, joka etsii suurimmat vastaavuudet kaksiosaisista kaavioista.

Hae inkluusio-maksimi riippumattomia joukkoja

Kaikki inkluusio-maksimaaliset riippumattomat joukot löytyvät O(3 n /3 ) -ajassa.

Ohjelmisto itsenäisten joukkojen löytämiseen

Nimi Lisenssi API-kieli Kuvaus
kuvio GPL C, Python, R, Ruby tarkka ratkaisu
VerkkoX BSD Python likimääräinen ratkaisu, katso menettely max_independent_set
openopt BSD Python tarkat ja likimääräiset ratkaisut, kyky määrittää kärjet, jotka tulisi sisällyttää / jättää pois. Katso lisätietoja ja esimerkkejä STAB -luokasta

Suurin itsenäinen joukko puussa

Jos annettu graafi on puu , niin riippumaton joukko-ongelma ratkaistaan ​​tehokkaasti dynaamisen ohjelmoinnin avulla .

Tehtävän optimaalinen alirakenne

Puun rakenne itsessään ehdottaa ratkaisua ongelmaan. Nimittäin merkitsemme mitä tahansa kärkeä puun juureksi ja kutsumme sitä . Olkoon alipuun suurimman riippumattoman kärkijoukon koko, jonka juuri on kärki . Sitten vastaus ongelmaan on .

On helppo nähdä, että jos sisällytetään kärki u suurimpaan riippumattomaan joukkoon, niin sen kardinaliteetti kasvaa 1:llä, mutta emme voi ottaa sen lapsia (koska ne on liitetty reunalla kärkeen u ); jos emme sisällytä tätä kärkeä, niin suurimman itsenäisen joukon kardinaliteetti on yhtä suuri kuin tämän kärjen riippumattomien lapsijoukkojen kokojen summa. On vain valittava suurin näistä kahdesta vaihtoehdosta, jotta ongelmaan saadaan ratkaisu:

jossa lapsenlapsi tarkoittaa mitä tahansa kärjen "lastenlasta" ja lapsi tarkoittaa mitä tahansa kärjen jälkeläistä.

Pseudokoodi

Katsomme, että yläosassa u on tallennettu :

funktio get_independent_set(solmu u) { jos I(u) on jo laskettu, niin palauttaa I(u) // joukon kardinaliteetti, joka voidaan saada, jos emme ota kärkeä u lapset_summa = 0 // joukon kardinaliteetti, joka voidaan saada ottamalla kärki u lastenlasten_summa = 0 // kiertää kaikkien lasten läpi for i := 1 to child_num do lasten_summa = lasten_summa + hanki_riippumaton_joukko(lapset[i]) // kiertää kaikkien lastenlasten läpi for i:= 1 to grandchildren_num lastenlasten_summa = lastenlasten_summa + hanki_itsenäinen_joukko(lastenlapset[i]) // muista, jotta et laske uudelleen I(u) = max(1 + lastenlasten_summa, lasten_summa) palauta I(u) }

Kutsuminen get_independent_set( r ) antaa vastauksen ongelmaan. Algoritmin suoritusaika on ilmeisesti O (|V| + |E|).

Katso myös

Muistiinpanot

  1. ↑ Chris Godsil, Gordon Royle. . Algebrallinen graafiteoria. - New York: Springer , 2001. - ISBN 0-387-95220-9 .  - s. 3.
  2. ↑ Evstigneev V. A., Kasyanov V. N. . Tietojenkäsittelytieteen graafien sanakirja. - Novosibirsk, 200. - (Ohjelmien suunnittelu ja optimointi, numero 17). - ISBN 978-591124-036-3 .
  3. ↑ Moon J. W., Moser L.  Klikeistä kaavioissa // Israel Journal of Mathematics. - 1965. - Voi. 3, ei. 1. - s. 23–28. - doi : 10.1007/BF02760024 .
  4. ↑ Furedi, Zoltan. Maksimiriippumattomien joukkojen lukumäärä yhdistetyissä kaavioissa // Journal of Graph Theory. - 1987. - Voi. 11, ei. 4. - P. 463-470. - doi : 10.1002/jgt.3190110403 .
  5. ↑ Rusovin ja Zakharovan artikkelista alla: Viime aikoina heuristiset algoritmit, eli algoritmit, jotka silti mahdollistavat NP-täydellisen ongelman ratkaisemisen, mutta joissain virheissä, ovat olleet eniten kiinnostavia tällaisten ongelmien ratkaisemisessa. Pääkriteerit heuristisen algoritmin arvioinnissa ovat "aikatehokkuus" ja virhe suhteessa tarkkaan algoritmiin.
  6. ↑ Robson J. M.  Algoritmit enimmäisriippumattomille joukoille // Journal of Algorithms. - 1986. - Voi. 7, ei. 3. - s. 425-440. - doi : 10.1016/0196-6774(86)90032-5 .
  7. ↑ Nicolas Bourgeois, Bruno Escoffier, Vangelis Th. Paschos, Johan M. M. van Rooij. . Alhaalta ylös -menetelmä ja nopeat algoritmit MAX INDEPENDENT SETille // Algoritmiteoria—SWAT 2010 . - Berlin: Springer , 2010. - (Luentomuistiinpanot tietojenkäsittelytieteessä, osa 6139). - doi : 10.1007/978-3-642-13731-0_7 .  — s. 62–73.
  8. ↑ Chiba N., Nishizeki T.  Arboricity ja aligraafien listausalgoritmit // SIAM Journal on Computing . - 1985. - Voi. 14, ei. 1. - s. 210-223. - doi : 10.1137/0214017 .
  9. ↑ Piotr Berman, Toshihiro Fujito. . Independent-joukkoongelman approksimaatioominaisuuksista 3. asteen kaavioille // Neljäs kansainvälinen algoritmeja ja tietorakenteita käsittelevä työpaja. - Springer , 1995. - (Lecture Notes in Computer Science, voi. 995). - doi : 10.1007/3-540-60220-8_84 .  - s. 449-460.
  10. ↑ Halldórsson M. M., Radhakrishnan J.  Ahneus on hyvä: Riippumattomien joukkojen approksimointi harvassa ja rajoitetun asteen graafissa // Algorithmica . - 1997. - Voi. 18, ei. 1. - s. 145-163. - doi : 10.1007/BF02523693 . .
  11. ↑ Sbihi, 1980 .
  12. ↑ Grötschel, Lovász, Schrijver, 1988 .
  13. ↑ Brenda S. Baker. Approksimointialgoritmit NP-täydellisiin ongelmiin tasokaavioissa // Journal of the ACM . - 1994. - Voi. 41, nro. 1. - s. 153-180. - doi : 10.1145/174644.174650 .
  14. ↑ Martin Grohe. Paikallinen puunleveys, poissuljetut alamerkit ja approksimaatioalgoritmit // Combinatorica . - 2003. - Voi. 23, ei. 4. - P. 613-632. - doi : 10.1007/s00493-003-0037-9 .

Kirjallisuus

Linkit

 NP-täydellisiä ongelmia
Pinoamisen (pakkauksen) maksimointiongelma
graafiteorian
joukkoteoria
Algoritmiset ongelmat
Logiikkapelejä
ja pulmia