Feedback vertex set

I den matematiska disciplinen grafteori är en återkopplingspunktuppsättning (FVS) av en graf en uppsättning av hörn vars borttagning lämnar en graf utan cykler ("borttagning" betyder att ta bort vertexet och alla kanter intill den). På motsvarande sätt innehåller varje FVS minst en vertex av varje cykel i grafen. Återkopplingspunktuppsättningsnumret för en graf är storleken på en minsta återkopplingspunktuppsättning . Problemet med minsta återkopplingspunktuppsättning är ett NP-komplett problem; det var bland de första problemen som visades vara NP-komplett . Den har breda tillämpningar inom operativsystem , databassystem och VLSI- chipdesign.

Definition

FVS- beslutsproblemet är som följer:

INSTANS: En (oriktad eller riktad) graf $G=(V,E)$ och ett positivt heltal $k$ .

FRÅGA: Finns det en delmängd $X\subseteq V$ med $|X|\leq k$ så att, när alla hörn av $X$ och deras intilliggande kanter raderas från $G$ , resten är cykelfri ?

Grafen $G[V\setminus X]$ som finns kvar efter att ${\displaystyle X} tagits bort$ från $G$ är en inducerad skog (resp. en inducerad riktad acyklisk graf i fallet med riktade grafer ). Att hitta ett minimum FVS i en graf är alltså likvärdigt med att hitta en maximalt inducerad skog (resp. maximalt inducerad riktad acyklisk graf i fallet med riktade grafer ).

NP-hårdhet

Karp (1972) visade att det minsta FVS-problemet för riktade grafer är NP-komplett . Problemet förblir NP-komplett på riktade grafer med maximal in-grad och ut-grader två, och på riktade plana grafer med maximal in-grad och ut-grader tre.

Karps minskning innebär också NP-fullständigheten av FVS-problemet på oriktade grafer, där problemet förblir NP-hårt på grafer med maximal grad fyra. FVS-problemet kan lösas i polynomtid på grafer med maximal grad av högst tre.

Exakta algoritmer

Det motsvarande NP-optimeringsproblemet att hitta storleken på en minimal återkopplingspunktuppsättning kan lösas i tiden O (1,7347 ⁿ ), där n är antalet hörn i grafen. Denna algoritm beräknar faktiskt en maximal inducerad skog, och när en sådan skog erhålls är dess komplement en minimal återkopplingspunktuppsättning. Antalet minimala återkopplingspunktuppsättningar i en graf begränsas av O (1,8638 ⁿ ). Problemet med den riktade återkopplingspunktuppsättningen kan fortfarande lösas i tiden O* (1,9977 ⁿ ), där n är antalet hörn i den givna riktade grafen. De parametriserade versionerna av de riktade och oriktade problemen är båda handhavbara med fasta parametrar .

I oriktade grafer av maximal grad tre kan återkopplingspunktuppsättningsproblemet lösas i polynomtid , genom att omvandla det till en instans av matroidparitetsproblemet för linjära matroider .

Approximation

Det oriktade problemet är APX-komplett . Detta följer av följande fakta.

• APX-fullständigheten av vertextäckningsproblemet ;
• Förekomsten av en approximation som bevarar L-reduktion från vertextäckningsproblemet till det;
• Befintliga konstantfaktorapproximationsalgoritmer.

Den mest kända approximationsalgoritmen på oriktade grafer är med en faktor två.

Däremot verkar den riktade versionen av problemet vara mycket svårare att uppskatta. Enligt den unika spelförmodan , ett oprövat men vanligt förekommande antagande om beräkningshårdhet , är det NP-svårt att approximera problemet till en konstant faktor i polynomtid. Samma hårdhetsresultat bevisades ursprungligen för det närbesläktade återkopplingsbåguppsättningsproblemet , men eftersom återkopplingsbåguppsättningsproblemet och återkopplingspunktuppsättningsproblemet i riktade grafer kan reduceras till varandra samtidigt som lösningsstorlekar bevaras, gäller det även för det senare.

Gräns

Enligt Erdős-Pósa-satsen ligger storleken på en minsta återkopplingspunktsuppsättning inom en logaritmisk faktor av det maximala antalet hörn-disjunkta cykler i den givna grafen.

Relaterade begrepp

• Istället för hörn kan man betrakta en återkopplingskantuppsättning - en uppsättning kanter i en oriktad graf, vars borttagning gör grafen acyklisk. Storleken på en minsta återkopplingsflankuppsättning i en graf kallas grafens kretsrankning . I motsats till FVS-numret kan kretsrankningen lätt beräknas: den är $|E|-|V|+|C|$ , där C är uppsättningen av anslutna komponenter i grafen. Problemet med att hitta en minsta återkopplingskantmängd är likvärdig med att hitta en spännskog , vilket kan göras i polynomtid .

• Det analoga konceptet i en riktad graf är feedback arc set (FAS) - en uppsättning riktade bågar vars borttagning gör grafen acyklisk. Att hitta en minsta FAS är ett NP-hårt problem.

Ansökningar

