Iteratív tömörítés

Az iteratív tömörítés egy algoritmikus technika rögzített paraméterűen feloldható algoritmusok fejlesztésére . Ennél a technikánál minden lépésnél egy elemet (például gráfcsúcsot ) adunk a feladathoz , és mielőtt hozzáadnánk, egy kis megoldást találunk a problémára.

Történelem

A technikát Reed, Smith és Wetta [1] fejlesztette ki, hogy bemutassa, hogy a páratlan ciklusok eltávolításának problémája időben megoldható az n csúcsú, m élű és k számú csúcsú gráfok esetében . A páratlan ciklus eltávolításának problémája az a probléma, hogy megtaláljuk a legkisebb csúcskészletet, amely legalább egy csúcsot tartalmaz bármely páratlan ciklusból. A probléma parametrikus összetettsége sokáig nyitott maradt [2] [3] . Később ez a technika nagyon hasznossá vált a fix paraméterű megoldhatósági eredmények bizonyítására . Manapság ezt a technikát tekintik az egyik alapvetőnek a paraméterezett algoritmusok területén. $O(3^{k}kmn)$

Az iteratív tömörítést számos problémában sikeresen alkalmazták, mint például a páratlan ciklusok eltávolítása (lásd alább) és az élek eltávolítása a bipartit létrehozásához , a ciklusvágó csúcsok keresése , a klasztercsúcsok eltávolítása és az orientált ciklusú vágási csúcsok megtalálása [4] . A módszert sikeresen alkalmazták egzakt exponenciális idő algoritmusokhoz is független halmaz megtalálására [5] .

Technika

Az iteratív tömörítés alkalmazható például olyan gráfokon lévő parametrizált problémákra , amelyek bemenete egy G =( V , E ) gráf és egy k természetes szám , és a feladat egy megoldás (egy halmaz) meglétének ellenőrzéseként jelenik meg. csúcsok) mérete . Tegyük fel, hogy a probléma le van zárva a generált részgráfok alatt (ha létezik megoldás egy adott gráfra, akkor minden generált részgráfra létezik ekkora vagy kisebb megoldás), és van egy hatékony eljárás, amely meghatározza, hogy Y méretű megoldás megoldható- e . kisebb k méretű oldatra zsugorodott . $\leqslant k$ $\leqslant k$ $k+1$

Ha ez a feltevés teljesül, akkor a probléma megoldható úgy, hogy egyesével adjuk hozzá a csúcsokat, és keressük a megoldást a generált részgráfra az alábbiak szerint:

Kezdjük egy részgráftal, amelyet k méretű S csúcsok halmaza generál, és egy X megoldás , amely megegyezik S -vel .
Egyelőre a következő lépéseket tesszük: $S\neq V$
- Legyen v tetszőleges csúcs , add hozzá v -t S -hez $V\backslash S$
- Ellenőrizzük, hogy a ( k + 1) Y = X ∪ {x } csúcsú megoldás S esetén tömöríthető-e k csúcsú megoldássá.
- Ha a megoldás nem tömöríthető, akkor leállítjuk az algoritmust - a bemeneti gráfnak nincs k csúcsú megoldása.
- Ellenkező esetben feltételezzük, hogy X egy új tömörített megoldás, és visszatérünk a ciklus elejére.

Ez az algoritmus lineáris számú alkalommal hívja meg a tömörítési rutint. Ezért, ha a tömörítési eljárás egy változata fix-paraméteresen feloldható idő alatt fut le, azaz valamilyen c állandóra , akkor a teljes probléma megoldására szolgáló iteratív tömörítési eljárás időben lefut . Ugyanez a technika használható élhalmazok keresésére olyan gráfok tulajdonságaihoz, amelyek részgráfok (nem generált részgráfok) vagy más gráfelméleti tulajdonságok alatt zártak. Ha a k paraméter értéke ismeretlen, akkor külső szintű exponenciális kereséssel vagy lineáris kereséssel kereshetjük meg a k optimális választását, minden lépésben kereséssel, ugyanazon iteratív tömörítési algoritmus alapján. ${\displaystyle f(k)\cdot n^{c))$ $f(k)\cdot n^{c+1}$

Alkalmazások

