Reducere parametrică

Reducerea parametrică este o tehnică de proiectare a algoritmilor eficienți care își ating eficiența printr-un pas de preprocesor în care intrarea algoritmului este înlocuită cu o intrare mai mică numită „kernel”. Rezultatul rezolvării problemei pe nucleu trebuie fie să fie același ca pentru datele inițiale, fie rezultatul soluției pentru nucleu trebuie să fie ușor transformat în rezultatul dorit al problemei inițiale.

Reducerea parametrică este adesea realizată prin aplicarea unui set de reguli de reducere care elimină partea unei anumite probleme care este ușor de rezolvat. În teoria complexității parametrizate , se poate dovedi adesea că un nucleu cu limite garantate în funcție de dimensiunea nucleului (în funcție de unii parametri legați de problemă) poate fi găsit în timp polinomial . Dacă este posibil, rezultatul va fi fix-rezolvabil parametric un algoritm al cărui timp de rulare este suma pasului (timpul polinom) al reducerii parametrice și timpul (nepolinom, dar mărginit de parametru) de rezolvare a nucleului. Mai mult, orice problemă care poate fi rezolvată printr-un algoritm solubil cu parametri fix poate fi rezolvată printr-un algoritm de reducere parametrică de acest tip.

Exemplu: acoperirea nodurilor

Un exemplu standard de algoritm de reducere parametrică este reducerea parametrică a problemei acoperirii vârfurilor de către S. Bass [1] . În această problemă, intrarea este un grafic nedirecționat împreună cu un număr . Ieșirea este un set de vârfuri maxim care include vârful final al fiecărui grafic dacă există o astfel de mulțime sau o excepție de eșec dacă un astfel de set nu există. Această problemă este NP-hard . Cu toate acestea, următoarele reguli pot fi utilizate pentru reducerea parametrică a acestuia: $G$ $k$ $k$

Dacă și este un vârf de grad mai mare decât , eliminați din grafic și micșorați cu unu. Orice problemă de acoperire a vârfurilor de dimensiune trebuie să conțină , deoarece altfel ar fi aleși prea mulți dintre vecinii săi pentru a acoperi marginile incidente. Astfel, acoperirea optimă a vârfurilor pentru graficul original poate fi formată din acoperirea problemei reduse prin adăugarea înapoi la capac. $k>0$ $v$ $k$ $v$ $k$ $k$ $v$ $v$
Dacă este un vârf izolat, ștergeți-l. Un vârf izolat nu poate acoperi nicio margine, deci în acest caz nu poate face parte dintr-o acoperire minimă. $v$ $v$
Dacă în grafic rămân mai multe muchii și nu pot fi aplicate două reguli anterioare, atunci graficul nu poate conține o acoperire de vârf de dimensiune . După eliminarea tuturor vârfurilor de grad mai mare decât , fiecare vârf rămas poate acoperi cel mai mult muchii, iar setul de vârfuri poate acoperi cel mult muchii. În acest caz, intrarea problemei poate fi înlocuită cu un grafic cu două vârfuri, o muchie și valoarea , iar această problemă, de asemenea, nu are soluție. $k^{2}$ $k$ $k$ $k$ $k$ $k^{2}$ $k=0$

Un algoritm care reaplică aceste reguli până când nu se mai pot face reduceri ulterioare se termină neapărat cu un nucleu care are cel mult muchii și (deoarece fiecare muchie are cel mult două vârfuri terminale și niciun vârf izolat) cel mult vârfuri. Această reducere parametrică se poate face în timp liniar . Odată construit nucleul, problema acoperirii nodurilor poate fi rezolvată printr-un algoritm de forță brută , care verifică dacă fiecare subset al nucleului este o acoperire a nucleului. Astfel, problema acoperirii nodurilor poate fi rezolvată în timp pentru un grafic cu vârfuri și muchii, ceea ce le permite să fie rezolvate eficient atunci când sunt mici, chiar dacă mari . $k^{2}$ $2k^{2}$ $O(2^{2k^{2))+n+m)$ $n$ $m$ $k$ $n$ $m$

