Cyklické řezání množiny vrcholů
V teorii grafů je soubor vrcholů grafu ořezávající cyklus souborem vrcholů, jejichž odstranění vede k přerušení cyklů . Jinými slovy, sada vrcholů pro řezání cyklu obsahuje alespoň jeden vrchol z libovolného cyklu grafu. Problém množiny vrcholů oříznutí cyklu je NP-úplný problém v teorii výpočetní složitosti . Problém je zahrnut v Karpově seznamu 21 NP-úplných problémů . Problém má široké uplatnění v operačních systémech , databázích a vývoji VLSI .
Definice
Problém množiny vrcholů pro řezání cyklu je následující problém řešitelnosti :
Dané: (neorientovaný nebo řízený) graf a kladné číslo . Otázka: Existuje podmnožina , pro kterou , taková, že s odstraněnými vrcholy patřícími do , neobsahuje cykly ?
Graf zbývající po odstranění vrcholů patřících do množiny z grafu je vygenerovaný les (pro neorientované grafy, nebo vygenerovaný orientovaný acyklický graf pro orientované grafy ). Hledání minimálního cyklu, který vyřízne množinu vrcholů v grafu, je tedy ekvivalentní hledání maximálně vygenerovaného lesa (respektive maximálně vygenerovaného acyklického grafu v případě orientovaných grafů ).
![{\displaystyle G[V\setminus X]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1166277c8d75dce9d8ea1f3ede58bd79c083211d)
NP-obtížnost
Karp [1] ukázal, že problém množiny vrcholů ořezávání cyklu pro orientované grafy je NP-úplný . Problém zůstává NP-úplný pro orientované grafy s maximálním stupněm příchozích a odchozích oblouků rovným dvěma a pro orientované plenární grafy s maximálním stupněm příchozích a odchozích oblouků rovným třem [2] . Karpova redukce také implikuje NP-úplnost problému množiny vrcholů ořezávání cyklu na neorientovaných grafech a problém zůstává NP-těžký na grafech s maximálním stupněm čtyři. Úlohu cyklicky řezající množiny vrcholů lze řešit v polynomiálním čase na grafech s maximálním stupněm nepřesahujícím tři [3] [4] .
Všimněte si, že úkol odstranit co nejméně hran pro přerušení cyklů (v neorientovaném grafu) je ekvivalentní hledání kostry a tento úkol lze dokončit v polynomiálním čase . Naproti tomu problém odstranění hran z orientovaného grafu , aby byl acyklický , tedy problém cyklicky řezající sady oblouků , je NP-úplný [1] .
Přesné algoritmy
Odpovídající NP-úplný optimalizační problém nalezení velikosti minimální množiny vrcholů ořezávání cyklu lze vyřešit v čase O (1,7347 n ), kde n je počet vrcholů v grafu [5] . Ve skutečnosti tento algoritmus najde maximum generovaného lesa a doplňkem tohoto lesa bude požadovaná sada vrcholů. Počet minimálních množin vrcholů ořezávání cyklu je omezen na O (1,8638 n ) [6] . Problém minimální množiny řezu cyklu pro orientovaný graf lze vyřešit v čase O* (1,9977 n ), kde n je počet vrcholů v daném orientovaném grafu [7] . Parametrizované verze orientovaných a neorientovaných problémů jsou pevně-parametricky řešitelné [8] .
Aproximace
Problém je APX-complete , což přímo vyplývá z APX složitosti problému pokrytí vrcholů [9] a existence aproximace, která zachovává L-redukce z problému pokrytí vrcholů na tento problém [1] . Nejznámější algoritmus pro neorientované grafy má faktor dva [10] .
Hranice
Podle Erdős-Poseovy věty je velikost minimální množiny vrcholů ořezávání cyklem omezena logaritmickým faktorem maximálního počtu vrcholově disjunktních cyklů v daném grafu [11] .
Aplikace
V operačních systémech hraje sada vrcholů pro řezání smyčky významnou roli při detekci uváznutí . V grafu čekání operačního systému každá orientovaná smyčka odpovídá uváznutí. Chcete-li ukončit všechna zablokování, musí být některé zablokované procesy ukončeny. Minimální množina vrcholů pro řezání cyklu v grafu odpovídá minimálnímu počtu procesů, které by měly být přerušeny [12]
Kromě toho má sada cyklů řezání vrcholů uplatnění při vývoji VLSI [13] .
Poznámky
- ↑ 1 2 3 Karp, 1972 .
- ↑ Nepublikovaný výsledek kvůli Gareymu a Johnsonovi (Garey, Johnson), viz Garey, Johnson, 1979 : GT7
- ↑ Ueno, Kajitani, Gotoh, 1988 .
- ↑ Li, Liu, 1999 .
- ↑ Fomin, Villager, 2010 .
- ↑ Fomin, Gaspers, Pyatkin, Razgon, 2008 .
- ↑ Razgon, 2007 .
- ↑ Chen, Liu, Lu, O'Sullivan, Razgon, 2008 .
- ↑ Dinur, Safra, 2005 .
- ↑ Becker, Geiger, 1996 . Viz také Bafna, Berman, Fujito, 1999 pro alternativní aproximační algoritmus se stejným koeficientem.
- ↑ Erdős, Posa, 1965 .
- ↑ Silberschatz, Galvin, Gagne, 2008 .
- ↑ Festa, Pardalos, Resende, 2000 .
Literatura
Výzkumné články a knihy
- Vineet Bafna, Piotr Berman, Toshihiro Fujito. Algoritmus 2 aproximace pro problém s neřízenou zpětnou vazbou vertex set // SIAM Journal on Discrete Mathematics. - 1999. - T. 12 , no. 3 . — s. 289–297 (elektronické) . - doi : 10.1137/S0895480196305124 . .
- Ann Becker, Reuven Bar-Yehuda, Dan Geiger. Randomizované algoritmy pro problém cutset smyčky // Journal of Artificial Intelligence Research . - 2000. - T. 12 . — S. 219–234 . - doi : 10.1613/jair.638 . - arXiv : 1106.0225 .
- Ann Becker, Dan Geiger. Optimalizace Pearlovy metody kondicionování a chamtivých aproximačních algoritmů pro problém množiny zpětné vazby vertexu. // Umělá inteligence . - 1996. - T. 83 , no. 1 . — S. 167–188 . - doi : 10.1016/0004-3702(95)00004-6 .
- Yixin Cao, Jianer Chen, Yang Liu. Proč. 12. skandinávské symposium a workshopy o teorii algoritmů (SWAT 2010), Bergen, Norsko, 21.–23. června 2010 / Haim Kaplan. - 2010. - T. 6139. - S. 93-104. — (Poznámky z informatiky). - doi : 10.1007/978-3-642-13731-0_10 .
- Jianer Chen, Fedor V. Fomin, Yang Liu, Songjian Lu, Yngve Villanger. Vylepšené algoritmy pro problémy s množinou vertexů zpětné vazby // Journal of Computer and System Sciences . - 2008. - T. 74 , č. 7 . - S. 1188-1198 . - doi : 10.1016/j.jcss.2008.05.002 .
- Jianer Chen, Yang Liu, Songjian Lu, Barry O'Sullivan, Igor Razgon. Algoritmus s pevným parametrem pro problém se souborem vertexů s řízenou zpětnou vazbou // Journal of the ACM . - 2008. - T. 55 , no. 5 . - doi : 10.1145/1411509.1411511 .
- Irit Dinur, Samuel Safra. O tvrdosti aproximujícího minimálního pokrytí vrcholů // Annals of Mathematics . - 2005. - T. 162 , čís. 1 . — S. 439–485 . - doi : 10.4007/annals.2005.162.439 .
- Paul Erdős, Lajos Posa. Na nezávislých obvodech obsažených v grafu // 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. Problém s minimální množinou vertexů zpětné vazby: přesné a výčtové algoritmy. // Algoritmika . - 2008. - T. 52 , č. 2 . — S. 293–307 . - doi : 10.1007/s00453-007-9152-0 .
- Fedor V. Fomin, Yngve Villager. Proč. 27. mezinárodní symposium o teoretických aspektech informatiky (STACS 2010). - 2010. - V. 5. - S. 383–394. - (Leibniz International Proceedings in Informatics (LIPIcs)). - doi : 10.4230/LIPIcs.STACS.2010.2470 .
- Richard M. Karp. Proč. Symposium on Complexity of Computer Computations, IBM Thomas J. Watson Res. Center, Yorktown Heights, NY. - New York: Plénum, 1972. - S. 85-103.
- Deming Li, Yanpei Liu. Polynomiální algoritmus pro nalezení minimální sady vertexů zpětné vazby 3-regulárního jednoduchého grafu // Acta Mathematica Scientia. - 1999. - T. 19 , vydání. 4 . — S. 375–381 .
- I. Razgon. Sborník příspěvků z 10. italské konference teoretické informatiky / Giuseppe F. Italiano, Eugenio Moggi, Luigi Laura. — World Scientific, 2007. — S. 70–81.
- Shuichi Ueno, Yoji Kajitani, Shin'ya Gotoh. Na neseparační nezávislou množinovou úlohu a zpětnovazební množinovou úlohu pro grafy s žádným vrcholovým stupněm vyšším než tři // Diskrétní matematika . - 1988. - T. 72 , no. 1-3 . — S. 355–360 . - doi : 10.1016/0012-365X(88)90226-9 .
Učebnice a přehledové články
- P. Festa, P.M. Pardalos, M.G.C. Resende. Handbook of Combinatorial Optimization, Supplement sv. A/D.-Z. Du, P. M. Pardalos. - Kluwer Academic Publishers, 2000. - S. 209-259.
- Michael R. Garey, David S. Johnson. Počítače a neovladatelnost: Průvodce teorií NP-úplnosti . - W.H. Freeman, 1979. - ISBN 0-7167-1045-5 .
- Abraham Silberschatz, Peter Baer Galvin, Greg Gagne. Koncepce operačního systému. — John Wiley & Sons. Inc, 2008. - ISBN 978-0-470-12872-5 .