Parametrinen vähennys

Parametrinen pelkistys on tekniikka tehokkaiden algoritmien suunnittelemiseksi , jotka saavuttavat tehokkuutensa esiprosessorivaiheen kautta, jossa algoritmin syöte korvataan pienemmällä syötteellä, jota kutsutaan "ytimeksi". Ytimen ongelman ratkaisun tuloksen tulee olla joko sama kuin lähtötiedoilla tai ytimen ratkaisun tulos on helposti muutettava alkuperäisen ongelman halutuksi tuotokseksi.

Parametrinen vähennys saavutetaan usein soveltamalla vähennyssääntöjä, jotka katkaisevat tietystä ongelmasta sen osan, joka on helppo käsitellä. Parametrisoidussa kompleksisuusteoriassa voidaan usein todistaa, että ydin, jolla on ytimen koosta riippuen taatut rajat ( joidenkin ongelmaan liittyvien parametrien funktiona), löytyy polynomiajasta . Jos mahdollista, tulos on kiinteä-parametrisesti ratkaistava algoritmi, jonka ajoaika on parametrisen pelkistyksen (polynomiajan) vaiheen ja ytimen ratkaisemiseen kuluvan (ei-polynomisen, mutta parametrirajoitetun) ajan summa. Lisäksi mikä tahansa ongelma, joka voidaan ratkaista kiinteän parametrin ratkaistavalla algoritmilla, voidaan ratkaista tämän tyyppisellä parametrisella pelkistysalgoritmilla.

Esimerkki: vertex coverage

Standardiesimerkki parametrisesta pelkistysalgoritmista on S. Bassin [1] vertex cover -ongelman parametrinen pelkistys . Tässä tehtävässä syöte on suuntaamaton graafi yhdessä luvun kanssa . Tulos on maksimipistejoukko , joka sisältää kunkin graafin loppupisteen, jos sellainen on olemassa, tai epäonnistuneen poikkeuksen, jos tällaista joukkoa ei ole olemassa. Tämä ongelma on NP-kova . Sen parametriseen vähentämiseen voidaan kuitenkin käyttää seuraavia sääntöjä: $G$ $k$ $k$

Jos ja on asteen kärkipiste suurempi kuin , poista kaaviosta ja vähennä yhdellä. Minkä tahansa kokoisen kärjen peittotehtävän tulee sisältää , koska muuten liian monta sen naapuria valitaan peittämään sattuvia reunoja. Näin ollen optimaalinen kärkipeite alkuperäiselle graafille voidaan muodostaa pelkistetystä ongelmapeitosta lisäämällä sitä takaisin kanteen. $k>0$ $v$ $k$ $v$ $k$ $k$ $v$ $v$
Jos se on eristetty huippu, poista se. Eristetty kärki ei voi peittää mitään reunaa, joten se ei voi tässä tapauksessa olla osa mitään minimipeitettä. $v$ $v$
Jos graafissa on jäljellä enemmän kuin reunoja, eikä kahta edellistä sääntöä voida soveltaa, graafi ei voi sisältää koon kärjen peitettä . Kun kaikki pisteet, joiden aste on suurempi kuin , on poistettu , jokainen jäljellä oleva kärki voi peittää suurimman osan reunoista ja kärkijoukko voi peittää suurimman osan reunoista. Tässä tapauksessa tehtävän syöte voidaan korvata graafilla, jossa on kaksi kärkeä, yksi reuna ja arvo , eikä tähänkään ongelmaan ole ratkaisua. $k^{2}$ $k$ $k$ $k$ $k$ $k^{2}$ $k = 0$

Algoritmi, joka soveltaa näitä sääntöjä uudelleen, kunnes muita vähennyksiä ei voida tehdä, päättyy välttämättä ytimeen, jolla on korkeintaan reunoja ja (koska jokaisella reunalla on enintään kaksi päätepistettä eikä eristettyjä pisteitä) enintään pisteet. Tämä parametrinen vähennys voidaan tehdä lineaarisessa ajassa . Kun ydin on rakennettu, vertex cover -ongelma voidaan ratkaista brute force -algoritmilla , joka tarkistaa, että jokainen ytimen osajoukko on ytimen kansi. Siten kärkipeiteongelma voidaan ratkaista ajoissa graafille, jossa on kärkipisteitä ja reunoja, mikä mahdollistaa niiden tehokkaan ratkaisemisen pienenä, vaikka suurikin . $k^{2}$ ${\displaystyle 2k^{2))$ $O(2^{2k^{2))+n+m)$ $n$ $m$ $k$ $n$ $m$

