3.přednáška

Bounded search trees

Pro VC máme první metodu jako že vezememe vrchol grafu $G$ a vyrobíme si strom, kde synové $(G,k)$ jsou $(G-v,k-1),(G-N(v),k-|N(v)|)$ a máme $\le k$ úrovní

1. bez izolovaných vrcholů $|T|\le 2^k$
2. zlepšení-$v$ vrchol maximálního stupně, předpokládejme $\Delta >1$

$$T(k)\le 1+T(k-1)+T(k-2)\dots |T|\le (1.69\dots {)}^k$$

3. $\Delta >2$ $T(k)\le 1+T(k-1)+T(k-2)\dots |T|\le (1.466{)}^k$.

---

Closest string

Vstup: $x_1,\dots ,x_k\in {\sum }^l\dots k$ řetězců délky $l$ na $\Sigma$, optimalizační problém je dosáhnou $y\in {\Sigma }^l$, který minimalizuje ${\max }_i\text{dist}(y,x_i)$. Parametrizovaný problém s parametrem $d$ je, zda existuje $y\in {\Sigma }^l:\text{dist}(y,x_i)\le d$, pro všechna $i$.

Preprocessing: vymažeme to kde se stringy shodují$\dots l^{\prime }\le k\cdot d$.

Řešme rozšířený problém navíc daného $z$ a $d^{\prime }<d$ a hledáme $y$, kde $\forall i:\text{dist}(y,x_i)\le d$ a $\text{dist}(y,z)\le d^{\prime }$

Alg: Výchozí volání ($x_1,\dots ,x_k,x_1,d,d$).

1. pokud $\forall i:\text{dist}(z,x_i)\le d\dots$return $z$
2. jinak:
   1. pokud $d^{\prime }=0\dots$return NE
   2. jinak $d^{\prime }\ge 1$ a $\exists x_i:\text{dist}(z,x_i)>d$ určeme množinu $P$ pozic, ve kterých se $z$ a $x_i$ liší a pokud jich zbylo více než $d+1$, tak vyberu jen $d+1$ z nich
   3. vyzkoušíme rekurentně pro CLOSEST STRING AUG($x_1,\dots ,x_k,z_p,d,d^{\prime }-1$) $d+1$ z $P$ případů, kdy pro $p\in P$ zavedeme $z_p:z_p=\{\begin{array}{ll}(x_i{)}_p& \\ z_j& \dots j\ne p\end{array}$ Analýza: Velikost stromu

$$T(d^{\prime })\le 1+(d+1)T(d^{\prime }-1)\to (d+1{)}^d.$$