Parametrisk minskning

Parametrisk reduktion är en teknik för att designa effektiva algoritmer som uppnår sin effektivitet genom ett förprocessorsteg där algoritmens inmatning ersätts av en mindre ingång som kallas "kärnan". Resultatet av att lösa problemet på kärnan måste antingen vara detsamma som för de initiala data, eller också måste utdata från lösningen för kärnan enkelt omvandlas till den önskade utdata från det ursprungliga problemet.

Parametrisk reduktion uppnås ofta genom att tillämpa en uppsättning reduktionsregler som skär bort den del av ett visst problem som är lätt att hantera. I parameteriserad komplexitetsteori , kan man ofta bevisa att en kärna med garanterade gränser beroende på storleken på kärnan (som en funktion av vissa problemrelaterade parametrar) kan hittas i polynomtid . Om möjligt kommer resultatet att bli en fast-parametriskt avgörbar -algoritm vars körtid är summan av (polynomtiden) parametriska reduktionssteget och den (icke-polynomiska men parameterbegränsade) tiden för att lösa kärnan. Dessutom kan alla problem som kan lösas med en lösbar algoritm med fasta parametrar lösas med en parametrisk reduktionsalgoritm av denna typ.

Exempel: vertex täckning

Ett standardexempel på en parametrisk reduktionsalgoritm är den parametriska reduktionen av vertextäckningsproblemet med S. Bass [1] . I det här problemet är inmatningen en oriktad graf tillsammans med ett nummer . Utdata är en maximal vertexuppsättning som inkluderar slutpunkten för varje graf om en sådan uppsättning finns, eller ett misslyckande undantag om en sådan uppsättning inte finns. Det här problemet är NP-svårt . Följande regler kan dock användas för dess parametriska minskning: $G$ $k$ $k$

Om och är en vertex som är större än , ta bort från grafen och minska med en. Alla problem med topptäckning av storlek måste innehålla , eftersom annars för många av dess grannar skulle väljas för att täcka de infallande kanterna. Således kan det optimala vertextäcket för den ursprungliga grafen bildas från det reducerade problemskyddet genom att lägga tillbaka till omslaget. $k>0$ $v$ $k$ $v$ $k$ $k$ $v$ $v$
Om det är en isolerad vertex, ta bort den. En isolerad vertex kan inte täcka någon kant, så i det här fallet kan inte vara en del av någon minimitäckning. $v$ $v$
Om mer än kanter finns kvar i grafen och inga föregående två regler kan tillämpas, kan grafen inte innehålla ett vertextäcke av storlek . Efter att ha tagit bort alla hörn som är större än , kan varje återstående hörn täcka de flesta kanterna, och uppsättningen av hörn kan täcka de flesta kanterna. I det här fallet kan inmatningen av problemet ersättas av en graf med två hörn, en kant och värdet , och detta problem har inte heller någon lösning. $k^{2}$ $k$ $k$ $k$ $k$ $k^{2}$ $k=0$

En algoritm som återanvänder dessa regler tills inga ytterligare minskningar kan göras, avslutas nödvändigtvis med en kärna som har högst kanter och (eftersom varje kant har högst två terminala hörn och inga isolerade hörn) vid de flesta hörn. Denna parametriska minskning kan göras i linjär tid . När kärnan väl är byggd kan problemet med vertextäckning lösas med en brute force- algoritm , som kontrollerar att varje delmängd av kärnan är ett kärnhölje. Därmed kan vertextäckningsproblemet lösas i tid för en graf med hörn och kanter, vilket gör att de kan lösas effektivt när de är små, även om de är stora . $k^{2}$ ${\displaystyle 2k^{2))$ $O(2^{2k^{2))+n+m)$ $n$ $m$ $k$ $n$ $m$

Även om denna gräns är fast-parametriskt lösbar, är dess beroende av parametern högre än man skulle kunna önska. Mer komplexa parametriska reduktionsprocedurer kan förbättra denna gräns genom att hitta mindre kärnor till priset av mer tid i det parametriska reduktionssteget. Algoritmer för problem med vertextäckning med parametrisk reduktion är kända, vilka ger maximala kärnor med hörn. Algoritmen som uppnår denna förbättrade gräns använder halvheltalsrelaxationen av vertextäckningsproblemet genom ett linjärt programmeringsproblem enligt George Nemhauser och Trotter [2] . En annan parametrisk reduktionsalgoritm som uppnår denna gräns är baserad på ett trick som kallas kronreduktionsregeln och använder vägväxlingsargument [3] . För närvarande är den mest kända parametriska reduktionsalgoritmen vad gäller antalet hörn på grund av Lampis [4] och uppnår hörn för vilken konstant som helst . $2k$ $2k-c\log k$ $c$

