ARTP - 13 - Problémy riešiteľné so zafixovateľným parametrom

Zhrnutie prednášky

Prednáška predstavuje problémy riešiteľné so zafixovateľným parametrom (FPT) na príklade vrcholového pokrytia, ktoré je NP-ťažké. Triviálne prehľadávanie všetkých podmnožín trvá O(2^n · m) a hladový 2-aproximačný algoritmus je rýchly, ale nepresný. Ak je veľkosť pokrytia k malá, stačí skúšať všetky k-tice vrcholov v čase približne O(n^k · m). Lepší algoritmus vyberá hranu (u, v), vetví výpočet podľa toho, ktorý z jej koncov patrí do pokrytia, a prehľadáva strom do hĺbky k, čo dáva časovú zložitosť O(2^k · n). Problém je FPT, ak ho možno riešiť v čase f(k)·n^c alebo f(k)+n^c, kde f závisí len od parametra k. Parametrom môže byť veľkosť riešenia, maximálny stupeň vrchola, stromová šírka či dimenzia.

• - Vrcholové pokrytie je NP-ťažké; triviálne riešenie skúša všetky podmnožiny v čase O(2^n · m).
• - Pre malé k stačí vyskúšať všetky k-tice vrcholov, čo trvá približne O(n^k · m) a pri väčšom k je pomalé.
• - Vetvenie podľa hrany (u, v): aspoň jeden z koncov musí byť v pokrytí, preto strom rozdvojujeme a hĺbku obmedzíme na k.
• - Algoritmus má zložitosť O(2^k · n); k netreba poznať vopred, ak strom prehľadávame do šírky.
• - FPT: algoritmus v čase f(k)·n^c alebo f(k)+n^c, kde f je ľubovoľná funkcia nezávislá od n (nie však n^k).
• - Parametrom môže byť veľkosť riešenia, maximálny stupeň vrchola, stromová šírka (treewidth) alebo dimenzia priestoru.
• - Typ f(k)+n^c je lepší a existencia prvého typu implikuje druhý, no dôkaz je nekonštruktívny, preto sa uvádzajú oba.

Zhrnutie pripravené s pomocou AI z prepisu videa.