4.přednáška

Feedback Vertex set

$X\subseteq G_V$ takový že $G\setminus X$ je les, existuje $|X|\le k$? V $G$ je minimální stupeň 3, slučováním. Seřadíme si vrcholy dle stupně a vezmeme prvních 3k. Lemma: Pokud $\delta (G)\ge 3$ a FVS $X$ velikosti $\le k$, potom $V_{3k}\cap X\ne \varnothing$. Důkaz: $G\setminus X$ má $|V|-|X|$ vrcholů $⟹$ $\le |V|-|X|-1$ hran.

$$\begin{array}{rl}\sum _{v\in X}deg(v_i)+|V|-|X|+1& \ge |E|\\ \sum _{v\in X}deg(v_i-1)& \ge |E|-|V|+1.\end{array}$$

Pro spor mějme $X\cap V_{3k}=\varnothing$. Sčítáme stupně

1. ${\sum }_{i=1}^{3k}(deg(v_i)-1)\ge 3{\sum }_{v\in X}(deg(v)-1)\ge 3(|E|-|V|+1)$
2. ${\sum }_{i=3k+1}^n(deg(v_i)-1)\ge {\sum }_{v\in X}(deg(v)-1)\ge |E|-|V|+1$ 1+2 $⟹$

$$\sum _{v\in V}(deg(v)-1)=2|E|-|V|\ge 4|E|-4|V|+4⟹2|E|\le 3|V|-4$$

kde to je spor se $\delta (G)\ge 3$

Branching:

• aplikujeme redukce stupňů a
• rekurentně rozlišíme 3k případů dle množiny největších stupů.

→ $O^{\ast }((3k{)}^k)$.

---

Vrcholové pokrytí nad lineárním programováním

$V{C}^{\ast }(G)$ LP v půlkách relaxace. VC nad LP $(G,d)$: Existuje VC velikosti $\le \underset{k}{\underbrace{V{C}^{\ast }(G)+d}}$? Pozorování: Redukce $(G,d)\to (G_{1/2},k-|V|)$ z 2.přednáška. Pokud existuje řešení v půlkách s $V_1\ne \varnothing$, provedeme ji. Získáme řešení $V_{1/2}=V_G$ a víme, že je optimální. Potom vyzkoušíme $v\in V_G$, zda nemůže být ve $V_1$, pokud získáme optimum, tak redukujeme. → poly-redukce, získáme $G$, t.ž. LP má jediné optimální řešení $V_G=V_{1/2}$. Zvolíme libovolně $e=(u,v)\in E$ a provedeme branching na odebrání $u$ nebo $v$.

Búno $G-u=G^{\prime }$, $k-1=k^{\prime }$, pak jaké je $d^{\prime }$. $d$ klesne alespoň o $1/2$.

$$V{C}^{\ast }(G^{\prime })\le V{C}^{\ast }(G)-\frac{1}{2}.$$

protože řešení $V_{1/2}=V_G^{\prime }$ je přípustné pro $G^{\prime }$. Ale ve skutečnosti platí rovnost protože by vznikl rozpor s řešením v půlkách, protože s $<$ doplníme $X_u=1$ a to je optimem na $G$, co není celé v půlkách.

$$\begin{array}{rl}{k}^{\prime }=k-1& =V{C}^{\ast }(G)+d-1\\ V{C}^{\ast }(G^{\prime })+d^{\prime }& =V{C}^{\ast }(G)-\frac{1}{2}+d^{\prime }\\ d^{\prime }& =d-\frac{1}{2}\end{array}$$

Strom je velký $2d$, vždy dvě větvení, $O^{\ast }(2^{2d})=O^{\ast }(4^d)$. V listech provedeme redukci ještě jednou máme $G_{1/2}=\varnothing$, pak je to YES a jinak NO.

---