I grafteorin kan en riktad graf innehålla riktade cykler , en ring av bågar som har samma riktning. I vissa applikationer är sådana cykler oönskade, vi kan eliminera dem och få en riktad acyklisk graf (Directed Acyclic Graph, DAG). Ett sätt att eliminera bågar är att helt enkelt ta bort bågarna från grafen. En återkopplingsbågeuppsättning ( FAS ) eller en cykelskärkantsuppsättning är en uppsättning bågar som, när de tas bort från en graf, bildar en DAG. Sett från en annan vinkel är det en uppsättning som innehåller minst en kant från varje cykel av grafen.
Ett närbesläktat koncept är den cykelskärande vertexuppsättningen , som inkluderar minst en vertex från varje cykel av en riktad graf, och det minsta spännträdet , som är en oriktad version av problemet med att hitta en cykelskärande uppsättning bågar.
En minimal cykelskärningsuppsättning av bågar (som inte kan minskas i storlek genom att ta bort kanter) har den ytterligare egenskapen att om dess kanter vänds istället för att tas bort, förblir grafen acyklisk. Att hitta en liten uppsättning kanter med den här egenskapen är ett nyckelsteg för att lägga en graf i lager [1] [2] .
Det är ibland önskvärt att kassera så få bågar som möjligt, vilket bildar den minsta cykelskärande uppsättningen av bågar , eller den dubbla största acykliska subgrafen . Problemet är ett komplext beräkningsproblem för vilket några approximativa lösningar har utvecklats.
Som ett enkelt exempel, föreställ dig följande hypotetiska situation där något måste göras för att få något:
Vi kan uttrycka denna situation som ett problem på en graf. Låt varje vertex representera ett objekt, och vi lägger till en båge från A till B om vi måste ha A för att få B. Tyvärr har du ingen av dessa tre saker, och eftersom grafen är cyklisk kan du inte ha någon av dessa saker. få.
Men anta att du ger George $100 för hans piano. Om han accepterar dem kommer den att ta bort bågen från gräsklipparen till pianot. Därmed är cykeln bruten och du kan göra två byten för att få den eftertraktade gräsklipparen. Denna enda båge utgör en cykelskärande uppsättning bågar.
Som i exemplet ovan är det vanligtvis ett visst pris förknippat med bågbrottet. Av denna anledning är det önskvärt att ta bort så få bågar som möjligt. Att ta bort en enskild båge räcker för att bryta en enkel cykel, men i allmänhet är det ett NP-hårt problem att hitta det minsta antalet bågar att ta bort , och kallas den minsta cykelavskärningsuppsättningen av bågar eller största acykliska subgrafproblem.
Detta problem är särskilt svårt för k -kantsanslutna grafer för stora k , där varje båge hamnar i många olika cykler. Lösbarhetsproblemet , som är NP-komplett , frågar om det är möjligt att klippa alla cykler genom att ta bort som mest k - bågar. Detta problem ingår i Karps lista över 21 NP-kompletta problem [3] [4] .
Eftersom det är NP-komplett är problemet med att hitta en uppsättning bågskärningscykler fast-parametriskt lösbart — det finns en algoritm för att lösa det, vars gångtid beror polynomiskt på storleken på ingångsgrafen (men inte beror på antalet kanter), men tiden beror exponentiellt på antalet kanter i cykelskärningsuppsättningen av bågar [5] .
Viggo Kann visade 1992 att problemet med att hitta den lägsta cykelskärningsuppsättningen av bågar är APX-hård , vilket betyder att det finns en konstant c så att, om man antar P≠NP, det inte finns någon polynom- tidsapproximationsalgoritm , som alltid hittar en uppsättning kanter som högst c gånger större än den optimala [6] [7] . År 2006 är det största värdet på c , för vilket det är känt att det inte finns någon sådan algoritm, lika med c = 1,3606 [8] . Den mest kända approximationsalgoritmen har en uppskattning av O (log n log log n ) [7] [9] . För det dubbla problemet med att approximera antalet kanter i en acyklisk subgraf är en algoritm med en koefficient något bättre än 1/2 [10] [11] möjlig .
Om inmatningsdigraferna är begränsade till turneringar är problemet känt som minimum feedback arc set problem on tournaments ( FAST ). Detta begränsade problem tillåter ett ungefärligt polynomtidsschema och detta uttalande förblir sant för den begränsade viktade versionen av problemet [12] . En algoritm med en fast subexponentiell parameter för viktad FAST föreslogs av Karpinski och Schudi [13] .
Å andra sidan, om kanterna är oriktade , är uppgiften att ta bort kanter för att nå en cykelfri graf likvärdig med att hitta ett minsta spännträd , vilket lätt kan göras i polynomtid.
Vissa approximationsalgoritmer har utvecklats för problemet [14] . En mycket enkel algoritm är följande:
Nu är både L och R acykliska subgrafer av G , och åtminstone en av dessa grafer är högst hälften så stor som en maximal acyklisk subgraf [15] .