• I operativsystem spelar återkopplingspunktuppsättningar en framträdande roll i studiet av återställning av dödläge . I väntan-på-grafen för ett operativsystem motsvarar varje riktad cykel en dödlägessituation. För att lösa alla dödlägen måste vissa blockerade processer avbrytas. En minsta återkopplingspunkt som anges i denna graf motsvarar ett minsta antal processer som man behöver avbryta.

• Problemet med återkopplingspunktuppsättningen har tillämpningar i VLSI- chipdesign.
• En annan tillämpning är i komplexitetsteorin. Vissa beräkningsproblem på grafer är NP-hårda i allmänhet, men kan lösas i polynomtid för grafer med begränsat FVS-nummer. Några exempel är grafisomorfism och problemet med vägomkonfiguration.

Anteckningar

Forskningsartiklar

• 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 (elektronisk), doi : 10.1137/S08954801960 6MR 501960 6MR 1460 601960 6   .
•   Becker, Ann; Bar-Yehuda, Reuven; Geiger, Dan (2000), "Randomized algorithms for the loop cutset problem", Journal of Artificial Intelligence Research , 12 : 219–234, arXiv : 1106.0225 , doi : 10.1613/jair.638 , MR 900 1725C 1765ID 7025ID  
•   Becker, Ann; Geiger, Dan (1996), "Optimering av Pearls metod för konditionering och giriga approximationsalgoritmer för problem med vertexåterkopplingsuppsättningen." Artificiell intelligens , 83 (1): 167–188, CiteSeerX 10.1.1.25.1442 , doi : 10.1016/0004-3702(95)00004-6
•   Cao, Yixin; Chen, Jianer; Liu, Yang (2010), "On feedback vertex set: new measure and new structures", i Kaplan, Haim (red.), Proc. 12th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2010), Bergen, Norge, 21-23 juni 2010, Lecture Notes in Computer Science, vol. nr _ _ _ _ _ _ _ _ _ _ _ _ _ _
•   Chen, Jianer; Fomin, Fedor V.; Liu, Yang; Lu, Songjian; Villanger, Yngve (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 , MR 2454063
•    Chen, Jianer; Liu, Yang; Lu, Songjian; O'Sullivan, Barry; Razgon, Igor (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 , MR 2456546 , S2CID 1547510
•   Dinur, Irit ; Safra, Samuel (2005), "On the hardness of approximating minimal vertex cover" (PDF) , Annals of Mathematics , Second Series, 162 (1): 439–485, doi : 10.4007/annals.2005.162.439 , MR 217896 arkiverad från originalet (PDF) 2009-09-20 , hämtad 2010-03-29
•   Erdős, Paul ; Pósa, Lajos (1965), "On independent circuits contained in a graph" (PDF) , Canadian Journal of Mathematics , 17 : 347–352, doi : 10.4153/CJM-1965-035-8 , S2CID 1283981322
•    Fomin, Fedor V.; Gaspers, Serge; Pyatkin, Artem; Razgon, Igor (2008), "On the minimal feedback vertex set problem: exact and enumeration algorithms." Algorithmica , 52 (2): 293–307, CiteSeerX 10.1.1.722.8913 , doi : 10.1001-5007-95 -0 , S2CID 731997
•    Fomin, Fedor V.; Villanger, Yngve (2010), "Finding induced subgraphs via minimal triangulations", Proc. 27th International Symposium on Theoretical Aspects of Computer Science (STACS 2010) , Leibniz International Proceedings in Informatics (LIPIcs), vol. 5, s. 383–394, doi : 10.4230/LIPIcs.STACS.2010.2470 , ISBN 9783939897163 , S2CID 436224
• Karp, Richard M. (1972), "Reducibility Among Combinatorial Problems", Proc. Symposium on Complexity of Computer Computations, IBM Thomas J. Watson Res. Center, Yorktown Heights, NY , New York: Plenum, s. 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 , MR 1735603
• Razgon, I. (2007), "Computing minimum riktad feedback vertex set in O*(1,9977 ⁿ )", i Italiano, Giuseppe F. ; Moggi, Eugenio; Laura, Luigi (red.), Proceedings of the 10th Italian Conference on Theoretical Computer Science (PDF) , World Scientific, s. 70–81
•   Ueno, Shuichi; Kajitani, Yoji; Gotoh, Shin'ya (1988), "Om det icke-separerande oberoende uppsättningsproblemet och återkopplingsuppsättningsproblemet för grafer utan vertexgrad som överstiger tre", Discrete Mathematics , 72 (1–3): 355–360, doi : 10.1016/0012- 365X(88)90226-9 , MR 0975556

Läroböcker och enkätartiklar

• Festa, P.; Pardalos, PM; Resende, MGC (2000), "Feedback set problems", i Du, D.-Z.; Pardalos, PM (red.), Handbook of Combinatorial Optimization, Supplement vol. A (PDF) , Kluwer Academic Publishers, s. 209–259
•   Garey, Michael R .; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness , WH Freeman, A1.1: GT7, sid. 191 , ISBN 978-0-7167-1045-5
•   Silberschatz, Abraham; Galvin, Peter Baer; Gagne, Greg (2008), Operativsystemkoncept (8:e upplagan), John Wiley & Sons. Inc, ISBN 978-0-470-12872-5