Kiertopisteiden joukko

Graafiteoriassa graafin syklin katkaiseva kärkijoukko on  joukko pisteitä, joiden poistaminen johtaa syklien katkeamiseen . Toisin sanoen syklinleikkauspistejoukko sisältää vähintään yhden kärjen mistä tahansa graafisyklistä. Syklileikkauspistejoukkoongelma on laskennallisen monimutkaisuusteorian NP-täydellinen ongelma . Ongelma sisältyy Karpin 21 NP-täydellisen ongelman luetteloon . Ongelmalla on laaja sovellus käyttöjärjestelmissä , tietokantoissa ja VLSI -kehityksessä .

Määritelmä

Syklileikkauspistejoukon ongelma  on seuraava ratkaistavuusongelma :

Graafi , joka jää jäljelle sen jälkeen , kun joukkoon kuuluvat pisteet on poistettu graafista, on generoitu metsä (suuntaamattomille graafiille tai generoitu suunnattu asyklinen graafi suunnatuille graafille ). Siten minimijakson etsiminen, joka katkaisee joukon pisteitä graafista, vastaa suurimman generoidun metsän etsimistä (vastaavasti suurimman generoidun asyklisen graafin, jos kyseessä ovat suunnatut graafit ).

NP-vaikeus

Karp [1] osoitti, että suunnattujen graafien kiertoleikkauspistejoukkoongelma on NP-täydellinen . Ongelma on edelleen NP-täydellinen suunnatuille kaavioille, joiden sisääntulevien ja lähtevien kaarien maksimiaste on kaksi, ja suunnatuissa täyskaavioissa, joiden sisääntulevien ja lähtevien kaarien maksimiaste on kolme [2] . Karp-pelkistys merkitsee myös kiertoleikkauspistejoukon ongelman NP-täydellisyyttä suuntaamattomissa graafis- sa, ja ongelma pysyy NP-kovana graafisissa maksimiasteen neljässä. Piikkien jaksottaisen joukon ongelma voidaan ratkaista polynomiajassa graafisilla, joiden maksimiaste on enintään kolme [3] [4] .

Huomaa, että tehtävä poistaa mahdollisimman vähän reunoja syklien katkaisemiseksi (ohjaamattomassa graafissa) vastaa virittävän puun löytämistä , ja tämä tehtävä voidaan suorittaa polynomiajassa . Sitä vastoin ongelma, joka koskee reunojen poistamista suunnatusta graafista sen tekemiseksi asykliseksi , eli syklin kaarien joukon ongelma , on NP-täydellinen [1] .

Tarkat algoritmit

Vastaava NP-täydellinen optimointiongelma pisteiden syklinleikkauksen minimijoukon koon löytämiseksi voidaan ratkaista ajassa O (1,7347 n ), missä n  on graafin kärkien lukumäärä [5] . Itse asiassa tämä algoritmi löytää suurimman generoidun metsän ja tämän metsän komplementti on haluttu kärkijoukko. Minimaalisten työkiertoleikkauspistejoukkojen määrä on rajoitettu O : een (1,8638 n ) [6] . Suunnatun graafin minimijaksoleikkausjoukon ongelma voidaan ratkaista ajassa O* (1,9977 n ), missä n  on pisteiden lukumäärä tietyssä suunnatussa graafissa [7] . Orientoitujen ja suuntaamattomien ongelmien parametroidut versiot ovat kiinteäparametrisesti ratkaistavissa [8] .

Arviointi

Ongelma on APX-täydellinen , mikä seuraa suoraan kärjenpeiteongelman APX-monimutkaisuudesta [ 9] ja approksimaatiosta, joka säilyttää L-reduktion kärjenpeiteongelmasta tähän ongelmaan [1] . Tunnetuimmalla ohjaamattomien graafien algoritmilla on kerroin kaksi [10] .

Reunat

Erdős-Pose-lauseen mukaan pisteen minimisyklinleikkausjoukon kokoa rajoittaa tietyn graafin piste-hajojajaksojen maksimimäärän logaritminen kerroin [11] .

Sovellukset

Käyttöjärjestelmissä silmukkaa leikkaavalla kärkijoukolla on merkittävä rooli lukkiutuman havaitsemisessa . Käyttöjärjestelmän odotuskaaviossa jokainen suunnattu silmukka vastaa umpikujaa. Kaikista lukkiutumisesta poistumiseksi jotkin estetyt prosessit on lopetettava. Graafin syklinleikkauspisteiden minimijoukko vastaa niiden prosessien vähimmäismäärää, jotka tulisi keskeyttää [12]

Lisäksi kärkipisteiden leikkaussyklien joukolla on sovelluksia VLSI :n kehityksessä [13] .

Muistiinpanot

1. ↑ 1 2 3 Karp, 1972 .
2. ↑ Julkaisematon tulos Gareyn ja Johnsonin vuoksi (Garey, Johnson), katso Garey, Johnson, 1979 : GT7
3. ↑ Ueno, Kajitani, Gotoh, 1988 .
4. ↑ Li, Liu, 1999 .
5. ↑ Fomin, Villagenger, 2010 .
6. ↑ Fomin, Gaspers, Pyatkin, Razgon, 2008 .
7. ↑ Razgon, 2007 .
8. ↑ Chen, Liu, Lu, O'Sullivan, Razgon, 2008 .
9. ↑ Dinur, Safra, 2005 .
10. ↑ Becker, Geiger, 1996 . Katso myös Bafna, Berman, Fujito, 1999 vaihtoehtoisesta approksimaatioalgoritmista samalla kertoimella.
11. ↑ Erdős, Posa, 1965 .
12. ↑ Silberschatz, Galvin, Gagne, 2008 .
13. ↑ Festa, Pardalos, Resende, 2000 .

