Paraméteres csökkentés

A paraméteres redukció olyan hatékony algoritmusok tervezésére szolgáló technika, amelyek hatékonyságukat egy előfeldolgozó lépéssel érik el, amelyben az algoritmus bemenetét egy kisebb, „kernelnek” nevezett bemenet helyettesíti. A kernel problémamegoldásának eredményének vagy meg kell egyeznie a kiindulási adatokkal, vagy a kernel megoldásának kimenetét könnyen át kell alakítani az eredeti probléma kívánt kimenetévé.

A paraméteres csökkentést gyakran olyan redukciós szabályok alkalmazásával érik el, amelyek levágják az adott probléma könnyen kezelhető részét. A paraméterezett komplexitáselméletben gyakran bizonyítható, hogy a kernel méretétől (egyes problémához kapcsolódó paraméterek függvényében) garantált határokkal rendelkező kernel megtalálható polinomiális időben . Ha lehetséges, az eredmény egy fix-parametrikusan eldönthető algoritmus lesz, amelynek futási ideje a (polinomiális idejű) parametrikus redukciós lépés és a kernel megoldásához szükséges (nem polinom, de paraméterkorlátozott) idő összege. Ezen túlmenően minden probléma, amely megoldható fix paraméterű megoldható algoritmussal, megoldható egy ilyen típusú parametrikus redukciós algoritmussal.

Példa: vertex coverage

A parametrikus redukciós algoritmus szabványos példája a csúcslefedési probléma paraméteres redukálása S. Bass által [1] . Ebben a feladatban a bemenet egy irányítatlan gráf egy számmal együtt . A kimenet egy maximális csúcskészlet, amely tartalmazza az egyes gráfok végcsúcsát, ha létezik ilyen halmaz, vagy egy sikertelen kivételt, ha ilyen halmaz nem létezik. Ez a probléma NP-nehéz . Azonban a következő szabályok használhatók a paraméteres csökkentésére: $G$ $k$ $k$

Ha a és a fok csúcsa nagyobb, mint , távolítsa el a gráfból, és csökkentse eggyel. Bármilyen méretű csúcs lefedettségi problémának tartalmaznia kell a -t , mert különben túl sok szomszédot választanának ki a beeső élek lefedésére. Így a redukált problémafedőből a fedőhöz való visszaadással kialakítható az eredeti gráf optimális csúcsborítója . $k>0$ $v$ $k$ $v$ $k$ $k$ $v$ $v$
Ha ez egy elszigetelt csúcs, törölje azt. Egy izolált csúcs nem takarhat le egyetlen élt sem, tehát ebben az esetben nem lehet része semmilyen minimális borításnak. $v$ $v$
Ha több mint él marad a gráfban, és az előző két szabály nem alkalmazható, akkor a gráf nem tartalmazhat méretű csúcsfedőt . A -nál nagyobb fokú összes csúcs eltávolítása után minden fennmaradó csúcs a legtöbb élt lefedheti, a csúcsok halmaza pedig a legtöbb élt. Ebben az esetben a feladat bemenetét egy két csúcsú, egy élű gráf helyettesítheti, amelynek értéke , és ennek a feladatnak sincs megoldása. $k^{2}$ $k$ $k$ $k$ $k$ $k^{2}$ $k=0$

Az az algoritmus, amely addig alkalmazza ezeket a szabályokat, amíg további redukciókat nem lehet végrehajtani, szükségszerűen egy olyan kernelnél végződik, amelynek legfeljebb éle van, és (mivel minden élnek legfeljebb két végpontja van, és nincsenek izolált csúcsai) a legtöbb csúcs. Ez a paraméteres redukció lineáris időben elvégezhető . A kernel felépítése után a csúcsfedő probléma megoldható egy brute force algoritmussal , amely ellenőrzi, hogy a kernel minden részhalmaza kernelborító-e. Így a csúcsok lefedésének problémája időben megoldható egy csúcsokkal és élekkel rendelkező gráf esetében, ami lehetővé teszi azok hatékony megoldását kicsiben, még akkor is, ha nagy . $k^{2}$ $2k^{2}$ $O(2^{2k^{2))+n+m)$ $n$ $m$ $k$ $n$ $m$