Vaikka tämä raja on kiinteä-parametrisesti ratkaistavissa, sen riippuvuus parametrista on suurempi kuin voisi toivoa. Monimutkaisemmat parametrivähennysmenettelyt voivat parantaa tätä sidosta etsimällä pienempiä ytimiä enemmän aikaa parametrivähennysvaiheessa. Parametrisen pelkistyksen kärkipeitto-ongelmalle tunnetaan algoritmeja, jotka antavat maksimiytimiä, joissa on kärkipisteitä. Algoritmi, joka saavuttaa tämän parannetun rajan, käyttää huippupisteen peittotehtävän puolikokonaislukurelaksaatiota George Nemhauserin ja Trotterin [2] mukaisella lineaarisella ohjelmointitehtävällä . Toinen parametrinen pelkistysalgoritmi, joka saavuttaa tämän rajan, perustuu temppuun, jota kutsutaan kruunun pienennyssäännöksi ja käyttää polun vuorotteluargumentteja [3] . Tällä hetkellä tunnetuin parametrinen pelkistysalgoritmi pisteiden lukumäärän suhteen on Lampis [4] ja saavuttaa pisteet mille tahansa vakiolle . $2k$ $2k-c\log k$ $c$

Tälle ongelmalle on mahdotonta löytää kokoista ydintä, ellei P=NP, jolloin ydin johtaisi polynomialgoritmiin NP-kovan vertex cover -ongelmalle. Tässä tapauksessa ytimen koon tiukemmat rajat voidaan kuitenkin todistaa - ellei coNP NP/poly (jota laskennallisen monimutkaisuuden teoreetikot pitävät epätodennäköisenä), kenenkään on mahdotonta löytää ytimiä, joissa on reunat polynomiajassa [5] . $O(\log k)$ $\subseteq$ $\epsilon >0$ $O(k^{2-\epsilon })$

Määritelmä

Kirjallisuudessa ei ole selvää yksimielisyyttä siitä, kuinka parametrinen pelkistys tulisi muodollisesti määritellä, ja tällaisten ilmaisujen käytössä on hienovaraisia eroja.

Downey-Fellowsin merkintä

Downey-Fellowes-merkinnässä [6] parametroitu ongelma on osajoukko , joka kuvaa ratkaistavuusongelmaa . $L\subseteq \Sigma ^{*}\times \mathbb {N}$

Parametrisoidun ongelman parametrinen pelkistys on algoritmi, joka ottaa edustajan ja kartoittaa sen ajallisesti polynomiaalisesti edustajaan , niin että $L$ ${\näyttötyyli (x, k)}$ $|x|$ $k$ ${\näyttötyyli (x',k')}$

${\näyttötyyli (x, k)}$ tulee sisään jos ja vain jos tulee , $L$ ${\näyttötyyli (x',k')}$ $L$
kokoa rajoittaa laskettava funktio $x'$ $f$ $k$
$k'$ rajoitettu laskettavaan funktioon . $k$

Parametrisen pelkistyksen tulosta kutsutaan ytimeksi. Tässä yleisessä yhteydessä merkkijonon kokoa kutsutaan usein sen pituudeksi. Jotkut kirjoittajat pitävät graafitehtävien yhteydessä parempana kärkien määrää tai reunojen määrää kokona. ${\näyttötyyli (x',k')}$ $x'$

Flamin nimi on Grohe

Flam-Grohen notaatiossa [7] parametroitu ongelma koostuu päätösongelmasta ja funktiosta , itse parametrisoinnista. Tehtävää edustava parametri on numero . $L\subseteq \Sigma ^{*}$ $\kappa :\Sigma ^{*}\to \mathbb {N}$ $x$ $\kappa (x)$

Parametrisoidun ongelman parametrinen pelkistys on algoritmi, joka ottaa edustajan parametrin kanssa ja kartoittaa sen polynomiajassa edustajaksi siten, että $L$ $x$ $k$ $y$

$x$ tulee sisään jos ja vain jos tulee $L$ $y$ $L$
kokoa rajoittaa laskettava funktio . $y$ $f$ $k$

Huomaa, että tässä merkinnässä koon rajoitus tarkoittaa, että parametria rajoittaa myös funktio . $y$ $y$ $k$