Det är omöjligt för detta problem att hitta en kärna av storlek om inte P=NP, i vilket fall kärnan skulle leda till en polynomalgoritm för NP-hårda vertextäckningsproblem. Men snävare gränser för storleken på kärnan kan bevisas i detta fall - såvida inte coNP NP/poly (vilket beräkningskomplexitetsteoretiker anser osannolikt), är det omöjligt för någon att hitta kärnor med kanter i polynomtid [5] . $O(\log k)$ $\subseteq$ $\epsilon >0$ $O(k^{2-\epsilon })$

Definition

Det finns ingen tydlig konsensus i litteraturen om hur parametrisk reduktion formellt ska definieras, och det finns en subtil skillnad i användningen av sådana uttryck.

Downey-Fellows notation

I Downey-Fellowes-notationen [6] är ett parametriserat problem en delmängd som beskriver lösbarhetsproblemet . $L\subseteq \Sigma ^{*}\times \mathbb {N}$

Parametrisk reduktion av ett parametriserat problem är en algoritm som tar en representant och avbildar den i tid polynomiskt i och till en representant , så att $L$ $(x, k)$ $|x|$ $k$ $(x',k')$

$(x, k)$ går in om och bara om går in , $L$ $(x',k')$ $L$
storleken begränsas av en beräkningsbar funktion av $x'$ $f$ $k$
$k'$ begränsad till en beräkningsbar funktion av . $k$

Utdata från parametrisk reduktion kallas kärnan. I det här allmänna sammanhanget hänvisas ofta till storleken på en sträng som dess längd. Vissa författare föredrar antalet hörn eller antalet kanter som storlek i samband med grafproblem. $(x',k')$ $x'$

Flams beteckning är Grohe

I Flam-Grohe-notationen [7] består ett parametriserat problem av ett beslutsproblem och en funktion , själva parametriseringen. Den uppgiftsrepresentativa parametern är ett tal . $L\subseteq \Sigma ^{*}$ $\kappa :\Sigma ^{*}\to \mathbb {N}$ $x$ $\kappa (x)$

Parametrisk reduktion för ett parameteriserat problem är en algoritm som tar en representant med en parameter och mappar den i polynomtid till en representant så att $L$ $x$ $k$ $y$

$x$ går in om och bara om det går in $L$ $y$ $L$
storleken begränsas av en beräkningsbar funktion av . $y$ $f$ $k$

Observera att storleksgränsen i denna notation innebär att parametern också begränsas av en funktion av . $y$ $y$ $k$

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

Parametrisk reducerbarhet och fixparametrisk lösbarhet är likvärdiga

Ett problem är fast-parametriskt lösbart om och bara om det kan reduceras parametriskt och det är lösbart .

Att ett parametriskt reducerbart och lösbart problem är fast-parametriskt lösbart framgår av definitionen ovan: en parametrisk reduktionsalgoritm som körs i tid för något c anropas för att få en kärna av storlek . Kärnan löses sedan av en algoritm som kontrollerar att problemet är lösbart. Den totala körtiden för denna procedur är , där är körtiden för algoritmen som används för att lösa kärnorna. Eftersom det är beräkningsbart, till exempel under antagandet att det är beräkningsbart, men kan beräknas genom uppräkning av alla möjliga indata av längd , följer det att problemet är fast-parametriskt lösbart. $O(|x|^{c})$ $f(k)$ $g(f(k))+O(|x|^{c})$ $g(n)$ $g(f(k))$ $f(k)$ $g(f(k))$ $f(k)$

Beviset åt andra hållet för att ett fixerat parametriskt lösbart problem är parametriskt reducerbart och lösbart är lite svårare. Anta att frågan är icke-trivial, vilket betyder att det finns minst en uppgiftsrepresentant som heter , som tillhör språket, och minst en uppgiftsrepresentant, som inte tillhör språket, heter . Annars är det en giltig parametrisk minskning att ersätta en representant med en tom sträng. Låt oss också anta att problemet är fast-parametriskt lösbart, det vill säga det har en algoritm som som mest fungerar i steg på representanter för problemet för någon konstant och någon funktion . För att implementera den parametriska reduktionen av ingången tillämpar vi algoritmen på en given ingång i maximalt steg. Om algoritmen slutar med ett svar, använd svaret för att välja antingen eller som kärna. Om vi istället når gränsen för antalet steg utan avbrott returnerar vi själva uppgiften som kärnan. Eftersom den returneras som indatakärnan med , följer det att storleken på kärnan som erhålls på detta sätt inte överstiger . Storleksgränsen är beräkningsbar under antaganden om fast-parametrisk lösbarhet, som är beräkningsbar. $I_{yes}$ $I_{no}$ ${\displaystyle f(k)\cdot |x|^{c))$ $(x, k)$ $c$ $f(k)$ $|x|^{c+1}$ $I_{yes}$ $I_{no}$ $|x|^{c+1}$ $(x, k)$ $(x, k)$ ${\displaystyle f(k)\cdot |x|^{c}>|x|^{c+1))$ ${\displaystyle \max\{|I_{yes}|,|I_{no}|,f(k)\))$ $f(k)$

