Vrcholový kryt - Vertex cover

V matematický disciplína teorie grafů, a vrcholový kryt (někdy kryt uzlu) a graf je sada vrcholů, která zahrnuje alespoň jeden koncový bod každé hrany graf Problém najít minimální vrcholový kryt je klasický optimalizační problém v počítačová věda a je typickým příkladem souboru NP-tvrdé optimalizační problém, který má aproximační algoritmus. Své rozhodovací verze, problém s vrcholovým krytem, byl jedním z Karpových 21 NP-úplných problémů a je tedy klasický NP-kompletní problém v teorie výpočetní složitosti. Kromě toho je problém pokrytí vrcholů fixovatelný parametr a ústřední problém v parametrizovaná teorie složitosti.
Problém s minimálním krytím vrcholu lze formulovat jako polointegrál lineární program jehož duální lineární program je problém s maximální shodou.
Problémy s vrcholovým krytem byly zobecněny na hypergrafy viz Vrcholový kryt v hypergrafech.
Definice
Formálně vrcholový kryt neorientovaného grafu je podmnožinou takhle , to znamená, že se jedná o množinu vrcholů kde každá hrana má alespoň jeden koncový bod ve vrcholovém krytu . Taková sada se říká Pokrýt okraje . Následující obrázek ukazuje dva příklady vrcholových krytů s některými vrcholovými kryty označeno červeně.
A minimální vrcholový kryt je vrcholový kryt nejmenší možné velikosti. Číslo vrcholového krytu je velikost minimálního vrcholového krytu, tj. . Následující obrázek ukazuje příklady minimálních vrcholů v předchozích grafech.
Příklady
- Sada všech vrcholů je vrcholovým krytem.
- Koncové body libovolného maximální shoda tvoří vrcholový kryt.
- The kompletní bipartitní graf má minimální vrcholový kryt velikosti .
Vlastnosti
- Sada vrcholů je vrcholový kryt právě tehdy, je-li jeho doplněk je nezávislá sada.
- V důsledku toho se počet vrcholů grafu rovná jeho minimálnímu počtu vrcholových obalů plus velikosti maximální nezávislé množiny (Gallai 1959).
Výpočtový problém
The problém s minimálním vrcholem je optimalizační problém hledání nejmenšího vrcholového krytu v daném grafu.
- INSTANCE: Graf
- VÝSTUP: Nejmenší číslo takhle má vrcholový kryt velikosti .
Pokud je problém uveden jako a rozhodovací problém, nazývá se to problém s vrcholovým krytem:
- INSTANCE: Graf a kladné celé číslo .
- OTÁZKA: Ano mít vrcholový kryt velikosti maximálně ?
Problém vrcholového krytu je NP-kompletní problém: byl to jeden z Karpových 21 NP-úplných problémů. Často se používá v teorie výpočetní složitosti jako výchozí bod pro NP-tvrdost důkazy.
Formulace ILP
Předpokládejme, že každý vrchol má související náklady (Vážený) problém s minimálním pokrytím vrcholů lze formulovat následovně celočíselný lineární program (ILP).[1]
minimalizovat (minimalizujte celkové náklady) podléhá pro všechny (zakryjte všechny okraje grafu) pro všechny . (každý vrchol je buď ve vrcholovém krytu, nebo ne)
Tento ILP patří do obecnější třídy ILP pro pokrývající problémy.v mezera v integritě tohoto ILP je , Takže to je relaxace (umožnění každé proměnné být v intervalu od 0 do 1, spíše než vyžadování, aby proměnné byly pouze 0 nebo 1) dává faktor- aproximační algoritmus pro problém s krytím minimálního vrcholu. Kromě toho je relaxace lineárního programování tohoto ILP napůl integrální, to znamená, že existuje optimální řešení, pro které každý záznam je buď 0, 1/2, nebo 1. Z tohoto zlomkového řešení lze získat 2-přibližný vrcholový obal výběrem podmnožiny vrcholů, jejichž proměnné jsou nenulové.
Přesné hodnocení
The rozhodnutí varianta problému vrcholového krytu je NP-kompletní, což znamená, že je nepravděpodobné, že existuje efektivní algoritmus, který by jej vyřešil přesně pro libovolné grafy. Úplnost NP lze prokázat snížením z 3 - uspokojivost nebo, jak to udělal Karp, snížením z klika problém. Vrcholový kryt zůstává NP-kompletní i v kubické grafy[2] a dokonce i dovnitř rovinné grafy stupně nanejvýš 3.[3]
Pro bipartitní grafy, ekvivalenci mezi vrcholovým krytem a maximální shodou popsal Kőnigova věta umožňuje řešit problém bipartitního vrcholového krytu v polynomiální čas.
Pro stromové grafy, algoritmus najde minimální vrcholový kryt v polynomiálním čase tím, že najde první list ve stromu a přidá jeho rodiče k minimálnímu vrcholovému krytu, poté odstraní list a nadřazený prvek a všechny přidružené hrany a pokračuje opakovaně, dokud ve stromu nezůstanou žádné hrany.
Opravitelnost s pevnými parametry
An vyčerpávající vyhledávání algoritmus dokáže vyřešit problém v čase 2knÓ(1), kde k je velikost vrcholového krytu. Vrcholový kryt je tedy fixovatelný parametr, a pokud nás zajímá jen malý k, můžeme problém vyřešit v polynomiální čas. Jedna algoritmická technika, která zde funguje, se nazývá algoritmus omezeného vyhledávacího stromua jeho myšlenkou je opakovaně zvolit nějaký vrchol a rekurzivně větvit, přičemž v každém kroku budou dva případy: umístit do vrcholového krytu buď aktuální vrchol, nebo všechny jeho sousedy. Algoritmus řešení vrcholového krytu, který dosahuje nejlepší asymptotické závislosti na parametru běží v čase .[4] The hodnota klam této časové hranice (odhad největší hodnoty parametru, kterou lze vyřešit v rozumném čase) je přibližně 190. To znamená, že pokud nelze najít další vylepšení algoritmu, je tento algoritmus vhodný pouze pro instance, jejichž číslo pokrytí vrcholem je 190 nebo méně. Za rozumně složitých teoretických předpokladů, jmenovitě exponenciální časová hypotéza, provozní dobu nelze zlepšit na 2Ó(k), i když je .
Nicméně pro rovinné grafy a obecněji, pro grafy vylučující nějaký fixní graf jako vedlejší, vrcholový kryt velikosti k lze najít včas , tj. problém je subexponenciální fixovatelný parametr.[5] Tento algoritmus je opět optimální, v tom smyslu, že pod exponenciální časová hypotéza, žádný algoritmus nedokáže vyřešit vrcholový kryt na rovinných grafech v čase .[6]
Přibližné hodnocení
Lze najít faktor 2 přiblížení opakovaným užíváním oba koncové body hrany do vrcholového krytu a jejich odstranění z grafu. Jinak řečeno, najdeme a maximální shoda M chamtivým algoritmem a vytvořte vrcholový kryt C který se skládá ze všech koncových bodů hran v M. Na následujícím obrázku je maximální shoda M je označen červeně a vrcholový kryt C je označen modře.
Sada C takto konstruovaný je vrcholový kryt: předpokládejme, že hrana E není pokryta C; pak M ∪ {E} je odpovídající a E ∉ M, což je v rozporu s předpokladem, že M je maximální. Kromě toho, pokud E = {u, proti} ∈ M, pak jakýkoli vrcholový kryt - včetně optimálního vrcholového krytu - musí obsahovat u nebo proti (nebo oboje); jinak hrana E není kryta. To znamená, že optimální obal obsahuje alespoň jeden koncový bod každé hrany v M; celkem C je maximálně 2krát větší než optimální vrcholový kryt.
Tento jednoduchý algoritmus objevili nezávisle Fanica Gavril a Mihalis Yannakakis.[7]
Více zapojených technik ukazuje, že existují aproximační algoritmy s mírně lepším aproximačním faktorem. Například aproximační algoritmus s aproximačním faktorem je známo.[8] Problém lze aproximovat pomocí aproximačního faktoru v - husté grafy.[9]
Nepřibližnost
Nelépe algoritmus aproximace konstantního faktoru než je známo výše. Problém s minimálním pokrytím vrcholů je APX-kompletní, to znamená, že jej nelze libovolně dobře aproximovat, pokud P = NP.Použití technik z Věta o PCP, Dinur a Safra v roce 2005 prokázal, že minimální vrcholovou pokrývku nelze pro jakýkoli dostatečně velký vrcholný stupeň aproximovat v rámci faktoru 1,3606, pokud P = NP.[10] Později byl faktor vylepšen na pro všechny .[11][12]Navíc pokud domněnky o jedinečných hrách je pravda, pak minimální vrcholový kryt nelze aproximovat v žádném konstantním faktoru lépe než 2.[13]
Ačkoli nalezení vrcholového krytu minimální velikosti je ekvivalentní nalezení nezávislé sady maximální velikosti, jak je popsáno výše, tyto dva problémy nejsou ekvivalentní způsobem zachovávajícím aproximaci: Problém nezávislé sady má Ne konstantní faktorová aproximace, pokud P = NP.
Pseudo kód
PŘIBLÍŽENÍ-VRCHOL-POKRÝT(G)=C = ∅E'= G.Ezatímco E' ≠ ∅: nechat (u, proti) být an libovolný okraj z E' C = C ∪ {u, proti} odstranit z E' každý okraj incident na buď u nebo protivrátit se C
Aplikace
Optimalizace vrcholového krytu slouží jako a Modelka pro mnoho skutečných a teoretický problémy. Například komerční provozovna se zájmem o instalaci co nejméně kamery s uzavřeným okruhem zakrytí všech chodeb (hran) spojujících všechny místnosti (uzly) na podlaze může model modelovat jako problém minimalizace vrcholového krytu. Problém byl také použit k modelování eliminace opakující se sekvence DNA pro syntetická biologie a metabolické inženýrství aplikace.[16][17]
Poznámky
- ^ Vazirani 2003, str. 121–122
- ^ Garey, Johnson & Stockmeyer 1974
- ^ Garey & Johnson 1977; Garey & Johnson 1979, s. 190 a 195.
- ^ Chen, Kanj a Xia 2006
- ^ Demaine a kol. 2005
- ^ Flum & Grohe (2006, str. 437)
- ^ Papadimitriou & Steiglitz 1998, str. 432, zmiňuje Gavril i Yannakakis. Garey & Johnson 1979, str. 134, uvádí Gavril.
- ^ Karakostas 2009
- ^ Karpinski & Zelikovsky 1998
- ^ Dinur a Safra 2005
- ^ Khot, Minzer a Safra 2017 [úplná citace nutná ]
- ^ Dinur a kol. 2018 [úplná citace nutná ]
- ^ Khot & Regev 2008
- ^ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [1990]. „Oddíl 35.1: Problém vrcholového krytu“. Úvod do algoritmů (2. vyd.). MIT Press a McGraw-Hill. str. 1024–1027. ISBN 0-262-03293-7.
- ^ Chakrabarti, Amit (zima 2005). „Aproximační algoritmy: Vrcholový kryt“ (PDF). Počítačová věda 105. Dartmouth College. Citováno 21. února 2005.
- ^ Hossain, Ayaan; Lopez, Eriberto; Halper, Sean M .; Cetnar, Daniel P .; Reis, Alexander C .; Strickland, Devin; Klavins, Eric; Salis, Howard M. (2020-07-13). „Automatizovaný návrh tisíců neopakovatelných částí pro konstrukci stabilních genetických systémů“. Přírodní biotechnologie. doi:10.1038 / s41587-020-0584-2. ISSN 1087-0156. PMID 32661437. S2CID 220506228.
- ^ Reis, Alexander C .; Halper, Sean M .; Vezeau, Grace E .; Cetnar, Daniel P .; Hossain, Ayaan; Clauer, Phillip R .; Salis, Howard M. (listopad 2019). „Současná represe více bakteriálních genů pomocí neopakovatelných extra dlouhých polí sgRNA“. Přírodní biotechnologie. 37 (11): 1294–1301. doi:10.1038 / s41587-019-0286-9. ISSN 1546-1696. PMID 31591552. S2CID 203852115.
Reference
- Chen, Jianer; Kanj, Iyad A .; Xia, Ge (2006). "Vylepšené parametrizované horní hranice pro vrcholový kryt". Matematické základy informatiky 2006: 31. mezinárodní sympozium, MFCS 2006, Stará Lesná, Slovensko, 28. srpna - 1. září 2006, sborník (PDF). Přednášky z informatiky. 4162. Springer-Verlag. 238–249. doi:10.1007/11821069_21. ISBN 978-3-540-37791-7.CS1 maint: ref = harv (odkaz)
- Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). Úvod do algoritmů. Cambridge, Massachusetts: MIT Press a McGraw-Hill. str.1024 –1027. ISBN 0-262-03293-7.CS1 maint: ref = harv (odkaz)
- Demaine, Erik; Fomin, Fedor V .; Hajiaghayi, Mohammad Taghi; Thilikos, Dimitrios M. (2005). „Subexponenciální parametrizované algoritmy na grafech omezeného rodu a grafech bez H-minor“. Deník ACM. 52 (6): 866–893. doi:10.1145/1101821.1101823. S2CID 6238832. Citováno 2010-03-05.CS1 maint: ref = harv (odkaz)
- Dinur, Irit; Safra, Samuel (2005). Msgstr "O tvrdosti přibližného minimálního vrcholového krytu". Annals of Mathematics. 162 (1): 439–485. CiteSeerX 10.1.1.125.334. doi:10.4007 / annals.2005.162.439.CS1 maint: ref = harv (odkaz)
- Flum, Jörg; Grohe, Martin (2006). Parametrizovaná teorie složitosti. Springer. ISBN 978-3-540-29952-3. Citováno 2010-03-05.CS1 maint: ref = harv (odkaz)
- Garey, Michael R.; Johnson, David S. (1977). "Přímočarý problém Steinerova stromu je NP-úplný". SIAM Journal on Applied Mathematics. 32 (4): 826–834. doi:10.1137/0132071.CS1 maint: ref = harv (odkaz)
- Garey, Michael R.; Johnson, David S. (1979). Počítače a neodolatelnost: Průvodce po teorii NP-úplnosti. W.H. Freemane. ISBN 0-7167-1045-5.CS1 maint: ref = harv (odkaz) A1.1: GT1, s. 190.
- Garey, Michael R.; Johnson, David S.; Stockmeyer, Larry (1974). „Některé zjednodušené NP-úplné problémy“. Proceedings of the Sixth Annual ACM Symposium on Theory of Computing. 47–63. doi:10.1145/800119.803884.CS1 maint: ref = harv (odkaz)
- Gallai, Tibor (1959). „Über extreme Punkt- und Kantenmengen“. Ann. Univ. Sci. Budapešť, Eötvös Sect. Matematika. 2: 133–138.CS1 maint: ref = harv (odkaz)
- Karakostas, George (listopad 2009). „Lepší poměr přiblížení pro problém vrcholového krytu“ (PDF). Transakce ACM na algoritmech. 5 (4): 41:1–41:8. CiteSeerX 10.1.1.649.7407. doi:10.1145/1597036.1597045. S2CID 2525818. ECCC TR04-084.CS1 maint: ref = harv (odkaz)
- Karpinski, Marek; Zelikovsky, Alexander (1998). „Přibližování hustých případů problémů s krytím“. Proceedings of the DIMACS Workshop on Network Design: Connectivity and Facilities Location. Řada DIMACS v diskrétní matematice a teoretické informatice. 40. Americká matematická společnost. 169–178.CS1 maint: ref = harv (odkaz)
- Khot, Subhash; Regev, Oded (2008). "Vrcholový kryt může být obtížné přiblížit do 2 ε". Journal of Computer and System Sciences. 74 (3): 335–349. doi:10.1016 / j.jcss.2007.06.019.CS1 maint: ref = harv (odkaz)
- O'Callahan, Robert; Choi, Jong-Deok (2003). „Hybridní detekce dynamických dat“. Sborník sympozia ACM SIGPLAN o principech a praxi paralelního programování (PPoPP 2003) a workshop o dílčím hodnocení a manipulaci s programem založeným na sémantice (PEPM 2003). Oznámení ACM SIGPLAN. 38 (10). 167–178. doi:10.1145/966049.781528.CS1 maint: ref = harv (odkaz)
- Papadimitriou, Christos H.; Steiglitz, Kenneth (1998). Kombinatorická optimalizace: Algoritmy a složitost. Doveru.CS1 maint: ref = harv (odkaz)
- Vazirani, Vijay V. (2003). Aproximační algoritmy. Springer-Verlag. ISBN 978-3-662-04565-7.CS1 maint: ref = harv (odkaz)