Eternal Domination

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.

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.

Seznam open problému:

  • 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.

Hypotézy:

  • mám-li v grafu artikulaci, pak se přes ni nebude moc často přecházet.
    • tzn. z bloku odejde maximálně konstantní počet ochránců.