Eternal Domination

Téma bylo Eternal domination, popis řešení přes stromový rozklad, které je ale stále exponenciální ve velikosti vstupu.

Model, kde na grafu je k obránců a přichází naráz k útoků. Třídu grafů, pro kterou je v tomto modelu možné ubránit libovolnou posloupnost útoků, lze definovat pomocí zakázaných antigrafů. Pro k ochránců a graf G jsou doplňku G’ zakázené jako podgrafy $K_{1,k}, K_{2,k-1}, \dots, K_{\lfloor k/2 \rfloor,\lceil k/2 \rceil}$.