Ciklusvágó csúcsok halmaza

A gráfelméletben a gráf csúcsainak ciklusvágó halmaza azoknak a csúcsoknak a halmaza, amelyek eltávolítása ciklusok  töréséhez vezet . Más szóval, a ciklusvágó csúcskészlet legalább egy csúcsot tartalmaz bármely gráfciklusból. A ciklusvágó csúcshalmaz probléma egy NP-teljes probléma a számítási komplexitáselméletben . A probléma szerepel Karp 21 NP-teljes problémát tartalmazó listájában . A probléma széles körben alkalmazható operációs rendszerekben , adatbázisokban és VLSI -fejlesztésben .

Definíció

A ciklusvágó csúcshalmaz probléma  a következő megoldhatósági probléma :

A halmazhoz tartozó csúcsok gráfból való eltávolítása után megmaradó gráf egy generált erdő (iránytalan gráfokhoz, vagy generált irányított aciklikus gráf irányított gráfokhoz ). Így egy minimális ciklus keresése, amely levágja a gráf csúcsainak halmazát, egyenértékű egy maximálisan generált erdő ( irányított gráfok esetén maximálisan generált aciklikus gráf) keresésével .

NP-nehézség

Karp [1] megmutatta, hogy az irányított gráfok ciklusvágó csúcshalmazának problémája NP-teljes . A probléma továbbra is NP-teljes marad az irányított gráfok esetében, amelyeknél a bejövő és kimenő ívek maximális mértéke kettő, és az irányított plenáris gráfok esetében, amelyeknél a bejövő és kimenő ívek maximális mértéke három [2] . A Karp redukció magában foglalja a ciklusvágó csúcshalmaz probléma NP-teljességét is irányítatlan gráfokon, és a probléma NP-nehéz marad a maximum négyes fokú gráfokon. A ciklusvágó csúcshalmaz problémája polinomiális időben megoldható olyan gráfokon, amelyek maximális foka nem haladja meg a hármat [3] [4] .

Vegye figyelembe, hogy a ciklusok megszakításához a lehető legkevesebb él eltávolítása (iránytalan gráfban) egyenértékű egy feszítőfa megtalálásával , és ez a feladat polinomiális idő alatt elvégezhető . Ezzel szemben az a probléma, hogy egy irányított gráf éleit távolítsuk el annak érdekében, hogy aciklikussá tegyük , vagyis egy ciklusvágó ívhalmaz problémája NP-teljes [1] .

Pontos algoritmusok

A megfelelő NP-teljes optimalizálási probléma a minimális ciklusvágó csúcshalmaz méretének megtalálására O idő alatt (1,7347 n ) megoldható, ahol n  a gráf csúcsainak száma [5] . Valójában ez az algoritmus megtalálja a maximálisan generált erdőt, és ennek az erdőnek a komplementere lesz a kívánt csúcskészlet. A minimális ciklusvágó csúcshalmazok száma O -ra korlátozódik (1,8638 n ) [6] . Az irányított gráf minimális ciklusvágási halmazának problémája megoldható O* idő alatt (1,9977 n ), ahol n  az adott irányított gráf csúcsainak száma [7] . Az orientált és irányítatlan problémák paraméterezett változatai fix-parametrikusan megoldhatók [8] .

Közelítés

A probléma APX-teljes , ami közvetlenül következik a csúcsfedő probléma APX összetettségéből [9] és egy olyan közelítésből, amely megőrzi az L-redukciót a csúcsfedő problémából erre a problémára [1] . Az irányítatlan gráfok legismertebb algoritmusa kettős tényezővel rendelkezik [10] .

Szegélyek

Az Erdős-Pose tétel szerint a minimális ciklusvágó csúcshalmaz méretét egy adott gráfban a csúcs-diszjunkt ciklusok maximális számának logaritmikus tényezője korlátozza [11] .

Alkalmazások

Az operációs rendszerekben a hurokvágó csúcskészlet kiemelkedő szerepet játszik a holtpont -észlelésben . Az operációs rendszer várakozási grafikonján minden orientált hurok egy holtpontnak felel meg. Az összes holtpontból való kilépéshez néhány blokkolt folyamatot le kell állítani. A gráf minimális ciklusvágó csúcskészlete megfelel a megszakítandó folyamatok minimális számának [12]

Ezenkívül a csúcsvágási ciklusok halmazának vannak alkalmazásai a VLSI fejlesztésében [13] .

Jegyzetek