Kirjallisuus

Tutkimusartikkeleita ja kirjoja

• Vineet Bafna, Piotr Berman, Toshihiro Fujito. 2-approksimaatioalgoritmi ohjaamattoman takaisinkytkentäpistejoukon ongelmalle // SIAM Journal on Discrete Mathematics. - 1999. - T. 12 , no. 3 . — s. 289–297 (sähköinen) . - doi : 10.1137/S0895480196305124 . .
• Ann Becker, Reuven Bar-Yehuda, Dan Geiger. Satunnaistetut algoritmit silmukan leikkausjoukon ongelmaan // Journal of Artificial Intelligence Research . - 2000. - T. 12 . — S. 219–234 . - doi : 10.1613/jair.638 . - arXiv : 1106.0225 .
• Ann Becker, Dan Geiger. Pearlin ehdollistamismenetelmän ja ahneiden approksimaatioalgoritmien optimointi vertex-palautejoukon ongelmalle.  // Tekoäly . - 1996. - T. 83 , no. 1 . — S. 167–188 . - doi : 10.1016/0004-3702(95)00004-6 .
• Yixin Cao, Jianer Chen, Yang Liu. Proc. 12th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2010), Bergen, Norja, 21.-23. kesäkuuta 2010 / Haim Kaplan. - 2010. - T. 6139. - S. 93–104. — (Luentomuistiinpanot tietojenkäsittelytieteestä). - doi : 10.1007/978-3-642-13731-0_10 .
• Jianer Chen, Fedor V. Fomin, Yang Liu, Songjian Lu, Yngve Villanger. Parannetut algoritmit takaisinkytkentäpisteiden joukkoongelmiin // Journal of Computer and System Sciences . - 2008. - T. 74 , no. 7 . - S. 1188-1198 . - doi : 10.1016/j.jcss.2008.05.002 .
• Jianer Chen, Yang Liu, Songjian Lu, Barry O'Sullivan, Igor Razgon. Kiinteäparametrinen algoritmi suunnatun takaisinkytkennän kärkijoukon ongelmalle // Journal of the ACM . - 2008. - T. 55 , no. 5 . - doi : 10.1145/1411509.1411511 .
• Irit Dinur, Samuel Safra. Huippupisteen vähimmäispeitteen lähentämisen kovuudesta // Annals of Mathematics . - 2005. - T. 162 , no. 1 . — S. 439–485 . - doi : 10.4007/annals.2005.162.439 .
• Paul Erdős, Lajos Posa. Riippumattomista piireistä, jotka sisältyvät kuvaajaan // Canadian Journal of Mathematics . - 1965. - T. 17 . — S. 347–352 . - doi : 10.4153/CJM-1965-035-8 .
• Fedor V. Fomin, Serge Gaspers, Artem Pyatkin, Igor Razgon. Vähimmäispalautepistejoukon ongelmasta: tarkat ja numerointialgoritmit. // Algorithmica . - 2008. - T. 52 , no. 2 . — S. 293–307 . - doi : 10.1007/s00453-007-9152-0 .
• Fedor V. Fomin, Yngve Villanger. Proc. 27. kansainvälinen symposium tietojenkäsittelytieteen teoreettisista näkökohdista (STACS 2010). - 2010. - V. 5. - S. 383–394. - (Leibniz International Proceedings in Informatics (LIPIcs)). - doi : 10.4230/LIPIcs.STACS.2010.2470 .
• Richard M. Karp. Proc. Symposium on Complexity of Computer Computations, IBM Thomas J. Watson Res. Center, Yorktown Heights, NY. - New York: Plenum, 1972. - S. 85-103.
• Deming Li, Yanpei Liu. Polynomialgoritmi 3-säännöllisen yksinkertaisen graafin minimipalautepistejoukon löytämiseksi // Acta Mathematica Scientia. - 1999. - T. 19 , numero. 4 . — S. 375–381 .
• I. Razgon. Proceedings of the 10. Italian Conference on Theoretical Computer Science / Giuseppe F. Italiano, Eugenio Moggi, Luigi Laura. — World Scientific, 2007. — S. 70–81.
• Shuichi Ueno, Yoji Kajitani, Shin'ya Gotoh. Erottelemattomasta riippumattoman joukon ongelmasta ja takaisinkytkentäjoukon ongelmasta graafiille, joiden kärkipiste ei ylitä kolmea // Diskreetti matematiikka . - 1988. - T. 72 , no. 1-3 . — S. 355–360 . - doi : 10.1016/0012-365X(88)90226-9 .

Oppikirjoja ja arvosteluartikkeleita

• P. Festa, P.M. Pardalos, M.G.C. Resende. Handbook of Combinatorial Optimization, Supplement voi. A/D.-Z. Du, P. M. Pardalos. - Kluwer Academic Publishers, 2000. - S. 209-259.
• Michael R. Garey, David S. Johnson. Tietokoneet ja hallitsemattomuus: opas NP-täydellisyyden teoriaan . - W.H. Freeman, 1979. - ISBN 0-7167-1045-5 .
• Abraham Silberschatz, Peter Baer Galvin, Greg Gagne. Käyttöjärjestelmän käsitteet. - John Wiley & Sons. Inc, 2008. - ISBN 978-0-470-12872-5 .