Andra exempel

Vertex Cover: Problemet med vertex cover har kärnor med maximala hörn och kanter [8] . Dessutom, för alla , har vertextäckningsproblemet inga kärnor med kanter, såvida inte {coNP} {NP/poly} [5] . Problemet med vertextäckning i -homogena hypergrafer har kärnor med kanter, med hjälp av solroslemmat , och har inga kärnor av storlek om inte coNP NP/poly [5] . $2k$ $O(k^{2})$ $\varepsilon >0$ $O(k^{2-\varepsilon })$ $\subseteq$ $d$ $O(k^{d})$ $O(k^{d-\varepsilon })$ $\subseteq$
Cykelskärande vertexuppsättning : Problemet med cykelskärande vertexuppsättning har kärnor med hörn och kanter [9] . Dessutom har problemet inga kärnor med hörn, såvida inte coNP NP/poly [5] . $4k^{2}$ $O(k^{2})$ $O(k^{2-\varepsilon })$ $\subseteq$
k-väg: Problemet med k-väg är att avgöra om en given graf har en väg med minst längd . Detta problem har en kärna av storlek som beror exponentiellt på , och inga kärnor av storlek som beror polynomiskt på , såvida inte coNP NP/poly [10] . $k$ $k$ $k$ $\subseteq$
2D-problem : Många parametriserade versioner av 2D- problem har linjära kärnor på plana grafer, och mer allmänt på grafer som inte innehåller någon fast graf som underordnad [11] .

Se även

Iterativ komprimering , en annan teknik för att utveckla fast-parametriskt lösbara algoritmer

Anteckningar

↑ Denna opublicerade observation anges i en artikel av Buss and Goldsmith ( Buss, Goldsmith 1993 )
↑ Flum, Grohe, 2006 .
↑ Flam och Grohe ( Flum, Grohe 2006 ) ger en kärna baserad på kronreduktion som har hörn. Hönsgränsen är lite mer komplex. $3k$ $2k$
↑ Lampis, 2011 .
↑ 1 2 3 4 Dell, van Melkebeek, 2010 .
↑ Downey, Fellows, 1999 .
↑ Flum, Grohe, 2006 , sid. fyra.
↑ Chen, Kanj, Jia, 2001 .
↑ Thomasse, 2010 .
↑ Bodlaender, Downey, Fellows, Hermelin, 2009 .
↑ Fomin, Lokshtanov, Saurabh, Thilikos, 2010 .

Litteratur

Faisal N. Abu-Khzam, Rebecca L. Collins, Michael R. Fellows, Michael A. Langston, W. Henry Suters, Chris T. Symons. Kerneliseringsalgoritmer för Vertex Cover Problem: Teori och experiment . — University of Tennessee, 2004.
Hans L. Bodlaender, Rod G. Downey, Michael R. Fellows, Danny Hermelin. Om problem utan polynomkärnor // Journal of Computer and System Sciences . - 2009. - T. 75 , nr. 8 . - S. 423-434 . - doi : 10.1016/j.jcss.2009.04.001 .
Jonathan F. Buss, Judy Goldsmith. Nondeterminism inom P // SIAM Journal on Computing . - 1993. - T. 22 , nr. 3 . - S. 560-572 . - doi : 10.1137/0222038 .
Jianer Chen, Iyad A. Kanj, Weijia Jia. Vertex cover: Ytterligare observationer och ytterligare förbättringar // Journal of Algorithms. - 2001. - T. 41 , nr. 2 . - S. 280-301 . - doi : 10.1006/jagm.2001.1186 .
Holger Dell, Dieter van Melkebeek. Tillfredsställelse tillåter ingen icke-trivial sparsifiering om inte polynom-tidshierarkin kollapsar //Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC 2010) . - 2010. - S. 251-260. - doi : 10.1145/1806689.1806725 .
RG Downey, MR-stipendiater. Parameteriserad komplexitet. - Springer, 1999. - ISBN 0-387-94883-X . - doi : 10.1007/978-1-4612-0515-9 .
Jörg Flum, Martin Grohe. Parameteriserad komplexitetsteori . - Springer, 2006. - ISBN 978-3-540-29952-3 .
Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, Dimitrios M. Thilikos. Bidimensionalitet och kärnor // Proceedings of the 21st ACM-SIAM Symposium on Discrete Algorithms (SODA 2010). - 2010. - S. 503-510.
Michael Lampis. En kärna av ordningen 2 k − c log k för vertex cover // Information Processing Letters . - 2011. - T. 111 , nr. 23-24 . - S. 1089-1091 . - doi : 10.1016/j.ipl.2011.09.003 .
Stephan Thomasse. En 4 k 2 kärna för feedback vertex set // ACM Transactions on Algoritms. - 2010. - T. 6 , nr. 2 .
Rolf Niedermeier. Inbjudan till algoritmer med fasta parametrar . - Oxford University Press, 2006. - ISBN 0-19-856607-7 . .