Bár ez a korlát fix-parametrikusan feloldható, a paramétertől való függése nagyobb, mint azt szeretnénk. A bonyolultabb paraméteres redukciós eljárások javíthatják ezt a korlátot, ha kisebb kerneleket találnak több idő árán a paraméteres redukciós lépésben. Ismeretesek a parametrikus redukció csúcslefedési problémájának algoritmusai, amelyek maximális magot adnak csúcsokkal. Az algoritmus, amely ezt a javított korlátot eléri, a csúcsfedő feladat félegészes relaxációját használja egy lineáris programozási feladattal George Nemhauser és Trotter [2] szerint . Egy másik paraméteres redukciós algoritmus, amely eléri ezt a határt, a koronaredukciós szabálynak nevezett trükkön alapul, és útvonalalternációs argumentumokat használ [3] . Jelenleg a csúcsok számát tekintve a legismertebb parametrikus redukciós algoritmus a Lampis [4] -nek köszönhető, és bármely konstansra képes csúcsokat elérni . $2k$ $2k-c\log k$ $c$

Ez a probléma nem találhat egy méretű kernelt, hacsak nem P=NP, ebben az esetben a kernel egy polinomiális algoritmushoz vezetne az NP-kemény csúcsfedő problémára. Ebben az esetben azonban a kernel méretének szigorúbb korlátai bizonyíthatóak - hacsak nem coNP NP/poly (amit a számítási komplexitás elméletei valószínűtlennek tartanak), lehetetlen, hogy bárki is találjon polinomiális időben élekkel rendelkező kernelt [5] . $O(\log k)$ $\subseteq$ $\epsilon >0$ $O(k^{2-\epsilon })$

Definíció

A szakirodalomban nincs egyértelmű konszenzus a paraméteres redukció formális meghatározását illetően, és finom különbségek vannak az ilyen kifejezések használatában.

Downey-Fellows jelölés

A Downey-Fellowes jelölésben [6] a parametrizált probléma a megoldhatósági problémát leíró részhalmaz . $L\subseteq \Sigma ^{*}\times \mathbb {N}$

A paraméterezett probléma paraméteres redukciója egy olyan algoritmus, amely reprezentatívot vesz és időben polinomiálisan leképezi egy reprezentatívra , így $L$ ${\megjelenítési stílus (x, k)}$ $|x|$ $k$ $(x',k')$

${\megjelenítési stílus (x, k)}$ akkor és csak akkor lép be , ha belép , $L$ $(x',k')$ $L$
a méretet egy kiszámítható függvény korlátozza $x'$ $f$ $k$
$k'$ egy kiszámítható függvényére korlátozva . $k$

A parametrikus redukció kimenetét kernelnek nevezzük. Ebben az általános összefüggésben egy karakterlánc méretét gyakran hosszának nevezik. Egyes szerzők a csúcsok számát vagy az élek számát részesítik előnyben méretként a gráffeladatok kontextusában. $(x',k')$ $x'$

A Flam neve Grohe

A Flam-Grohe jelölésben [7] egy parametrizált probléma egy döntési problémából és egy függvényből , magából a parametrizálásból áll. A feladat reprezentatív paramétere egy szám . $L\subseteq \Sigma ^{*}$ $\kappa :\Sigma ^{*}\to \mathbb {N}$ $x$ $\kappa (x)$

A paraméterezett probléma paraméteres redukciója egy olyan algoritmus, amely egy reprezentatívot vesz egy paraméterrel , és polinomiális időben leképezi egy reprezentatívra úgy, hogy $L$ $x$ $k$ $y$

$x$ akkor és csak akkor lép be , ha belép $L$ $y$ $L$
a méretet egy kiszámítható függvény korlátozza . $y$ $f$ $k$

Vegye figyelembe, hogy ebben a jelölésben a méretkorlátozás azt jelenti, hogy a paramétert egy függvény is korlátozza . $y$ $y$ $k$

A függvényt gyakran a kernel méretének nevezik. Ha valaki azt mondja, hogy polinomiális kernelt enged be. Hasonlóképpen, a probléma elfogadja a lineáris kernelt. $f$ $f=k^{O(1)}$ $L$ $f={O(k)}$

A paraméteres redukálhatóság és a fix paraméterű megoldhatóság egyenértékű

