Körlefogó csúcshalmaz

A matematika, azon belül a gráfelmélet területén egy gráf körlefogó csúcshalmaza vagy körlefogó ponthalmaza (feedback vertex set) a gráf csúcsainak olyan halmaza, melyek eltávolításával a gráf kör nélkül marad. Más szavakkal, a körlefogó csúcshalmaz a gráf minden körének legalább egy csúcsát tartalmazza. A körlefogó csúcshalmaz problémája a számítási bonyolultságelmélet szerint NP-teljes probléma, méghozzá az első problémák között volt, amiről ezt megmutatták. Széles körben alkalmazzák operációs rendszerek, adatbázisok és VLSI-csipek tervezésében.

Definíció

Az eldöntési probléma a következő:

PÉLDÁNY: Egy (irányított vagy irányítatlan) gráf, G = ( V , E ) {\displaystyle G=(V,E)} és ez k {\displaystyle k} pozitív egész szám.
KÉRDÉS: Létezik-e olyan X ⊆ V {\displaystyle X\subseteq V} részhalmaz, melyre | X | ≤ k {\displaystyle |X|\leq k} és G {\displaystyle G} -ből X {\displaystyle X} csúcsainak törlésével kapott gráf körmentes?

A G [ V ∖ X ] {\displaystyle G[V\setminus X]} gráf, amit X {\displaystyle X} G {\displaystyle G} -ből való eltávolításával kapunk, egy feszített erdő (illetve irányított gráfok esetén, irányított körmentes gráf). Így egy gráf körlefogó csúcshalmazának megkeresése ekvivalens maximális feszített erdőjének (illetve maximális feszített irányított körmentes gráfjának) megkeresésével.

NP-nehézség

(Karp 1972) megmutatta, hogy a körlefogó csúcshalmaz problémája irányított gráfok esetén NP-teljes. A probléma szintén NP-teljes olyan irányított gráfokon, melyek maximális be-foka és ki-foka kettő, illetve irányított síkbarajzolható gráfokon, melyek maximális ki- és be-foka három.[1] A Karp-redukcióból következik továbbá a körlefogó csúcshalmaz-probléma NP-teljességét irányítatlan gráfokon, ahol a probléma NP-nehéz marad még négy maximális fokszámú gráfokon is; ellenben polinom időben megoldható három maximális fokszámú gráfok esetében.[2]

Vegyük észre, hogy a lehető legkevesebb él törlésével körmentessé alakítás ekvivalens a gráf feszítőfájának megkeresésével, ami polinom időben elvégezhető. Kontrasztként, az irányított gráf lehető legkevesebb él törlésével körmentessé alakítása, a körlefogó irányított élhalmaz-probléma (feedback arc set), NP-nehéz.[3]

Egzakt algoritmusok

A minimális méretű körlefogó csúcshalmaz NP-optimalizálási problémája O(1,7347n) időben megoldható, ahol n a gráf csúcsainak száma.[4] Ez az algoritmus ténylegesen kiszámítja a maximális feszített erdőt, majd annak komplementereként állítja elő a minimális körlefogó csúcshalmazt. Egy gráf minimális körlefogó csúcshalmazainak száma legfeljebb O(1,8638n).[5] Az irányított eset O*(1,9977n) időben megoldható, ahol n szintén az irányított gráf csúcsainak száma.[6] Mind az irányított, mind az irányítatlan eset parametrizált változata rögzített paraméter mellett kezelhető.[7]

Maximálisan 3 fokszámú irányítatlan gráfokban a probléma polinom időben megoldható, a lineáris matroidok matroidparitás-problémájára átalakítva.[8]

Approximáció

A probléma APX-teljes, ami közvetlen következménye a csúcslefedés-probléma APX-teljességének,[9] és a csúcslefedés-probléma és a körlefogó csúcshalmaz-probléma közötti approximációtartó L-redukció létezésének.[3] Irányítatlan gráfoknál a legjobb ismert approximációs arány 2 faktorú.[10]

Korlátok

Az Erdős–Pósa-tétel szerint a minimális körlefogó csúcshalmaz mérete az adott gráf csúcsdiszjunkt köreinek maximális számának logaritmikus faktora lehet.[11]

Alkalmazások

Operációs rendszerekben a körlefogó csúcshalmazok a holtponti helyzetből (deadlockból) való visszatérésben játszanak szerepet. Az operációs rendszer várakozási gráfjának minden irányított köre egy holtponti helyzetnek felel meg. Az összes deadlock feloldásához egyes blokkolt folyamatokat meg kell szakítani. Ennek a gráfnak a minimális körlefogó csúcshalmaza a megszakítandó folyamatok minimális számának felel meg.[12]

Ezen túl, a körlefogó csúcshalmaz-probléma a VLSI csipek tervezésében is szerephez jut.[13]

