### General - gets approximate optimal solution for [[Vertex Cover Problem]], where $\alpha = 2$ - (in worst case is twice as bad as optimal value) ### Matchings Explanation - we'll use the notion of a *matching* - a subset of edges that have no vertices in common - a *matching* is *maximal* if no more edges can be added to it - (any further edge would touch an existing vertex in the edge set) - *maximal matchings* are easy to generate - simply repeatedly pick edges that are disjoint from the ones chosen already, until this is no longer possible ### The Algorithm 1. Find a maximal matching $M$ in $G$ 2. Output $P$ = {endpoints of $M$} - $\alpha = 2$ ### Claims - claim 1: - if you have a vertex cover $S \subseteq V$ and a matching $M \subseteq E$ - then you have $|M| \leq |S|$ - proof: - $\forall$ edge $\in\,M$, $\exists$ vertex $\in S$ that only touches that match edge and no other match edge in $M$ - in vertex cover, the cover vertex set must touch all edges in the graph - this means each match edge must end up with at least 1 vertex in the cover set - match edges also cannot share endpoints, so each match edge must have 1 or 2 unique vertex cover vertices - claim 2: - $M \subseteq E$ is a maximal matching - then the endpoints of edges in $M$ can be a vertex cover (aka covers all edges) - proof: - If this set of endpoints $P$ does not cover all edges, then $\exists$ an edge that has 2 endpoints not included in $P$ - But $M$ was already defined as maximal matching and should have added this edge already. Contradiction.