Deși această limită este fixă-parametric rezolvabilă, dependența sa de parametru este mai mare decât s-ar putea dori. Procedurile mai complexe de reducere parametrică pot îmbunătăți această limită prin găsirea de nuclee mai mici cu costul a mai mult timp în etapa de reducere parametrică. Sunt cunoscuți algoritmi pentru problema acoperirii vârfurilor a reducerii parametrice, care dau nuclee maxime cu vârfuri. Algoritmul care realizează această limită îmbunătățită folosește relaxarea pe jumătate întreg a problemei acoperirii vârfurilor printr-o problemă de programare liniară conform lui George Nemhauser și Trotter [2] . Un alt algoritm de reducere parametrică care realizează această limită se bazează pe un truc numit regula de reducere a coroanei și folosește argumente de alternanță a căii [3] . În prezent, cel mai cunoscut algoritm de reducere parametrică în ceea ce privește numărul de vârfuri se datorează lui Lampis [4] și realizează vârfuri pentru orice constantă . $2k$ $2k-c\log k$ $c$

Este imposibil ca această problemă să găsească un nucleu de dimensiune decât dacă P=NP, caz în care nucleul ar duce la un algoritm polinomial pentru problema acoperirii vertexului NP-hard. Cu toate acestea, limite mai strânse ale mărimii nucleului pot fi dovedite în acest caz - cu excepția cazului în care conNP NP/poly (pe care teoreticienii complexității computaționale îl consideră puțin probabil), este imposibil pentru cineva să găsească nuclee cu muchii în timp polinomial [5] . $O(\log k)$ $\subseteq$ $\epsilon >0$ $O(k^{2-\epsilon })$

Definiție

Nu există un consens clar în literatură cu privire la modul în care reducerea parametrică ar trebui definită formal și există o diferență subtilă în utilizarea unor astfel de expresii.

Notație Downey-Fellows

În notația Downey-Fellowes [6] , o problemă parametrizată este o submulțime care descrie problema de solubilitate . $L\subseteq \Sigma ^{*}\times \mathbb {N}$

Reducerea parametrică a unei probleme parametrizate este un algoritm care ia un reprezentant și îl mapează în timp polinom în și către un reprezentant , astfel încât $L$ $(x, k)$ $|x|$ $k$ $(x',k')$

$(x, k)$ intră dacă și numai dacă intră , $L$ $(x',k')$ $L$
dimensiunea este limitată de o funcție calculabilă de $X'$ $f$ $k$
$k'$ limitată la o funcție calculabilă de . $k$

Ieșirea reducerii parametrice se numește nucleu. În acest context general , dimensiunea unui șir este adesea denumită lungimea sa. Unii autori preferă numărul de vârfuri sau numărul de muchii ca mărime în contextul problemelor de graf. $(x',k')$ $X'$

Denumirea lui Flam este Grohe

În notația Flam-Grohe [7] , o problemă parametrizată constă dintr- o problemă de decizie și o funcție , parametrizarea însăși. Parametrul reprezentativ al sarcinii este un număr . $L\subseteq \Sigma ^{*}$ $\kappa:\Sigma ^{*}\la \mathbb {N}$ $X$ $\kappa (x)$

Reducerea parametrică pentru o problemă parametrizată este un algoritm care ia un reprezentant cu un parametru și îl mapează în timp polinomial la un reprezentant astfel încât $L$ $X$ $k$ $y$

$X$ intră dacă și numai dacă intră $L$ $y$ $L$
dimensiunea este limitată de o funcție calculabilă de . $y$ $f$ $k$

Rețineți că în această notație limita de dimensiune implică faptul că parametrul este , de asemenea, mărginit de o funcție de . $y$ $y$ $k$

Funcția este adesea denumită dimensiunea nucleului. Dacă se spune că admite un nucleu polinom. În mod similar, pentru problemă admite un nucleu liniar. $f$ $f=k^{O(1)}$ $L$ $f={O(k)}$