Toimintoa kutsutaan usein ytimen kooksi. Jos joku sanoo, että se hyväksyy polynomin ytimen. Vastaavasti ongelmalle myönnetään lineaarinen ydin. $f$ $f=k^{O(1)}$ $L$ $f={O(k)}$

Parametrinen pelkistyvyys ja kiinteäparametrinen ratkaistavuus ovat samanarvoisia

Ongelma on kiinteä-parametrisesti ratkaistava, jos ja vain, jos se voidaan pienentää parametrisesti ja se on ratkaistavissa .

Se, että parametrisesti pelkistettävä ja ratkaistava ongelma on kiinteä-parametrisesti ratkaistava, voidaan nähdä yllä olevasta määritelmästä: parametrinen pelkistysalgoritmi, joka suoritetaan ajassa jonkin c:n ajan, kutsutaan koon ytimen saamiseksi . Ydin ratkaistaan sitten algoritmilla, joka tarkistaa, että ongelma on ratkaistavissa. Tämän menettelyn kokonaisajoaika on , missä on ytimien ratkaisemiseen käytetyn algoritmin ajoaika. Koska se on laskettavissa esimerkiksi olettaen, että se on laskettavissa, mutta se voidaan laskea luettelemalla kaikki mahdolliset pituuden syötteet , tästä seuraa, että ongelma on kiinteä-parametrisesti ratkaistava. $O(|x|^{c})$ $f(k)$ $g(f(k))+O(|x|^{c})$ $g(n)$ $g(f(k))$ $f(k)$ $g(f(k))$ $f(k)$

Todistaminen toiseen suuntaan, että kiinteä parametrisesti ratkaistava ongelma on parametrisesti pelkistettävissä ja ratkaistavissa, on hieman vaikeampi. Oletetaan, että kysymys on ei-triviaali, mikä tarkoittaa, että on olemassa vähintään yksi tehtäväedustaja nimeltä , joka kuuluu kieleen, ja vähintään yksi tehtäväedustaja, joka ei kuulu kieleen, nimeltä . Muussa tapauksessa minkä tahansa edustajan korvaaminen tyhjällä merkkijonolla on kelvollinen parametrinen vähennys. Oletetaan myös, että ongelma on kiinteäparametrisesti ratkaistava, eli sillä on algoritmi, joka toimii korkeintaan vaiheittain ongelman edustajilla jollekin vakiolle ja jollekin funktiolle . Tulon parametrisen pienentämisen toteuttamiseksi käytämme algoritmia annettuun tuloon enintään vaiheittain. Jos algoritmi päättyy vastaukseen, käytä vastausta valitaksesi joko tai ytimeksi. Jos sen sijaan saavutamme vaiheiden rajan keskeytyksettä, palautamme itse tehtävän ytimeksi. Koska se palautetaan syöteytimenä :lla , tästä seuraa, että tällä tavalla saadun ytimen koko ei ylitä . Kokoraja on laskettavissa kiinteän parametrisen ratkaistavuuden oletuksilla, mikä on laskettavissa. $I_{yes}$ $I_{no}$ ${\displaystyle f(k)\cdot |x|^{c))$ ${\näyttötyyli (x, k)}$ $c$ $f(k)$ $|x|^{c+1}$ $I_{yes}$ $I_{no}$ $|x|^{c+1}$ ${\näyttötyyli (x, k)}$ ${\näyttötyyli (x, k)}$ ${\displaystyle f(k)\cdot |x|^{c}>|x|^{c+1))$ ${\displaystyle \max\{|I_{yes}|,|I_{no}|,f(k)\))$ $f(k)$

Muita esimerkkejä

Vertex Cover: Vertex cover -ongelmassa on ytimiä, joissa on maksimipisteet ja reunat [8] . Lisäksi millekään , vertex cover -ongelmassa ei ole ytimiä, joissa on reunat, ellei {coNP} {NP/poly} [5] . Huippupeittoongelmassa -homogeenisissa hypergrafeissa on ytimiä, joissa on reunat, käyttäen auringonkukkalemmaa , eikä siinä ole kokoisia ytimiä, ellei coNP NP/poly [5] . $2k$ $O(k^{2})$ $\varepsilon >0$ $O(k^{2-\varepsilon })$ $\subseteq$ $d$ $O(k^{d})$ $O(k^{d-\varepsilon })$ $\subseteq$
Cycle-cutting vertex set: Cycle-cutting vertex set -ongelmassa on ytimiä, joissa on kärkipisteitä ja reunoja [9] . Lisäksi ongelmassa ei ole ytimiä, joissa on kärkipisteitä, ellei coNP NP/poly [5] . $4k^{2}$ $O(k^{2})$ $O(k^{2-\varepsilon })$ $\subseteq$
k-polku: k-polun ongelmana on päättää, onko tietyllä kaaviolla polun pituus vähintään . Tässä ongelmassa on eksponentiaalisesti koon riippuva ydin , eikä ytimiä, joiden koko riippuu polynomiaalisesti arvosta , ellei coNP NP/poly [10] . $k$ $k$ $k$ $\subseteq$
2D-ongelmat : Monissa parametrisoiduissa 2D -ongelmien versioissa on lineaariset ytimet tasograafisissa kaavioissa ja yleisemmin graafisissa kaavioissa, jotka eivät sisällä kiinteää kuvaajaa sivuaineena [11] .