1. ↑ 1 2 3 Karp, 1972 .
2. ↑ Nem publikált eredmény Garey és Johnson miatt (Garey, Johnson), lásd Garey, Johnson, 1979 : GT7
3. ↑ Ueno, Kajitani, Gotoh, 1988 .
4. ↑ Li, Liu, 1999 .
5. ↑ Fomin, Villager, 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 . Lásd még Bafna, Berman, Fujito, 1999 egy azonos együtthatójú alternatív közelítési algoritmust.
11. ↑ Erdős, Pósa, 1965 .
12. ↑ Silberschatz, Galvin, Gagne, 2008 .
13. ↑ Festa, Pardalos, Resende, 2000 .

Irodalom

Kutatási cikkek és könyvek

• Vineet Bafna, Piotr Berman, Toshihiro Fujito. Egy 2-közelítési algoritmus az irányítatlan visszacsatolási csúcskészlet problémájához // SIAM Journal on Discrete Mathematics. - 1999. - T. 12 , sz. 3 . — 289–297. (elektronikus) . - doi : 10.1137/S0895480196305124 . .
• Ann Becker, Reuven Bar-Yehuda, Dan Geiger. Véletlenszerű algoritmusok a hurok kivágási problémájához // Journal of Artificial Intelligence Research . - 2000. - T. 12 . – S. 219–234 . - doi : 10.1613/jair.638 . - arXiv : 1106.0225 .
• Ann Becker, Dan Geiger. Pearl kondicionáló módszerének és mohó-szerű közelítő algoritmusainak optimalizálása a csúcs-visszacsatolási halmaz problémájára.  // Mesterséges intelligencia . - 1996. - T. 83 , sz. 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, Norvégia, 2010. június 21-23. / Haim Kaplan. - 2010. - T. 6139. - S. 93-104. — (Számítástechnikai előadásjegyzetek). - doi : 10.1007/978-3-642-13731-0_10 .
• Jianer Chen, Fedor V. Fomin, Yang Liu, Songjian Lu, Yngve Villanger. Továbbfejlesztett algoritmusok visszacsatolási csúcskészlet-problémákhoz // Journal of Computer and System Sciences . - 2008. - T. 74 , sz. 7 . - S. 1188-1198 . - doi : 10.1016/j.jcss.2008.05.002 .
• Jianer Chen, Yang Liu, Songjian Lu, Barry O'Sullivan, Igor Razgon. Rögzített paraméterű algoritmus az irányított visszacsatolási csúcskészlet problémájához // Journal of the ACM . - 2008. - T. 55 , sz. 5 . - doi : 10.1145/1411509.1411511 .
• Irit Dinur, Samuel Safra. A minimális csúcsfedő közelítésének keménységéről // Annals of Mathematics . - 2005. - T. 162 , sz. 1 . – S. 439–485 . - doi : 10.4007/annals.2005.162.439 .
• Erdős Pál, Pósa Lajos. Grafikonban foglalt független áramkörökről // 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. A minimális visszacsatolási csúcshalmaz problémájáról: egzakt és felsorolási algoritmusok. // Algorithmica . - 2008. - T. 52 , sz. 2 . – S. 293–307 . - doi : 10.1007/s00453-007-9152-0 .
• Fedor V. Fomin, Yngve Villanger. Proc. 27. Nemzetközi Szimpózium a Számítástudomány elméleti vonatkozásairól (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. Polinomiális algoritmus egy 3 szabályos egyszerű gráf minimális visszacsatolási csúcskészletének megtalálásához // Acta Mathematica Scientia. - 1999. - T. 19 , szám. 4 . – S. 375–381 .
• I. Razgon. Proceedings of the 10th Italian Conference on Theoretical Computer Science / Giuseppe F. Italiano, Eugenio Moggi, Luigi Laura. – World Scientific, 2007. – P. 70–81.
• Shuichi Ueno, Yoji Kajitani, Shin'ya Gotoh. A nem elválasztható független halmazproblémáról és a visszacsatolási halmaz problémájáról olyan gráfokhoz, amelyek csúcsfoka nem haladja meg a hármat // Discrete Mathematics . - 1988. - T. 72 , sz. 1-3 . — S. 355–360 . - doi : 10.1016/0012-365X(88)90226-9 .

Tankönyvek és ismertető cikkek

• P. Festa, P. M. Pardalos, M.G.C. Resende. Handbook of Combinatorial Optimization, Supplement vol. A / D.-Z. Du, P. M. Pardalos. - Kluwer Academic Publishers, 2000. - S. 209-259.
• Michael R. Garey, David S. Johnson. Számítógépek és kezelhetetlenség: Útmutató az NP-teljesség elméletéhez . - W. H. Freeman, 1979. - ISBN 0-7167-1045-5 .
• Abraham Silberschatz, Peter Baer Galvin, Greg Gagne. Az operációs rendszer fogalmai. – John Wiley & Sons. Inc., 2008. - ISBN 978-0-470-12872-5 .