Körlefogó csúcshalmaz

Innen: testwiki
Ugrás a navigációhoz Ugrás a kereséshez

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) és ez k pozitív egész szám.
KÉRDÉS: Létezik-e olyan X⊆V részhalmaz, melyre |X|≤k és G-ből X csúcsainak törlésével kapott gráf körmentes?

A G[V∖X] gráf, amit X 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

Sablon:Harvtxt 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).Sablon:Sfnp 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.Sablon:Sfnp Mind az irányított, mind az irányítatlan eset parametrizált változata rögzített paraméter mellett kezelhető.Sablon:Sfnp

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.Sablon:Sfnp

Approximáció

A probléma APX-teljes, ami közvetlen következménye a csúcslefedés-probléma APX-teljességének,[5] é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ú.[6]

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.Sablon:Sfnp

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.Sablon:Sfnp

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

Jegyzetek

Sablon:Jegyzetek

Fordítás

Irodalom

Kutatási cikkek

Sablon:Refbegin

Sablon:Refend

Tankönyvek és áttekintő cikkek

  1. ↑ unpublished results due to Garey and Johnson, cf. Sablon:Harvtxt: GT7
  2. ↑ Sablon:Harvtxt; Sablon:Harvtxt
  3. ↑ 3,0 3,1 Sablon:Harvtxt
  4. ↑ Sablon:Harvtxt
  5. ↑ Sablon:Harvnb
  6. ↑ Sablon:Harvtxt. Lásd még Sablon:Harvtxt-nál egy alternatív közelítő algoritmust ugyanakkora approximációs aránnyal.
A lap eredeti címe: „https://hu.wiki.beta.math.wmflabs.org/w/index.php?title=Körlefogó_csúcshalmaz&oldid=3917”