Kernelisering

Den här artikeln handlar om komplexitetsteori. För kärniserade maskininlärningsmetoder, se Kernel-metod .

Inom datavetenskap är en kärnbildning en teknik för att designa effektiva algoritmer som uppnår sin effektivitet genom ett förbearbetningssteg där indata till algoritmen ersätts av en mindre indata, kallad "kärna". Resultatet av att lösa problemet på kärnan bör antingen vara detsamma som på originalinmatningen, eller så bör det vara lätt att omvandla utdata på kärnan till önskad utdata för originalproblemet.

Kernelisering uppnås ofta genom att tillämpa en uppsättning reduktionsregler som skär bort delar av instansen som är lätta att hantera. I parameteriserad komplexitetsteori är det ofta möjligt att bevisa att en kärna med garanterade gränser för storleken på en kärna (som en funktion av någon parameter associerad med problemet) kan hittas i polynomtid . När detta är möjligt resulterar det i en med fasta parametrar, vars körtid är summan av (polynomtiden) kärnbildningssteget och (icke-polynomet men begränsat av parametern) tiden för att lösa kärnan. Faktum är att varje problem som kan lösas med en algoritm med fasta parametrar kan lösas med en kärniseringsalgoritm av denna typ. Detta gäller även för ungefärlig kärnbildning .

Exempel: vertexskydd

Ett standardexempel för en kerneliseringsalgoritm är kerneliseringen av vertextäckningsproblemet av S. Buss. I detta problem är inmatningen en oriktad graf $G$ tillsammans med ett tal $k$ . Utdata är en uppsättning av högst $k$ hörn som inkluderar en ändpunkt för varje kant i grafen, om en sådan uppsättning finns, eller ett misslyckande undantag om ingen sådan uppsättning finns. Detta problem är NP-svårt . Följande reduktionsregler kan dock användas för att kernelisera den:

1. Om $k>0$ och $v$ är en vertex som är större än ${\displaystyle k} ,$ ta bort $v$ från grafen och minska $k$ med ett. Varje vertextäcke av storleken $k$ måste innehålla $v$ eftersom annars för många av dess grannar skulle behöva väljas för att täcka de infallande kanterna. Således kan ett optimalt vertextäcke för den ursprungliga grafen bildas från ett täcke av det reducerade problemet genom att lägga till $v$ tillbaka till omslaget.
2. Om $v$ är en isolerad vertex, ta bort den. En isolerad vertex kan inte täcka några kanter, så i det här fallet $v$ inte vara en del av någon minimal täckning.
3. Om mer än $k^{2}$ kanter finns kvar i grafen, och ingen av de två föregående reglerna kan tillämpas, kan grafen inte innehålla ett vertextäcke av storleken k {\ $k}$ . För, efter att ha eliminerat alla hörn som är större än $k$ , kan varje återstående vertex endast täcka högst $k$ kanter och en uppsättning $k$ hörn kunde bara täcka högst $k^{2}$ kanter. I det här fallet kan instansen ersättas av en instans med två hörn, en kant och $k=0$ , som inte heller har någon lösning.

En algoritm som tillämpar dessa regler upprepade gånger tills inga fler reduktioner kan göras avslutas nödvändigtvis med en kärna som har högst $k^{2}$ kanter och (eftersom varje kant har högst två ändpunkter och det inte finns några isolerade hörn) högst $2k^{2}$ hörn. Denna kernelisering kan implementeras i linjär tid . När kärnan väl har konstruerats kan problemet med vertextäckning lösas med en brute force- sökningsalgoritm som testar om varje delmängd av kärnan är en täckning av kärnan. Således kan vertextäckningsproblemet lösas i tiden $O(2^{2k^{2}}+n+m)$ för en graf med $n$ hörn och $m$ kanter, vilket gör att det kan lösas effektivt när $k$ är liten även om $n$ och $m$ båda är stora.

Även om denna gräns kan hanteras med fasta parametrar, är dess beroende av parametern högre än vad som kan vara önskvärt. Mer komplexa kerneliseringsprocedurer kan förbättra denna gräns, genom att hitta mindre kärnor, på bekostnad av längre körtid i kerneliseringssteget. I topplocksexemplet är kärnbildningsalgoritmer kända som producerar kärnor med högst $2k$ hörn. En algoritm som uppnår denna förbättrade gräns utnyttjar halvintegriteten i den linjära programavslappningen av vertextäckning på grund av Nemhauser och Trotter. En annan kerneliseringsalgoritm som uppnår den gränsen är baserad på vad som kallas kronreduktionsregeln och använder alternerande vägargument . Den för närvarande mest kända kerneliseringsalgoritmen när det gäller antalet hörn beror på Lampis (2011) och uppnår $2k-c\log k$ hörn för varje fast konstant $c$ .