Egy probléma akkor és csak akkor fix-parametrikusan megoldható, ha paraméteresen redukálható és megoldható .

Hogy egy parametrikusan redukálható és megoldható probléma fix-parametrikusan megoldható, azt a fenti definícióból láthatjuk: egy paraméteres redukciós algoritmust hívunk meg, amely bizonyos c-ig időben fut, hogy megkapjuk a méretű magot . A kernelt ezután egy algoritmus oldja meg, amely ellenőrzi, hogy a probléma megoldható-e. Ennek az eljárásnak a teljes futási ideje , ahol a kernelek megoldásához használt algoritmus futási ideje. Mivel például kiszámítható, feltételezve, hogy kiszámítható, de kiszámítható az összes lehetséges hosszúságú bemenet felsorolásával , ebből következik, hogy a probléma fix-parametrikusan megoldható. $O(|x|^{c})$ $f(k)$ $g(f(k))+O(|x|^{c})$ $g(n)$ $g(f(k))$ $f(k)$ $g(f(k))$ $f(k)$

A másik irányba annak bizonyítása, hogy egy rögzített paraméteresen megoldható probléma parametrikusan redukálható és megoldható, kicsit nehezebb. Tegyük fel, hogy a kérdés nem triviális, ami azt jelenti, hogy van legalább egy , a nyelvhez tartozó nevû feladatképviselõ, és legalább egy, a nyelvhez nem tartozó feladatképviselõ, név szerint . Ellenkező esetben, ha bármely képviselőt üres karakterláncra cserélünk, az érvényes paraméteres csökkentés. Tételezzük fel azt is, hogy a probléma fix-paraméteresen megoldható, vagyis van olyan algoritmusa, amely legfeljebb lépésenként működik a probléma reprezentánsain valamilyen állandó és valamilyen függvény esetén . A bemenet parametrikus redukciójának megvalósításához az algoritmust egy adott bemeneten maximum lépésekben alkalmazzuk. Ha az algoritmus egy válasszal végződik, használja a választ a kernel vagy a válasz kiválasztásához. Ha ehelyett megszakítás nélkül elérjük a lépések számának határát, magát a feladatot adjuk vissza kernelként. Mivel bemeneti kernelként kerül visszaadásra -val , ebből következik, hogy az így kapott kernel mérete nem haladja meg a -t . A méretkorlát a fix paraméteres megoldhatóság feltételezése mellett számítható, ami kiszámítható. $I_{yes}$ $I_{no}$ ${\displaystyle f(k)\cdot |x|^{c))$ ${\megjelenítési stílus (x, k)}$ $c$ $f(k)$ $|x|^{c+1}$ $I_{yes}$ $I_{no}$ $|x|^{c+1}$ ${\megjelenítési stílus (x, k)}$ ${\megjelenítési stílus (x, k)}$ ${\displaystyle f(k)\cdot |x|^{c}>|x|^{c+1))$ ${\displaystyle \max\{|I_{yes}|,|I_{no}|,f(k)\))$ $f(k)$

Egyéb példák

Csúcsborító: A csúcsfedő probléma maximális csúcsokkal és élekkel rendelkező magokat tartalmaz [8] . Ezen túlmenően, bármely , csúcsfedő problémának nincsenek élekkel rendelkező magjai, kivéve, ha a {coNP} {NP/poly} [5] . A -homogén hipergráfokban a csúcsfedő-probléma élekkel rendelkező magokat tartalmaz , a napraforgó lemma használatával , és nincs akkora magja, hacsak nem coNP NP/poly [5] . $2k$ $O(k^{2})$ $\varepsilon >0$ $O(k^{2-\varepsilon })$ $\subseteq$ $d$ $O(k^{d})$ $O(k^{d-\varepsilon })$ $\subseteq$
Ciklusvágó csúcskészlet: A ciklusvágó csúcshalmaz probléma csúcsokkal és élekkel rendelkező magokat tartalmaz [9] . Sőt, a problémának nincsenek csúcsaival rendelkező kernelek , hacsak nem coNP NP/poly [5] . $4k^{2}$ $O(k^{2})$ $O(k^{2-\varepsilon })$ $\subseteq$
k-Path: A k-útvonal probléma annak eldöntése, hogy egy adott gráfnak van-e legalább hosszuságú útja . Ennek a problémának van egy méretű kernelje, amely exponenciálisan függ -től , és nincs olyan méretű kernel, amely polinomiálisan függ -től, kivéve, ha a coNP NP/poly [10] . $k$ $k$ $k$ $\subseteq$
2D-s problémák : A 2D -s problémák sok parametrizált változata lineáris magot tartalmaz sík gráfokon, és általánosabban olyan gráfokon, amelyek nem tartalmaznak valamilyen rögzített gráfot mellékként [11] .