Reductibilitatea parametrică și solvabilitatea parametrică fixă sunt echivalente

O problemă este fixată-parametric rezolvabilă dacă și numai dacă poate fi redusă parametric și este rezolvabilă .

Că o problemă reductibilă și rezolvabilă parametric este fix-parametric rezolvabilă se poate vedea din definiția de mai sus: un algoritm de reducere parametrică care rulează în timp pentru un anumit c este invocat pentru a obține un nucleu de dimensiune . Nucleul este apoi rezolvat de un algoritm care verifică dacă problema este rezolvabilă. Timpul total de rulare al acestei proceduri este , unde este timpul de rulare al algoritmului utilizat pentru rezolvarea nucleelor. Deoarece este calculabil, de exemplu, sub ipoteza că este calculabil, dar poate fi calculat prin enumerarea tuturor intrărilor posibile de lungime , rezultă că problema este rezolvabilă fix-parametric. $O(|x|^{c})$ $f(k)$ $g(f(k))+O(|x|^{c})$ $g(n)$ $g(f(k))$ $f(k)$ $g(f(k))$ $f(k)$

Dovada în cealaltă direcție că o problemă fixă rezolvabilă parametric este reductibilă și rezolvabilă este puțin mai dificilă. Să presupunem că întrebarea este netrivială, ceea ce înseamnă că există cel puțin un reprezentant al sarcinii numit , aparținând limbii și cel puțin un reprezentant al sarcinii, care nu aparține limbii, numit . În caz contrar, înlocuirea oricărui reprezentant cu un șir gol este o reducere parametrică validă. Să presupunem, de asemenea, că problema este rezolvabilă fix-parametric, adică are un algoritm care funcționează cel mult în pași pe reprezentanți ai problemei pentru o constantă și o anumită funcție . Pentru a implementa reducerea parametrică a intrării, aplicăm algoritmul pe o intrare dată în maximum pași. Dacă algoritmul se termină cu un răspuns, utilizați răspunsul pentru a alege oricare sau ca nucleu. Dacă, în schimb, ajungem la limita numărului de pași fără întrerupere, returnăm sarcina în sine ca nucleu. Deoarece este returnat ca nucleu de intrare cu , rezultă că dimensiunea nucleului obținut în acest mod nu depășește . Limita mărimii este calculabilă în baza ipotezelor de solvabilitate parametrică fixă, care este calculabilă. $I_{da}$ $I_{nu}$ $f(k)\cdot |x|^{c)$ $(x, k)$ $c$ $f(k)$ $|x|^{c+1}$ $I_{da}$ $I_{nu}$ $|x|^{c+1}$ $(x, k)$ $(x, k)$ $f(k)\cdot |x|^{c}>|x|^{c+1)$ ${\displaystyle \max\{|I_{da}|,|I_{nu}|,f(k)\))$ $f(k)$

Alte exemple

Acoperire cu vârfuri: Problema acoperirii cu vârfuri are nuclee cu vârfuri și muchii maxime [8] . Mai mult, pentru orice , problema acoperirii vârfurilor nu are nuclee cu margini, cu excepția cazului în care {coNP} {NP/poly} [5] . Problema acoperirii vârfurilor în hipergrafele -omogene are sâmburi cu margini, folosind lema floarea soarelui , și nu are sâmburi de dimensiune decât dacă conNP NP/poly [5] . $2k$ $O(k^{2})$ $\varepsilon >0$ $O(k^{2-\varepsilon })$ $\subseteq$ $d$ $O(k^{d})$ $O (k^{d-\varepsilon })$ $\subseteq$
Setul de vârfuri de tăiere ciclului: Problema setului de vârfuri de tăiere ciclului are nuclee cu vârfuri și muchii [9] . Mai mult, problema nu are nuclee cu vârfuri, cu excepția cazului în care conNP NP/poly [5] . $4k^{2}$ $O(k^{2})$ $O(k^{2-\varepsilon })$ $\subseteq$
k-Path: problema k-path este de a decide dacă un anumit grafic are o cale de cel puțin . Această problemă are un nucleu de dimensiune care depinde exponențial de , și nici un nucleu de dimensiune care depinde polinomial de , cu excepția cazului în care conNP NP/poli [10] . $k$ $k$ $k$ $\subseteq$
Probleme 2D : Multe versiuni parametrizate ale problemelor 2D au nuclee liniare pe grafice plane și, mai general, pe grafice care nu conțin un graf fix ca minor [11] .

