Publikace na Matematicko-fyzikální fakulta |
2007
Abstrakt
Seidelovo přepnutí množiny vrcholů je operace, která smaže hrany vycházejicí z této množiny z grafu a přidá do něj ty hrany mezi množinou a zbytkem grafu, které tam původně nebyly. Ostatní hrany tato operace nemění.
Obvyklá otázka v parametrizované složitosti je, zda exponenciální část algoritmů pro těžké problémy může být omezena nějakou funkcí pouze zvoleného parametru, jenž očekáváme, že bude malý. Studujeme složitost otázky, zda zadaný graf může být změněn pomocí Seidelova přepnutí na graf s nějakou vlastností P z parametrizovaného hlediska.
Ukazujeme parametrizovanou dostupnost přepnutí na regulární graf, graf s omezeným stupněm vrcholů, omezeným počtem hran a graf bez zakázaného podgrafu.