Graphs - Matching ::

A matching in a graph is a subset of edges that have no vertices in common.

A matching is ==maximal== if we cannot add any more edges to it - we’ve found a local optimum for matching nodes. ![[Pasted image 20230116154549.png]]

A matching is the ==maximum== if there does not exist any other matching that has more edges – +global optimum

cus whenever we would find another node that is not found and could contribute to our matching, we can say that our assumption - to have the maximal matching already - invalid and we have to increase our set of vertex cover >> thus we will continue until all have been found and we can conclude with the max matching ==> we found the upper bound because there is not more to be found.

![[Pasted image 20230116154555.png]]

How to find a maximal Matching ?

We can generate a maximal matching greedily :: start with an empty set of edges, and keep on adding edges that do not have any vertex in commong.

Let $F\subset E$ be any matching, and $S^{\ast }$ an optimal solution of vertex cover. Then $|F|\le |S^{\ast }|$.

Proof of it :: In the minimal matching, the edges are not touching. For each of these edges, one of its two vertices need to be i the vertex cover. So we need at least as many vertices cover as we have edges in the matching.

Upper bounds ::

Consider a maximal matching $F\subset E$ define S as the set of all vertices touched by the matching - so we add both end points for each edge. Then S is a vertex cover, and we have the inequality $|S{|}^{\ast }\le |S|=2|F|$- Where $S^{\ast }$ is an optimal solution of vertex cover.

Proof to it ::

Assume that there is an edge that is not touched by the current Set S. As this edge does not have any vertex in common with S, we could add this edge to the matching F However by the assumption we made earlier the matching F was supposed to be a maxima.

How can we build an algorithm for vertex cover with a nice approximation guarantee?

We require a maximal matching >> matching that satisfies our vertex cover and we cannot add anymore nodes to the current matching –> not the maximum is required, that provides the matching with the most edges

Proposition : 2-Approximation ::

Construct a maximal matching F by the greedy procedure outline above. Define S as the set of all vertices of these edges - with $|S|=2|F|$ Then $|S|S$ is an 2-approximation to the optimal solution of our vertex cover. !

Proof to it :: We denote an optimal solution of vertex cover by $S^{\ast }$. By the two propositions before we know : $|F|\le |S^{\ast }|\le |S|=2|F|$

Wir wissen die Menge der optimalen Länge und suchen eine mögliche Lösung, welches nah genug approximieren kann. Unser Algorithmus schließt mit einer gefundenen Lösungsmenge $S^{\ast }$ ab und wir können dann darauf approximieren, dass unsere Menge um den Faktor 2 ==von F== gelegen ist.

This is an approximation Algorithm with a constant factor.