Abstrakt
Studujeme problém vyváženého souvislého rozdělení: rozdělit vrcholy grafu do předepsaného počtu tříd tak, že každá třída indukuje souvislý podgraf a velikosti tříd se liší nejvýše o jedna. Zkoumáme problém z pohledu parametrizované složitosti vzhledem k ruzným parametrizacím a jejich kombinacím, které zahrnují druhotné míry jako: (1) počet tříd rozdělení, (2) stromová šířka, (3) cestová šířka, (4) minimální velikost množiny vrcholů protínající všechny cykly, (5) minimální velikost vrcholové pokrytí a (6) maximální počet listů v kostře grafu. Jmenovitě ukazujeme, že problém je W[1]-těžký vzhledem ke kombinaci prvních čtyř a parametrizovaně dostupný vzhledem ke každému z posledních dvou. Těžkost platí i pro rovinné grafy. Dále ukážeme, že blízce související problém Vyváženého barvení (vyváženě rozdělit vrcholy do předepsaného počtu nezávislých množin) je parametrizovaně dostupný vzhledem k maximálnímu počtu listů v kostře grafu.