Cykelskärande uppsättning av hörn

I grafteorin är den cykelavskärande uppsättningen av hörn i en graf  den uppsättning av hörn vars borttagning leder till att cyklerna bryter . Med andra ord innehåller den cykelskärande vertexuppsättningen minst en vertex från vilken grafcykel som helst. Cykelskärande är ett NP-komplett problem inom beräkningskomplexitetsteori . Problemet finns med i Karps lista över 21 NP-kompletta problem . Problemet har bred tillämpning i operativsystem , databaser och VLSI- utveckling .

Definition

Problemet med cykelskärande vertexuppsättning  är följande lösbarhetsproblem :

Givet: En (oriktad eller riktad) graf och ett positivt tal . Fråga: Finns det en delmängd för vilken , som med borttagna hörn som tillhör , inte innehåller cykler ?

Grafen som återstår efter att de hörn som tillhör uppsättningen har tagits bort från grafen är en genererad skog (för oriktade grafer, eller en genererad riktad acyklisk graf för riktade grafer ). Att söka efter en minimicykel som skär en uppsättning hörn i en graf är alltså likvärdig med att söka efter en maximal genererad skog (respektive en maximal genererad acyklisk graf i fallet med riktade grafer ).

NP-svårighet

Karp [1] visade att problemet med cykelskärande vertexuppsättningar för riktade grafer är NP-komplett . Problemet förblir NP-komplett för riktade grafer med en maximal grad av inkommande och utgående bågar lika med två, och för riktade plenumgrafer med en maximal grad av inkommande och utgående bågar lika med tre [2] . Karp-reduktionen antyder också NP-fullständigheten för det cykelskärande vertexuppsättningsproblemet på oriktade grafer, och problemet förblir NP-hårt på grafer med maximal grad fyra. Problemet med en cykelskärande uppsättning av hörn kan lösas i polynomtid på grafer med en maximal grad som inte överstiger tre [3] [4] .

Observera att uppgiften att ta bort så få kanter som möjligt för att bryta cykler (i en oriktad graf) är likvärdig med att hitta ett spännträd , och denna uppgift kan slutföras i polynomtid . Däremot är problemet med att ta bort kanter från en riktad graf för att göra den acyklisk , det vill säga problemet med en cykelskärande uppsättning bågar NP-komplett [1] .

Exakta algoritmer

Motsvarande NP-komplett optimeringsproblem att hitta storleken på den minsta cykelskärningsuppsättningen av hörn kan lösas i tiden O (1,7347 n ), där n  är antalet hörn i grafen [5] . Faktum är att denna algoritm hittar den maximala genererade skogen och komplementet till denna skog kommer att vara den önskade uppsättningen av hörn. Antalet minimala cykelskärande vertexuppsättningar är begränsat till O (1,8638 n ) [6] . Problemet med den minsta cykelskärningsuppsättningen för en riktad graf kan lösas i tiden O* (1,9977 n ), där n  är antalet hörn i en given riktad graf [7] . Parametriserade versioner av orienterade och oriktade problem är fast-parametriskt lösbara [8] .

Approximation

Problemet är APX-komplett , vilket direkt följer av APX-komplexiteten hos vertextäckningsproblemet [9] och förekomsten av en approximation som bevarar L-reduktionen från vertextäckningsproblemet till detta problem [1] . Den mest kända algoritmen för oriktade grafer har en faktor på två [10] .

Gränser

Enligt Erdős-Pose-satsen begränsas storleken på den minsta cykelskärande uppsättningen av hörn av den logaritmiska faktorn för det maximala antalet cykler med brytpunktsuppdelning i en given graf [11] .

Applikationer

I operativsystem spelar den slingklippande vertexuppsättningen en framträdande roll vid detektering av dödläge . I operativsystemets väntediagram motsvarar varje orienterad slinga ett dödläge. För att gå ur alla dödlägen måste vissa blockerade processer avslutas. Den minsta cykelskärningsuppsättningen av hörn i grafen motsvarar det minsta antalet processer som bör avbrytas [12]

Dessutom har uppsättningen av skärningscykler för hörn applikationer i utvecklingen av VLSI [13] .

Anteckningar

  1. ↑ 1 2 3 Karp, 1972 .
  2. ↑ Opublicerat resultat på grund av Garey och Johnson (Garey, Johnson), se Garey, Johnson, 1979 : GT7
  3. ↑ Ueno, Kajitani, Gotoh, 1988 .
  4. ↑ Li, Liu, 1999 .
  5. ↑ Fomin, Villanger, 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 . Se även Bafna, Berman, Fujito, 1999 för en alternativ approximationsalgoritm med samma koefficient.
  11. ↑ Erdős, Posa, 1965 .
  12. ↑ Silberschatz, Galvin, Gagne, 2008 .
  13. ↑ Festa, Pardalos, Resende, 2000 .

Litteratur

Forskningsartiklar och böcker

Läroböcker och recensionsartiklar