Lásd még

Iteratív tömörítés , egy másik technika a rögzített paraméterekkel feloldható algoritmusok fejlesztésére

Jegyzetek

↑ Ezt a kiadatlan megfigyelést Buss és Goldsmith egy cikkében fogalmazta meg ( Buss, Goldsmith 1993 )
↑ Flum, Grohe, 2006 .
↑ Flam és Grohe ( Flum, Grohe 2006 ) egy koronaredukción alapuló kernelt adnak, amelynek csúcsai vannak. A csúcshatár egy kicsit bonyolultabb. $3k$ $2k$
↑ Lampis, 2011 .
↑ 1 2 3 4 Dell, van Melkebeek, 2010 .
↑ Downey, Fellows, 1999 .
↑ Flum, Grohe, 2006 , p. négy.
↑ Chen, Kanj, Jia, 2001 .
↑ Thomasse, 2010 .
↑ Bodlaender, Downey, Fellows, Hermelin, 2009 .
↑ Fomin, Lokshtanov, Saurabh, Thilikos, 2010 .

Irodalom

Faisal N. Abu-Khzam, Rebecca L. Collins, Michael R. Fellows, Michael A. Langston, W. Henry Suters, Chris T. Symons. Kernelizációs algoritmusok a csúcsfedő problémához: elmélet és kísérletek . – Tennessee Egyetem, 2004.
Hans L. Bodlaender, Rod G. Downey, Michael R. Fellows, Danny Hermelin. A polinomiális kernelek nélküli problémákról // Journal of Computer and System Sciences . - 2009. - T. 75 , sz. 8 . - S. 423-434 . - doi : 10.1016/j.jcss.2009.04.001 .
Jonathan F. Buss, Judy Goldsmith. Nondeterminizmus a P-n belül // SIAM Journal on Computing . - 1993. - T. 22 , sz. 3 . - S. 560-572 . - doi : 10.1137/0222038 .
Jianer Chen, Iyad A. Kanj, Weijia Jia. Vertex cover: További megfigyelések és további fejlesztések // Journal of Algorithms. - 2001. - T. 41 , sz. 2 . - S. 280-301 . - doi : 10.1006/jagm.2001.1186 .
Holger Dell, Dieter van Melkebeek. A kielégíthetőség nem tesz lehetővé nem triviális ritkítást, kivéve, ha a polinom-idő hierarchia összeomlik //Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC 2010) . - 2010. - S. 251-260. - doi : 10.1145/1806689.1806725 .
RG Downey, MR Fellows. Paraméterezett komplexitás. - Springer, 1999. - ISBN 0-387-94883-X . - doi : 10.1007/978-1-4612-0515-9 .
Jörg Flum, Martin Grohe. Paraméterezett komplexitáselmélet . - Springer, 2006. - ISBN 978-3-540-29952-3 .
Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, Dimitrios M. Thilikos. Bidimensionalitás és kernelek // Proceedings of the 21st ACM-SIAM Symposium on Discrete Algorithms (SODA 2010). - 2010. - S. 503-510.
Michael Lampis. 2 k − c log k rendű kernel a csúcsfedőhöz // Information Processing Letters . - 2011. - T. 111 , sz. 23-24 . - S. 1089-1091 . - doi : 10.1016/j.ipl.2011.09.003 .
Stephan Thomasse. Egy 4 k 2 -es kernel visszacsatolási csúcskészlethez // ACM-tranzakciók az algoritmusokon. - 2010. - T. 6 , sz. 2 .
Rolf Niedermeier. Meghívás fix paraméterű algoritmusokhoz . - Oxford University Press, 2006. - ISBN 0-19-856607-7 . .