Jegyzetek

Fordítás

  • Ez a szócikk részben vagy egészben a Feedback vertex set című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Irodalom

Kutatási cikkek

  • Bafna, Vineet; Berman, Piotr & Fujito, Toshihiro (1999), "A 2-approximation algorithm for the undirected feedback vertex set problem", SIAM Journal on Discrete Mathematics 12 (3): 289–297 (electronic), DOI 10.1137/S0895480196305124.
  • Becker, Ann; Bar-Yehuda, Reuven & Geiger, Dan (2000), "Randomized algorithms for the loop cutset problem", Journal of Artificial Intelligence Research 12: 219–234, DOI 10.1613/jair.638
  • Becker, Ann & Geiger, Dan (1996), "Optimization of Pearl's method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem.", Artificial Intelligence 83 (1): 167–188, DOI 10.1016/0004-3702(95)00004-6
  • Cao, Yixin; Chen, Jianer & Liu, Yang (2010), "On feedback vertex set: new measure and new structures", in Kaplan, Haim, Proc. 12th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2010), Bergen, Norway, June 21-23, 2010, vol. 6139, Lecture Notes in Computer Science, pp. 93–104, DOI 10.1007/978-3-642-13731-0_10
  • Chen, Jianer; Fomin, Fedor V. & Liu, Yang et al. (2008), "Improved algorithms for feedback vertex set problems", Journal of Computer and System Sciences 74 (7): 1188–1198, DOI 10.1016/j.jcss.2008.05.002
  • Chen, Jianer; Liu, Yang & Lu, Songjian et al. (2008), "A fixed-parameter algorithm for the directed feedback vertex set problem", Journal of the ACM 55 (5): Art. 21, DOI 10.1145/1411509.1411511
  • Dinur, Irit & Safra, Samuel (2005), "On the hardness of approximating minimum vertex cover", Annals of Mathematics, Second Series 162 (1): 439–485, doi:10.4007/annals.2005.162.439, <http://www.cs.huji.ac.il/~dinuri/mypapers/vc.pdf> Archiválva 2009. szeptember 20-i dátummal a Wayback Machine-ben
  • Erdős, Paul & Pósa, Lajos (1965), "On independent circuits contained in a graph", Canadian Journal of Mathematics 17: 347–352, doi:10.4153/CJM-1965-035-8, <http://www.renyi.hu/~p_erdos/1965-05.pdf>
  • Fomin, Fedor V.; Gaspers, Serge & Pyatkin, Artem et al. (2008), "On the minimum feedback vertex set problem: exact and enumeration algorithms.", Algorithmica 52 (2): 293–307, DOI 10.1007/s00453-007-9152-0
  • Fomin, Fedor V. & Villanger, Yngve (2010), "Finding induced subgraphs via minimal triangulations", Proc. 27th International Symposium on Theoretical Aspects of Computer Science (STACS 2010), vol. 5, Leibniz International Proceedings in Informatics (LIPIcs), pp. 383–394, DOI 10.4230/LIPIcs.STACS.2010.2470
  • Karp, Richard M. (1972), "Reducibility Among Combinatorial Problems", Proc. Symposium on Complexity of Computer Computations, IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., New York: Plenum, pp. 85–103
  • Li, Deming & Liu, Yanpei (1999), "A polynomial algorithm for finding the minimum feedback vertex set of a 3-regular simple graph", Acta Mathematica Scientia 19 (4): 375–381, DOI 10.1016/s0252-9602(17)30520-9
  • Razgon, I. (2007), "Computing minimum directed feedback vertex set in O*(1.9977n)", in Italiano, Giuseppe F.; Moggi, Eugenio & Laura, Luigi, Proceedings of the 10th Italian Conference on Theoretical Computer Science, World Scientific, pp. 70–81, <http://www.cs.le.ac.uk/people/ir45/papers/ictcsIgorCamera.pdf>
  • Ueno, Shuichi; Kajitani, Yoji & Gotoh, Shin'ya (1988), "On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three", Discrete Mathematics 72 (1-3): 355–360, DOI 10.1016/0012-365X(88)90226-9

Tankönyvek és áttekintő cikkek

  • Festa, P.; Pardalos, P. M. & Resende, M.G.C. (2000), "Feedback set problems", in Du, D.-Z. & Pardalos, P. M., Handbook of Combinatorial Optimization, Supplement vol. A, Kluwer Academic Publishers, pp. 209–259, <http://www.research.att.com/~mgcr/doc/sfsp.pdf>
  • Garey, Michael R. & Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, A1.1: GT7, p. 191, ISBN 0-7167-1045-5
  • Silberschatz, Abraham; Galvin, Peter Baer & Gagne, Greg (2008), Operating System Concepts (8th ed.), John Wiley & Sons. Inc, ISBN 978-0-470-12872-5