Det är inte möjligt, i detta problem, att hitta en kärna av storleken ${\displaystyle O(\log k)} ,$ såvida inte P = NP, för en sådan kärna skulle leda till en polynom-tidsalgoritm för problemet med NP-hårda vertextäckning. Men mycket starkare gränser för kärnans storlek kan bevisas i det här fallet: om inte coNP $\subseteq$ NP/poly (tros osannolikt av komplexitetsteoretiker ), för varje $\epsilon >0$ är det omöjligt i polynomtid att hitta kärnor med $O(k^{2-\epsilon })$ kanter. Det är okänt för vertextäckning om kärnor med $(2-\epsilon )k$ hörn för vissa $\epsilon >0$ skulle ha några osannolika komplexitetsteoretiska konsekvenser.

Definition

I litteraturen finns det ingen tydlig konsensus om hur kärnbildning formellt ska definieras och det finns subtila skillnader i användningen av det uttrycket.

Downey–Fellows notation

I notationen av Downey & Fellows (1999) är ett parametriserat problem en delmängd $L\subseteq \Sigma ^{*}\times \mathbb {N}$ som beskriver ett beslutsproblem .

En kernelisering för ett parameteriserat problem $L$ är en algoritm som tar en instans $(x,k)$ och mappar den i tidspolynom i $|x|$ och $k$ till en instans $(x',k')$ så att

• $(x,k)$ är i $L$ om och endast om $(x',k')$ är i $L$ ,
• storleken på $x'$ begränsas av en beräkningsbar funktion $f$ i $k$ , och
• $k'$ begränsas av en funktion i $k$ .

