Eternal Domination

Materiály

Teorie

  • Mějme graf $G$ a funkci $g:V(G) \rightarrow \mathbb{N}$, takovou, že množina vrcholů $\{v:v\in V(G) \wedge g(v)\geq 1\}$ tvoří dominující množinu. Potom definujme konfiguraci $C_G = (G,g)$.
  • Nechť $S_G$ je strategie definovaná jako $S_G=(\mathbb{C},R)$ kde $\mathbb{C}=\{C_1,C_2,\dots\}$ je množina konfigurací stejné kardinality, a $R:\mathbb{C}\times\mathbb{C}$ je relace přechodu mezi konfiguracemi taková, že $R(C_1,C_2)=1 \Leftrightarrow $
  • Nechť $U_G$ je universum všech strategií $S_G$.

Uvažme nějakou počáteční konfiguraci guardů v grafu G. Po každém tahu sestrojme bipartitní graf $B_i$, kde v jedné partitě jsou současné pozice ochránců a v druhé partitě jsou vrcholy, na nichž stáli guardi v počáteční konfiguraci (dále už jen pozice). Hranu mezi guardem g a pozicí p natáhneme, pokud vzdálenost mezi g a p je menší nebo rovna 1. Lze útoky vynutit, aby v nějakém grafu $B_1,\dots,n$ nebylo párování? Pokud ne, tak jsme (prý) dokázali, že eternal domination leží v PSPACE.

Známé výsledky

  • Je známá strategie pro stromy.

Rozdělané

  • DP řešení na stromech a jak (a jestli) je rozšířit na stromový rozklad (PAMový). Problém je, že závislost mezi přechody DP nemusí záviset pouze na sousedech v rozkladu. Rozklad grafu na úplňáky a hvězdy není úplně cesta, protože braní hvězd na kružnici přidá jenom 1 guarda, zatímco skutečné hvězdy se brání 2 guardy.
  • 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}$.

Hypotézy

  • Nechť $A_1,\dots,A_K$ jsou bloky G. Pak $\exists S^\star_G$ taková, že $\forall i \in \{1,\dots,k\}: P^+_G(S^\star_G,A_I) - P^-_G(S^\star_G,A_I) \leq 1$ (mám-li v grafu artikulaci, pak se přes ni nebude moc často přecházet)
    • tzn. z bloku odejde maximálně 1 ochránce.

Open

  • existuje FPT algoritmus, kde parametrem je šířka stromového rozkladu?
  • FPT algoritmus pro bránění hran, kde parametrem je velikost řešení $(O(2^k) k)$.
    • existuje polynomiální kernel?
  • lze řešit eternal domination v polynomiálním prostoru?
    • nápad 1: ukázat, že pro každý graf existuje polynomiálně velký graf strategií.
    • nápad 2: ukázat, že pokud umím ubránit polynomiálně mnoho útoků, pak je umím ubránit všechny.
    • opak: ukázat EXPTIME úplnost.

Pár nesouvisejících problémů a Eternal domination

2018-11-11
Tung ukázal pár drobných problémů, nad kterými jsme strávili chvilku, před tím než přišel Radovan a Ondra, kdy jsme se začli bavit o ED. Koukli jsme na neklikovou strategii na mřížce 5x5. Používá 10 stavů, které jsou ‘skoro’ symetrické. Šlo by nehledat nejmenší strategii, ale nějakou symetrickou.

Eternal Domination

2018-08-08
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}$.

Eternal Domination

2018-08-08
Dnes mluvil Matyáš na téma Eternal Domination. Zmínila se jeho bakalářka a její výsledky. Ukázala se strategie pro stromy. Diskutovalo se o DP řešení na stromech a jak (a jestli) je rozšířit na stromový rozklad (PAMový). Problém je, že závislost mezi přechody DP nemusí záviset pouze na sousedech v rozkladu. Rozklad grafu na úplňáky a hvězdy není úplně cesta, protože braní hvězd na kružnici přidá jenom 1 guarda, zatímco skutečné hvězdy se brání 2 guardy.