Az eredeti cikkben Reed, Smith és Wetta megmutatta, hogyan lehet egy gráfot kétoldalúvá tenni úgy, hogy időben eltávolítanak legfeljebb k csúcsot . Később Lokshtanov, Saurabh és Sikdar egy egyszerűbb algoritmust adott, szintén iteratív tömörítést alkalmazva [6] . Az eltávolított k + 1 méretű Y halmaz k méretű X halmazba tömörítéséhez az algoritmusuk az Y halmaz összes partícióját három részhalmazra ellenőrzi - az Y halmaz egy részhalmazára, amely az új eltávolított halmazhoz tartozik, és két részhalmazra az X halmaz eltávolítása után megmaradó kétrészes gráf két részéhez tartozó Y halmaz . Ha ezt a három halmazt kiválasztottuk, az eltávolítandó X halmaz fennmaradó csúcsai (ha van ilyen) megtalálhatók belőlük a Ford-Fulkerson algoritmus segítségével . $O(3^{k}kmn)$ $3^{k+1}$

A csúcslefedettség egy másik példa, amelyre az iteratív tömörítés alkalmazható. A csúcsfedő feladathoz egy gráfot és egy k természetes számot adunk bemenetként , és az algoritmusnak el kell döntenie, hogy létezik-e olyan X halmaz , amelynek k csúcsa van úgy, hogy bármely él beesik az X -beli csúcsra . A tömörítési változatban a bemenet egy Y halmaz , amelynek csúcsai a gráf összes élére esnek, és az algoritmusnak meg kell találnia egy k méretű X halmazt , amelynek ugyanaz a tulajdonsága, ha létezik ilyen. Ennek egyik módja az összes opció tesztelése, amellyel az Y halmazt eltávolítjuk a lefedettségből, és visszahelyezzük a grafikonba. Egy ilyen iteráció csak akkor működhet, ha nincs szomszédos két eltávolítandó csúcs, és minden ilyen változatnál az alprogramnak tartalmaznia kell a lefedésben az Y -on kívüli összes olyan csúcsot , amely az eltávolítás következtében felfedetlenné váló élre esik. Egy ilyen szubrutin használata egy iteratív tömörítési algoritmusban egyszerű algoritmust eredményez idővel a csúcslefedettséghez. $G=(V,E)$ $k+1$ $2^{k+1}$ $O(2^{k}n^{2})$

Lásd még

Paraméteres redukció , egy másik technika rögzített paraméterű, eldönthető algoritmusokhoz

Jegyzetek

↑ Reed, Smith, Vetta, 2004 , p. 299–301.
↑ Niedermeier, 2006 , p. 184.
↑ Cygan, Fomin, Kowalik és mtsai, 2015 , p. 555.
↑ Guo, Moser, Niedermeier, 2009 , p. 65–80.
↑ Fomin, Gaspers, Kratsch et al., 2010 , p. 1045–1053.
↑ Lokshtanov, Szaurabh, Sikdar, 2009 , p. 380–384.

Irodalom

Bruce Reed, Kaleigh Smith, Adrian Vetta. Páratlan ciklusú transzverzálisok keresése // Operations Research Letters. - 2004. - T. 32 , sz. 4 . - doi : 10.1016/j.orl.2003.10.009 .
Rolf Niedermeier. Meghívás fix paraméterű algoritmusokhoz. - Oxford University Press, 2006. - V. 31. - (Oxford előadássorozat a matematikából és alkalmazásaiból). — ISBN 9780198566076 .
Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Daniel Marx, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh. Paraméterezett algoritmusok. - Springer, 2015. - ISBN 978-3-319-21274-6 .
Jiong Guo, Hannes Moser, Rolf Niedermeier. Iteratív tömörítés az NP-kemény minimalizálási problémák pontos megoldásához // Nagy és összetett hálózatok algoritmusai. - Springer, 2009. - T. 5515. - S. 65–80. — (Számítástechnikai előadásjegyzetek). - ISBN 978-3-642-02093-3 . - doi : 10.1007/978-3-642-02094-0_4 .
Fedor Fomin, Serge Gaspers, Dieter Kratsch, Mathieu Liedloff, Saket Saurabh. Iteratív tömörítés és egzakt algoritmusok // Elméleti számítástechnika. - 2010. - T. 411 , sz. 7 . – S. 1045–1053 . - doi : 10.1016/j.tcs.2009.11.012 .
Daniel Lokshtanov, Saket Saurabh, Somnath Sikdar. Egyszerűbb paraméterezett algoritmus az OCT számára // 20th International Workshop on Combinatorial Algorithms, IWOCA 2009, Hradec nad Moravicí, Cseh Köztársaság, 2009. június 28–július 2., Revised Selected Papers. - Springer, 2009. - T. 5874. - S. 380-384. — (Számítástechnikai előadásjegyzetek). - ISBN 978-3-642-10216-5 . - doi : 10.1007/978-3-642-10217-2_37 .