Utgången $(x',k')$ från kernelisering kallas en kärna. I detta allmänna sammanhang hänvisar storleken på strängen ${\displaystyle x'} bara till dess längd.$ Vissa författare föredrar att använda antalet hörn eller antalet kanter som storleksmått i samband med grafproblem.

Flum–Grohe notation

I beteckningen av Flum & Grohe (2006 , s. 4) består ett parametriserat problem av ett beslutsproblem $L\subseteq \Sigma ^{*}$ och en funktion ${ \displaystyle \kappa :\Sigma ^{*}\to \mathbb {N} }$ , parametreringen. Parametern för en instans $x$ är talet $\displaystyle \kappa (x)}$ { .

En kärnisering för ett parameteriserat problem $L$ är en algoritm som tar en instans $x$ med parametern $k$ och mappar den i polynomtid till en instans $y$ så att

• $x$ är i $L$ om och endast om $y$ är i $L$ och
• storleken på $y$ begränsas av en beräkningsbar funktion $f$ i $k$ .

Observera att i denna notation innebär gränsen på storleken på $y$ att parametern för $y$ också begränsas av en funktion i $k$ .

Funktionen $f$ kallas ofta för storleken på kärnan. Om $f=k^{O(1)}$ sägs det att $L$ tillåter en polynomkärna. På liknande sätt, för ${\displaystyle f={O(k)}} ,$ medger problemet linjär kärna.

Kernelizerbarhet och spårbarhet med fasta parametrar är likvärdiga

Ett problem kan lösas med fasta parametrar om och bara om det är kärnlizerbart och avgörbart .

Att ett kärnlizerbart och avgörbart problem kan hanteras med fasta parametrar kan ses från definitionen ovan: Först kerneliseringsalgoritmen, som körs i tiden $O(|x|^{c})$ för vissa c, anropas för att generera en kärna av storleken $f(k)$ . Kärnan löses sedan av algoritmen som bevisar att problemet är avgörbart. Den totala körtiden för denna procedur är ${\displaystyle g(f(k))+O(|x|^{c})} ,$ där $g(n)$ är körtiden för algoritmen som används för att lösa kärnorna. Eftersom $g(f(k))$ beräkningsbar, t.ex. genom att använda antagandet att $f(k)$ är beräkningsbar och testa alla möjliga indata av längden $f(k)$ , detta innebär att problemet kan hanteras med fasta parametrar.

Den andra riktningen, att ett lösbart problem med fasta parametrar är kernelizbart och avgörbart är lite mer involverat. Antag att frågan är icke-trivial, vilket betyder att det finns minst en instans som finns i språket, kallad $I_{yes}$ , och minst en instans som inte finns i språket, kallas $I_{no}$ ; Annars är att ersätta valfri instans med den tomma strängen en giltig kärnisering. Antag också att problemet är löst med fasta parametrar, dvs det har en algoritm som körs i högst $f(k)\cdot |x|^{c}$ steg på instanser $(x,k)$ , för vissa konstanter $c$ och vissa funktioner $f(k)$ . För att kärnisera en ingång, kör den här algoritmen på den givna ingången för högst $|x|^{c+1}$ steg. Om det avslutas med ett svar, använd det svaret för att välja antingen $I_{yes}$ eller $I_{no}$ som kärna. Om det istället överskrider $|x|^{c+1}$ bunden till antalet steg utan att avsluta, returnera sedan $(x,k)$ sig själv som kärnan. Eftersom $(x,k)$ endast returneras som en kärna för indata med ${\displaystyle f(k)\cdot |x|^{c}>|x|^{c+1}} ,$ det följer att storleken på kärnan som produceras på detta sätt är högst $\max\{|I_{yes}|,|I_{no}|,f(k)\}$ . Denna storleksgräns är beräkningsbar, genom antagandet från följbarhet med fasta parametrar att $f(k)$ är beräkningsbar.

Fler exempel

• Vertextäcket parametriseras av storleken på vertextäcket: Vertextäckningsproblemet har kärnor med högst $2k$ hörn och $O(k^{2})$ kanter. Dessutom, för alla $\varepsilon >0$ , har vertextäcket inte kärnor med $O(k^{2-\varepsilon })$ kanter om inte ${\text{coNP}}\subseteq {\text{NP/poly}}$ . Problemen med vertextäckning i $d$ -uniform hypergraphs har kärnor med $O(k^{d})$ kanter med hjälp av solroslemma , och den har inte kärnor av storlek $O(k^{d-\varepsilon })$ om inte ${\text{coNP}}\subseteq {\text{NP/poly}}$ .
• Återkopplingspunktuppsättning parametriserad av storleken på återkopplingspunktuppsättningen: Problemet med återkopplingspunktuppsättning har kärnor med $4k^{2}$ hörn och $O(k^{2} )$ kanter. Dessutom har den inte kärnor med $O(k^{2-\varepsilon })$ kanter om inte ${\text{coNP}}\subseteq { \text{NP/poly}}$ .
• $k$ -path: ${\displaystyle k} -path-$ problemet är att avgöra om en given graf har en bana med längden minst $k$ . Det här problemet har kärnor av storleken exponentiell i $k$ , och det har inte kärnor av storleken polynom i $k$ om inte ${\text{coNP}}\subseteq { \text{NP/poly}}$ .
• Tvådimensionella problem: Många parametriserade versioner av tvådimensionella problem har linjära kärnor på plana grafer, och mer allmänt på grafer som exkluderar någon fast graf som en mindre .

Kernelisering för strukturella parametreringar

Även om parametern $k$ i exemplen ovan är vald som storleken på den önskade lösningen, är detta inte nödvändigt. Det är också möjligt att välja ett strukturellt komplexitetsmått på ingången som parametervärde, vilket leder till så kallade strukturella parametriseringar. Detta tillvägagångssätt är fruktbart för fall vars lösningsstorlek är stor, men för vilka något annat komplexitetsmått är begränsat. Till exempel definieras återkopplingspunktnumret för en oriktad graf ${\displaystyle G} som den lägsta kardinaliteten för en uppsättning hörn vars borttagning gör$$G$ acyklisk. Problemet vertextäckning parametrerat av återkopplingspunktnumret för ingångsgrafen har en polynomisk kärnbildning: Det finns en polynom-tidsalgoritm som, givet en graf $G$ vars återkopplingspunktnummer är $k$ , matar ut en graf $G'$ på $O(k^{3})$ hörn så att ett minimalt vertextäcke i $G'$ kan omvandlas till ett minimum vertextäcke för $G$ i polynomtid. Kerneliseringsalgoritmen garanterar därför att instanser med ett litet återkopplingspunktnummer $k$ reduceras till små instanser.

Se även

• Iterativ komprimering , en annan designteknik för algoritmer med fasta parametrar
• Ungefärlig kärnbildning , för optimeringsproblem kan en kärna förlora en given faktor i lösningens kvalitet

Anteckningar

• Abu-Khzam, Faisal N.; Collins, Rebecca L.; Fellows, Michael R. ; Langston, Michael A .; Suters, W. Henry; Symons, Chris T. (2004), Kerneliseringsalgoritmer för Vertex Cover Problem: Theory and Experiments (PDF) , University of Tennessee .
• Bodlaender, Hans L. ; Downey, Rod G. ; Fellows, Michael R. ; Hermelin, Danny (2009), "Om problem utan polynomiska kärnor", Journal of Computer and System Sciences , 75 (8): 423–434, doi : 10.1016/j.jcss.2009.04.001 .
•   Buss, Jonathan F.; Goldsmith, Judy (1993), "Nondeterminism within $P^{*}$ " , SIAM Journal on Computing , 22 (3): 560–572, doi : 10.1137/0222038 , S2CID 43081484 .
•   Chen, Jianer; Kanj, Iyad A.; Jia, Weijia (2001), "Vertex cover: Further observations and further improvements" , Journal of Algorithms , 41 (2): 280–301, doi : 10.1006/jagm.2001.1186 , S2CID 13557005 .
•   Dell, Holger; van Melkebeek, Dieter (2010), "Satisfiability tillåter ingen icke-trivial sparsifiering om inte polynom-tidshierarkin kollapsar" (PDF) , Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC 2010) , s. 251–1:260 , do . /1806689.1806725 , S2CID 1117711 .
• Downey, RG ; Fellows, MR (1999), Parameterized Complexity , Monographs in Computer Science, Springer,     : 10.1007 /978-1-4612-0515-9 , ISBN 0-387-94883-X , MR 1656112 , 5271ID 5271ID 5271ID doi
•   Flum, Jörg; Grohe, Martin (2006), Parameterized Complexity Theory , Springer, ISBN 978-3-540-29952-3 , hämtad 2010-03-05 .
• Fomin, Fedor V.; Lokshtanov, Daniel; Saurabh, Saket; Thilikos, Dimitrios M. (2010), "Bidimensionality and kernels", Proceedings of the 21st ACM-SIAM Symposium on Discrete Algorithms (SODA 2010) , s. 503–510 .
• Jansen, Bart MP; Bodlaender, Hans L. (2013), "Vertex Cover Kernelization Revisited - Upper and Lower Bounds for a Refined Parameter", Theory Comput. Syst. , 53 (2): 263–299, doi : 10.1007/s00224-012-9393-4 ,
• Lampis, Michael (2011), "A kernel of order 2 k − c log k for vertex cover", Information Processing Letters , 111 (23–24): 1089–1091, doi : 10.1016/j.ipl.2011.09.003 .
•   Thomassé, Stéphan (2010), "A 4 k ² kernel for feedback vertex set", ACM Transactions on Algorithms , 6 (2): 1–8, doi : 10.1145/1721837.1721848 , S2CID 7510317 .
•   Niedermeier, Rolf (2006), Invitation to Fixed-Parameter Algorithms , Oxford University Press, ISBN 0-19-856607-7 , arkiverad från originalet 2008-09-24 , hämtad 2017-06-01 .

Vidare läsning

•   Fomin, Fedor V.; Lokshtanov, Daniel; Saurabh, Saket; Zehavi, Meirav (2019), Kernelization: Theory of Parameterized Preprocessing , Cambridge University Press, sid. 528, doi : 10.1017/9781107415157 , ISBN 978-1107057760
•   Niedermeier, Rolf (2006), Invitation to Fixed-Parameter Algorithms , Oxford University Press, Kapitel 7, ISBN 0-19-856607-7 , arkiverad från originalet 2007-09-29 , hämtad 2017-06-01
•   Cygan, Marek; Fomin, Fedor V.; Kowalik, Lukasz; Lokshtanov, Daniel; Marx, Daniel; Pilipczuk, Marcin; Pilipczuk, Michal; Saurabh, Saket (2015), Parameterized Algorithms , Springer, kapitel 2 och 9, ISBN 978-3-319-21274-6