Paremetrizovaná složitost barvících problémů: stromová šíře vs vrcholové pokrytí (rozšířený abstrakt)

Abstrakt

Ukazujeme, že parametrerizovaná složitost příbuzných problémů se podstatně mění při různých způsobech parameterizace.

Klíčová slova

• Parameterized
• Complexity
• Coloring
• Problems
• Treewidth
• versus
• Vertex
• Cover
• Extended
• abstract