Santa Claus — modified 2022-12-14 15:36 (22 days ago) — edit — reply
# Převod na SAT
Pro každý vrchol $v_i \in V$ vytvoříme výrokovou proměnnou $x_i$. Dále vytvoříme klauzule pro splnění základní podmínky pokrytí strážníky:
Pro každý vrchol $v_i$ a jeho sousedy $v_{i_1}, ..., v_{i_j}$ přidáme do formule klauzuli
$v_i \vee v_{i_1} \vee ... \vee v_{i_j}$ (A)
Tím máme zaručeno zabezpečení města G, nyní musíme vzít v potaz rozpočtovou stránku, protože takto by nám zatím prošlo i postavení strážníka na každou křižovatku, čímž bychom do rozpočtu vykousli díru.
Pro omezení počtu na nejvýše $k$ strážníků použijeme podobný trik jako na Medvědově přednášce s převodem nezávislé množiny na SAT.
Protože ale na rozdíl od přednášky potřebujeme počet vrcholů omezit shora, použijeme trik a sice omezíme zdola počet strážníkem neobsazených vrcholů.
Stanovme $n$ počet vrcholů $G$ a $t = n - k$
Vytvoříme tabulku $t \times n$ výrokových proměnných $p_{i,j}$, kde $p_{i,j}$ bude indikovat, že vrchol $v_j$ je v množině neobsazených vrcholů $i-tý$.
Nyní budeme muset několika sadami klauzulí zajistit požadované chování:
* (B) V každém řádku tabulky má být právě jedna splněná proměnná. To rozložíme na alespoň jedna a nejvýše jedna:
* Alespoň jedna $\forall i; i \in 1...t: p_{i,1} \vee p_{i,2} \vee ... \vee p_{i,n}$
* Nejvýše jedna: $\forall i,j,j^\prime; i \in 1...t , j, j^\prime \in 1...n, j \neq j^\prime : p_{i,j} \implies \neg p_{i,j^\prime}$.
Toto je sice implikace, ale jednoduše převedeme na klauzuli:
$\neg p_{i,j} \vee \neg p_{i,j^\prime}$
* (C\) V každém sloupci je nejvýše jedna splněná proměnná:
* Obdobně jako výše, v bodě Nejvýše jedna.
* (D) Pokud je ve sloupci splněná proměnná, v odpovídajícím vrcholu není strážník:
$\forall p_{i,j}: p_{i,j} \implies \neg x_j$. Implikaci opět převedeme na klauzuli: $\forall p_{i,j}: \neg p_{i,j} \vee \neg x_j$.
Pokud jsou tyto klauzule splněny, máme alespoň $t = n - k$ neobsazených vrcholů, tedy nejvýše $k$ obsazených vrcholů.
## Rozvaha o správnosti
Když je město $k$-ohlídatelné, pak lze pro libovolné $k$-ohlídání najít $n-k$ vrcholů bez strážníků, ty označíme $v_1,...,v_t$, v tabulce vybereme diagonálu a tyto proměnné nastavíme na 1, tím splníme sady klauzulí B,C,D. Klauzule A jsou splněné z premisy, že město je ohlídané.
Naopak když je zkonstrovaná formule splnitelná, pak pro libovolné ohodnocení máme alespoň $n-k$ nulových proměnných, ty z tabulky jako vrcholy bez strážníka, na zbytek vrcholů dáme strážníky a máme validní ohlídání.
## Polynomiálnost převodu
Vytvoříme formuli polynomiální velikosti:
A ... $O(n^2)$
tabulka ... $O(nk)$ proměnných
B-D ... $O(n \cdot n^2)$
Nerozepisuji, protože je to podle mě triviálně patrné.
## Možnost s právě $k$ strážníky
Zatím jsme pracovali s možností $k$-ohlídatelnosti jako existence ohlídání s nejvýše $k$ strážníky. Pokud je město méně než $k$-ohlídatelné, pak je jistě i $k$-ohlídatelné, tedy pokud má alespoň $k$ křižovatek. Můžeme tedy přidat kontrolu na $k \leq n$.
Dále pokud bychom chtěli zjistit, jestli dané $k$ je nejmenší, pro které je město $k$-ohlídatelné, stačí spojit danou formuli s negací formule pro $k-1$, správnost i polynomialita zůstává, pouze je potřeba převést negaci CNF na CNF, což není složité.
# Převod ze SAT
Vytvoříme graf s vrcholy $v_1...v_n$ a $u_1...u_n$ a $t_1...t_n$, mezi vrcholy se stejnými indexy přidáme hranu. Všimněme si, že tento graf je $n$-ohlídatelný, navíc v každém takovém ohlídání bude platit, že alespoň jeden z vrcholů $u_i, v_i, t_i$ má strážníka. Také bude platit, že právě jeden z těchto vrcholů má strážníka, protože kdyby byli na těchto třech vrcholech strážníci dva, musel by existovat index, pro který by nezbyl strážník žádný.
Toto uspořádání nám dává základ pro SAT - indexům přiřadíme výrokové proměnné - $n$ tedy bude počet prvovýroků. V ohlídání bude vyběr mezi $u_i, v_i a t_i$ rozhodovat ohodnocení výrokové proměnné příslušící indexu $i$ - stanovme $u_i$ jako $0$ a $v_i$ jako $1$, pokud bude strážník na spojovacím vrcholu $t_i$, znamená to, že v ohodnocení můžeme zvolit libovolnou hodnotu, tedy že výrok je nezávislý. Pokud bychom chtěli generovat jednoznačná ohodnocení, můžeme přidat spojnice $t^\prime_i$ obdobné vrcholům $t_i$.
Pro klauzuli nad $n$ proměnnými tedy vytvoříme naši konstrukci s $3n$ vrcholy, pro každou klauzuli přidáme vrchol a přidáme hrany mezi klauzulí a obsaženými literály (máme vrchol pro každou proměnnou i její negaci).
Pak zkusíme najít $n$-ohlídání.
### Správnost
Pokud existuje $n$-ohlídání, pak existuje splňující ohodnocení - každá klauzule je splněná, protože alespoň jeden příslušný literál má strážníka tedy je nastaven na 1. Zároveň platí, že nenastavujeme proměnnou i její negaci zároveň - pak by totiž graf nemohl být $n$-ohlídatelný.
Dále pokud existuje ohodnocení - existuje i $n$-ohlídání - každá proměnná má nějakou hodnotu, postavíme na příslušný vrchol strážníka. Tím máme zajíštěny vrcholy $u, v, t$. Všechny vrcholy klauzulí jsou ale také pod dohledem, protože každá klauzule má alespoň jeden literál se strážníkem.
### Polynomiálnost
Převod je polynomiální, protože použijeme $3n$ vrcholů a hran plus počet klauzulí a součet jejich velkostí.