Hopcroft-Karp

V bipartitních grafech maximální párování m velikost stejnou jako vrcholové pokrytí a máme poly alg. $O (m n)$

Definice: Korunní rozklad $G$ je $V = C \dot{\cup} H \dot{\cup} R$ , kde

$H \neq = \emptyset$ ,
$C$ je nezávislá,
mezi $C$ a $R$ nevede hrana,
$G$ obsahuje párování mezi $H, C$ velikosti $H$ .

Lemma: Pro $G$ $∣ V ∣ \geq 3 k + 1$ existuje algortimus, který buď najde párování velikosti $\geq k + 1$ , nebo máme nějaký horní odhad.

DK:

hladově najdeme maximální párování (nepřidatelná další hrana) $N$ ,předpokladem je $∣ M ∣ \leq k$ , jinak NE, tedy $V ∖ N$ je nezávislá množina $I$ , kde $E^{'}$ jsou hrany z $I$ do $N$ . $E^{'}$ indukuje bip. graf
najdeme největší párování $G ∣_{E^{'}}$ a spojující VC $X$ , jménem $M^{'}$ , předpokladem je $∣ M^{'} ∣ = ∣ X ∣ \leq k$ , jinak NE. Protože $∣ X ∣ < ∣ I ∣ \land X ⊈ I$ , $⟹ X \cap V_{M} \neq = \emptyset$ .
Zvolíme $H := X \cap V_{M}$ , $C := V_{M^{'}} \cap I$ , $R$ je zbytkem Zbývá bod 3. definice, $C$ do $X$ nic společného nemají $W \subset C \Rightarrow v \in V_{M}$ , HopcroftKarp $\Rightarrow v \neq \in X$ , hrana $v w$ by musela být pokryta $X$ , takže $v \in X \Rightarrow v \in X \cap V_{M} \Rightarrow v \in H \Rightarrow\in R$ spor

Použití $G$ , búno bez izolovaných vrcholů a má-li $\geq 3 k + 1$ vrcholů, tak aplikujeme lemma a máme NE, nebo $(H, C, R)$ $⟹$ velikost $\leq 3 k$ .

Korektnost: musíme alespoň $∣ H ∣$ vrcholů

LP pro VC má řešení (v pol. čase) s hodnotami řešení ${0, 1, 1/2}$ $H = (V_{1} \times V_{2}, E^{'})$ - bip., párování $M^{'}$ v poly čase → ILP řešení → LP v $G$ , průměr z $H$ , $X_{v} = \frac{1}{2} (x_{v_{1}} + x_{v_{2}})$ . Optimalita nechť $y$ je nějaké optimum LP v $G$ . Zadefinujeme řešení $z$ na $H : z_{v_{1}} = y_{v_{1}}$ , z je přípustné řešení

v \in V_{1} \sum y_{v} = \frac{1}{2} \sum (z_{v_{2}} + z_{v_{2}}) .

∣ M ∣ = v \in G, pokud v \in M \sum \frac{1}{2} (y_{v_{2}} + y_{v_{2}}) = v \in V_{1} \sum x_{v} .

v \in V_{1} \sum y_{v} = \frac{1}{2} \sum (z_{v_{2}} + z_{v_{2}}) \geq \frac{1}{2} (v_{1}, v_{2}) \in M \sum (z_{v_{2}} + z_{v_{2}})

Mějme $S$ jako vertex cover v $H$ , $∣ S ∣ = ∣ H ∣$

\frac{1}{2} (v_{1}, v_{2}) \in M \sum (z_{v_{2}} + z_{v_{2}}) \geq \frac{1}{2} ∣ M ∣ = \frac{1}{2} ∣ S ∣ = \sum x_{v} .

Dokončení: Dáme $G, k$ vyřešíme půlkový LP, a rozdělí vrcholy dle hodnoto a zúžíme problematiku na vrcholy co mají polovinky a $0, 1$ jsou součástí VC.

Mějme LP v půlkách $G$ a dáno řešení $y$

v \in V_{G} \sum y_{v} = \frac{1}{2} (v_{1}, v_{2}) \in M \sum (z_{v_{2}} + z_{v_{2}}) \geq \frac{1}{2} (z_{u_{i}}, z_{v_{i}}^{'}) \in M \sum z_{u_{i}} + z_{v_{i}}^{'} \geq \frac{1}{2} ∣ M ∣ = \frac{1}{2} ∣ S ∣ = \sum x_{v} .

Použití

$G \dots$ vyřešíme LP v půlkách pro VC. pokud $\sum x_{v} > k \dots$ NE, protože celočíselné řešení nelepší, jinak řešme VC na $(G [V_{1/2}], k - ∣ V_{1} ∣)$

right Věta: Pro každé řešení LP v půlkách existuje optimální VC $S$ , t. ž. $V_{1} \subseteq S \subseteq V_{1} \cup V_{1/2}$ . DK: Dáno alt. VC $S^{*}$ , vezmeme $S := (S^{*} ∖ V_{0}) \cup V_{1}$

korektnost $\dots$ stačí hrany uvnitř $V_{1/2}$ , ty jsou pokryté $S^{*}$ ,
minimalita $\dots$ třeba ukázat, že $∣ S^{*} \cap V_{0} ∣ \geq ∣ V_{1} ∖ S^{*} ∣$

Sporem: kdyby platila " $<$ ", zavedeme $y$ :

y_{v} = {\frac{1}{2} if b

TODO:

Osobní stránka

Explorer

2.přednáška

Hopcroft-Karp

Použití

Graph View

Table of Contents

Backlinks