Vezi și

Compresia iterativă , o altă tehnică de dezvoltare a algoritmilor fixați-parametric rezolvabili

Note

↑ Această observație nepublicată a fost afirmată într-un articol de Buss și Goldsmith ( Buss, Goldsmith 1993 )
↑ Flum, Grohe, 2006 .
↑ Flam și Grohe ( Flum, Grohe 2006 ) oferă un nucleu bazat pe reducerea coroanei care are vârfuri. Limita vârfurilor este puțin mai complexă. $3k$ $2k$
↑ Lampis, 2011 .
↑ 1 2 3 4 Dell, van Melkebeek, 2010 .
↑ Downey, Fellows, 1999 .
↑ Flum, Grohe, 2006 , p. patru.
↑ Chen, Kanj, Jia, 2001 .
↑ Thomasse, 2010 .
↑ Bodlaender, Downey, Fellows, Hermelin, 2009 .
↑ Fomin, Lokshtanov, Saurabh, Thilikos, 2010 .

Literatură

Faisal N. Abu-Khzam, Rebecca L. Collins, Michael R. Fellows, Michael A. Langston, W. Henry Suters, Chris T. Symons. Algoritmi de kernelizare pentru problema acoperirii vârfurilor: teorie și experimente . - Universitatea din Tennessee, 2004.
Hans L. Bodlaender, Rod G. Downey, Michael R. Fellows, Danny Hermelin. Despre probleme fără nuclee polinomiale // 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 în cadrul P // SIAM Journal on Computing . - 1993. - T. 22 , nr. 3 . - S. 560-572 . - doi : 10.1137/0222038 .
Jianer Chen, Iyad A. Kanj, Weijia Jia. Coperta de vârf: Observații suplimentare și îmbunătățiri ulterioare // Journal of Algorithms. - 2001. - T. 41 , nr. 2 . - S. 280-301 . - doi : 10.1006/jagm.2001.1186 .
Holger Dell, Dieter van Melkebeek. Satisfiabilitatea nu permite sparsificarea netrivială decât dacă ierarhia polinomială-timp se prăbușește //Proceedings of the 42th ACM Symposium on Theory of Computing (STOC 2010) . - 2010. - S. 251-260. - doi : 10.1145/1806689.1806725 .
RG Downey, MR Fellows. Complexitate parametrizată. - Springer, 1999. - ISBN 0-387-94883-X . - doi : 10.1007/978-1-4612-0515-9 .
Jörg Flum, Martin Grohe. Teoria complexității parametrizate . - Springer, 2006. - ISBN 978-3-540-29952-3 .
Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, Dimitrios M. Thilikos. Bidimensionalitate și nuclee // Proceedings of the 21st ACM-SIAM Symposium on Discrete Algorithms (SODA 2010). - 2010. - S. 503-510.
Michael Lampis. Un nucleu de ordinul 2 k − c log k pentru acoperirea vârfurilor // Litere de procesare a informațiilor . - 2011. - T. 111 , nr. 23-24 . - S. 1089-1091 . - doi : 10.1016/j.ipl.2011.09.003 .
Stephan Thomasse. Un nucleu de 4 k 2 pentru un set de vârfuri de feedback // ACM Transactions on Algorithms. - 2010. - T. 6 , nr. 2 .
Rolf Niedermeier. Invitație la algoritmi cu parametri fixe . - Oxford University Press, 2006. - ISBN 0-19-856607-7 . .