Katso myös

Iteratiivinen pakkaus , toinen tekniikka kiinteäparametrisesti ratkaistavien algoritmien kehittämiseen

Muistiinpanot

↑ Tämä julkaisematon havainto esitettiin Bussin ja Goldsmithin artikkelissa ( Buss, Goldsmith 1993 )
↑ Flum, Grohe, 2006 .
↑ Flam ja Grohe ( Flum, Grohe 2006 ) antavat kruunun pienentämiseen perustuvan ytimen, jossa on kärkipisteitä. Huippupisteen raja on hieman monimutkaisempi. $3k$ $2k$
↑ Lampis, 2011 .
↑ 1 2 3 4 Dell, van Melkebeek, 2010 .
↑ Downey, Fellows, 1999 .
↑ Flum, Grohe, 2006 , s. neljä.
↑ Chen, Kanj, Jia, 2001 .
↑ Thomasse, 2010 .
↑ Bodlaender, Downey, Fellows, Hermelin, 2009 .
↑ Fomin, Lokshtanov, Saurabh, Thilikos, 2010 .

Kirjallisuus

Faisal N. Abu-Khzam, Rebecca L. Collins, Michael R. Fellows, Michael A. Langston, W. Henry Suters, Chris T. Symons. Ytimen muodostamisalgoritmit vertex-peiteongelmalle: teoria ja kokeet . – Tennesseen yliopisto, 2004.
Hans L. Bodlaender, Rod G. Downey, Michael R. Fellows, Danny Hermelin. Ongelmista ilman polynomiytimiä // Journal of Computer and System Sciences . - 2009. - T. 75 , no. 8 . - S. 423-434 . - doi : 10.1016/j.jcss.2009.04.001 .
Jonathan F. Buss, Judy Goldsmith. Epädeterminismi P // SIAM Journal on Computingissa . - 1993. - T. 22 , no. 3 . - S. 560-572 . - doi : 10.1137/0222038 .
Jianer Chen, Iyad A. Kanj, Weijia Jia. Vertex cover: lisähavaintoja ja lisäparannuksia // Journal of Algorithms. - 2001. - T. 41 , no. 2 . - S. 280-301 . - doi : 10.1006/jagm.2001.1186 .
Holger Dell, Dieter van Melkebeek. Tyytyväisyys ei salli ei-triviaalista harventumista, ellei polynomiaikahierarkia romahda //Proceedings of 42nd ACM Symposium on Theory of Computing (STOC 2010) . - 2010. - S. 251-260. - doi : 10.1145/1806689.1806725 .
RG Downey, MR Fellows. Parametrisoitu monimutkaisuus. - Springer, 1999. - ISBN 0-387-94883-X . - doi : 10.1007/978-1-4612-0515-9 .
Jörg Flum, Martin Grohe. Parametrisoitu kompleksiteoria . - Springer, 2006. - ISBN 978-3-540-29952-3 .
Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, Dimitrios M. Thilikos. Kaksiulotteisuus ja ytimet // Proceedings of the 21st ACM-SIAM Symposium on Discrete Algorithms (SODA 2010). - 2010. - S. 503-510.
Michael Lampis. Ydin luokkaa 2 k − c log k vertex coverille // Information Processing Letters . - 2011. - T. 111 , no. 23-24 . - S. 1089-1091 . - doi : 10.1016/j.ipl.2011.09.003 .
Stephan Thomasse. 4 k 2 -ydin palautepisteiden joukkoon // ACM Transactions on Algorithms. - 2010. - T. 6 , no. 2 .
Rolf Niedermeier. Kutsu kiinteiden parametrien algoritmeihin . - Oxford University Press, 2006. - ISBN 0-19-856607-7 . .