Publikace na Matematicko-fyzikální fakulta |
2008
Abstrakt
Seidelovo přepnutí množiny vrcholů je operace, která z grafu vymaže hrany vycházející z této množiny a přidá takové hrany mezi touto množinou a zbytkem grafu, které v něm původně nebyly. Ostatní hrany nejsou operací dotčeny.
Obvyklou otázkou v parametrizované složitosti je, zda exponenciální část algoritmů pro těžké problémy lze omezit nějakou funkcí výhradně zvoleného parametru, o němž předpokládáme, že je malý. Studujeme z parametrizovaného pohledu složitost otázky, zda daný graf může být pomocí Seidelova přepnutí změněn na graf s vlastností P.
Ukážeme parametrizovanou dostupnost přepnutí na regulární graf, na graf s omezenými stupni vrcholů, omezeným počtem hran, graf prostý zakázaného podgrafu a bipartitní graf.