Vertex Cover, Independent Set, Clique, and Matching
Independent set <=> clique
An independent set S of G corresponds to a clique containing the same set of vertices S in G’s complement graph (flipping edges in E and not in E). This is because all vertex pair (i, j) in S is not an edge in G is equivalent to all vertex pair (i, j) in S is an edge in G’s complement graph.
Vertex cover <=> independent set
A vertex cover S in graph G corresponds to an independent set $V \setminus S$ in G. If S is a valid vertex cover, any vertex pair (i, j) in $V \setminus S$ is not an edge in G, so $V \setminus S$ is independent set. If $V \setminus S$ is an independent set, for any edge at least one endpoint is in S, so S is a vertex cover. Then MIN-VERTEX-COVER = MAX-INDEPENDENT-SET.
Vertex cover <=> matching (in bipartite graph)
In bipartite graph, the size of any matching is less or equal than the size of any vertex cover, and MAX-MATCHING = MIN-VERTEX-COVER.
(a) Any matching <= any vertex cover
Given a matching in a bipartite graph, we need to select at least one vertex from every matched edge. Otherwise, there exist matched edge that isn’t covered. So matching <= vertex cover.
(b) MAX-MATCHING = MIN-VERTEX-COVER
From a maximum matching M, we can construct a vertex cover by (1) direct all matched edge from Y to X and all unmatched edge from X to Y, (2) run a DFS from all unmatched vertices in X, and (3) construct set R by all unvisited vertices in X and all visited vertices in Y.
The only type of edge that has both endpoints not in R consists of a visited vertex u in X and a unvisited vertex v in Y. If {u, v} is a unmatched edge, then v should be reachable by appending (u, v) to the path to u. If {u, v} is a matched edge, then the only incoming edge towards u is (v, u). Then u cannot be reachable if v is unreachable. Both cases lead to contradiction. So all edge contains some endpoint in R and R is a valid vertex cover.
Unvisited vertices in X corresponds to a matched edge (otherwise they will be initially visited by DFS). Visited vertices in Y corresponds to a matched edge (otherwise we have an augmenting path between two unmatched vertices, but M is a maximum matching). Because unvisited vertices in X are not reachable, these edges can not intersect. So |R| <= |M|. Then there exist some vertex cover whose size is at most |M|, so MIN-VERTEX-COVER <= |M|, and MIN-VERTEX-COVER = MAX-MATCHING.