Question

Definition: Given a Graph \(\mathrm{G}=(\mathrm{V}, \mathrm{E})\), define the complement graph of \(\mathrm{G}, \overline{\boldsymbol{G}}\), to be \(\bar{G}=(\mathrm{V}, E)\) where \(E\) is the complement set of edges. That is \((\mathrm{v}, \mathrm{w})\) is in \(E\) if and only if \((\mathrm{v}, \mathrm{w}) \notin \mathrm{E}\) Theorem: Given \(\mathrm{G}\), the complement graph of \(\mathrm{G}, \bar{G}\) can be constructed in polynomial time. Proof: To construct \(G\), construct a copy of \(\mathrm{V}\) (linear time) and then construct \(E\) by

a) constructing all possible edges of between vertices in \(\mathrm{V}\) (effectively constructing the complete graph on the vertices \(\mathrm{V}\). This can be done in quadratic time in \(|\mathrm{V}|\)

b) Then traverse the adjacency list of \(\mathrm{E}\) and delete those edges from the from the complete set of edges just constructed. This again can be done in at worse \(\mathrm{O}\left(|\mathrm{V}|^{2}\right)\) time. This leaves you with the set of edges of \(E\). Thus the whole procedure can be done in polynomial time. Theorem: \(\mathrm{C}\) is a vertex cover in a graph \(\mathrm{G}=(\mathrm{V}, \mathrm{E})\) if and only if the set of vertices \(\mathrm{V}-\mathrm{C}\) is a clique in the complement graph of \(\mathrm{G}\)

1. Proof: C a vertex cover implies that \(\mathbf{V}-\mathbf{C}\) is a clique Suppose \(\mathrm{V}-\mathrm{C}\) is not a clique in \(G\).

\(\rightarrow\) Then two vertices in \(\mathrm{V}-\mathrm{C}\) are not connected by an edge in \(E\), thus \((\mathrm{v}, \mathrm{w}) \notin E .\)

\(\rightarrow(\mathrm{v}, \mathrm{w}) \in \mathrm{E}\)

\(\rightarrow\) But \(v\) and \(w\) are in \(V=C\), thus \(v, w\) are not in \(C\), thus \(C\) is not a vertex cover since it does not cover \((v, w)\)

Therefore \(\mathrm{C}\) a vertex cover implies that \(\mathrm{V}-\mathrm{C}\) is a clique. Proof: \(\mathrm{V}-\mathrm{C}\) is a clique implies \(\mathrm{C}\) a vertex cover Suppose \(\mathrm{C}\) is not a vertex cover for \(\mathrm{G}\)

\(\rightarrow\) Then there is an edge \((\mathrm{v}, \mathrm{w}) \in \mathrm{E}\) where neither \(\mathrm{v}\) nor \(\mathrm{w}\) is in \(\mathrm{C}\)

\(\rightarrow\) Since \(v, w \notin C\) that implies that both \(v\) and \(w\) are in \(V-C\)

\(\rightarrow\) But \((\mathrm{v}, \mathrm{w})\) in \(\mathrm{E}\) means that \((\mathrm{v}, \mathrm{w}) \notin \bar{E}\)

\(\rightarrow\) This contradicts that \(\mathrm{V}-\mathrm{C}\) is a clique Therefore \(\mathrm{V}-\mathrm{C}\) is a clique implies \(\mathrm{C}\) a vertex cover Theorem: Min Vertex cover and Max Clique are polynomial reducible to each other. (Thus if you can solve one problem in polynomial time you can solve the other problem in polynomial time.) Proof: Since getting the complement graph takes only polynomial time, the transformation from \(\mathrm{G}\) to \(G\) is polynomial time. Suppose you can solve Max Clique in polynomial time. Write this max clique as a complement of some set of vertices

C. that is \(\mathrm{V}\) - \(\mathrm{C}\). Then \(\mathrm{C}\) must be the smallest vertex cover in \(\mathrm{G}\). (If there is a smaller vertex cover, say \(\mathrm{C}\) ', then \(\mathrm{V}-\mathrm{C}^{\prime}\) would be a larger clique than \(\mathrm{V}\) -C. ) A similar argument works to show that if you can solve Min Vertex cover in polynomial time you can solve Max Clique in polynomial time.

Show that the following two problems are polynomial reducible to each other. Minimum Vertex cover and Maximum Independent Set

(ii) Determine, for a given graph \(\mathrm{G}=(\mathrm{V}, \mathrm{E})\) and a positive integer \(\mathrm{m} \leq|\mathrm{V}|\), whether there is a vertex cover of size \(\mathrm{m}\) or less for \(\mathrm{G}\) (A vertex cover of size \(\mathrm{m}\) for a graph \(\mathrm{G}=(\mathrm{V}, \mathrm{E})\) is a subset \(\mathrm{V}^{\prime} \subseteq \mathrm{V}\) such that \(\left|\mathrm{V}^{\prime}\right|=\mathrm{m}\) and, for each edge \((\mathrm{u}, \mathrm{v}) \in \mathrm{E}\) at least one of \(\mathrm{u}\) and \(\mathrm{v}\) belongs to \(\left.\mathrm{V}^{\prime} .\right)\)

Answer 1

Vertex Cover: Vertex cover is a set of vertices C such that every edge has atleast one edge belonging to C. It is a NP-complete problem. For decision version, Given a graph G and a number k, does G contain a vertex cover of size at most k

Independent Set: Independent set is a set of vertices S in a graph such that no two vertices are adjacent to each other i.e no two vertices in the S share same edge. For decision version, Given graph G and a number k, does G contain a set of at least k independent vertices?

To prove that two problems are polynomially reducible to each other we need another theorem.

Theorem: If G = (V, E) is a graph, then S is an independent set $\Leftrightarrow$ V − S is a vertex cover.

Proof:

Necessity: Suppose S is an independent set, and e=(u,v) be an edge so from the definition u and v cannot be in S. So atleast one of the u,v should be in V-S. So V-S is a vertex cover for the graph G.

Sufficiency:Suppose V − S is a vertex cover, and let u, v ∈ S. There can’t be an edge between u and v (otherwise, that edge wouldn’t be covered in V − S). So, S is an independent set.

$Independent Set \leqslant p Vertex Cover$

Proof: To prove this we need to show that any instance of the independent set can be converted into an instant of Vertex cover i.e a 'yes' instance of independent set should match to 'yes' instance of vertex cover and 'no' instance to that of 'no'.

For a given instance of Independent Set (G,k), find the vertex cover by decision making if there is a vertex cover V-S of size less than |V|-k. By the previous theorem, S is an independent set if and only if V-S is a vertex cover

If there is yes instance, then S must be an independent of size $\geq$ |V| - k

If there is a no instance then there is no vertex cover of size $\leq$ |V| - k, so there is no independent set of size $\geq$ k.

$Vertex Cover \leq Independent Set$

Proof: Similarly, To prove this we need to show that any instance of Vertex cover the can be converted into an instant of independent set i.e a 'yes' instance of Vertex Cover should match to 'yes' instance of vertex cover and 'no' instance to that of 'no'.

By decision algorithm we can  decide if G has an vertex cover of size $\leq$ k, we ask if it has an independent set of size $\geq$ n − k.

If there is yes instance, then there exists a vertex cover V-S.

If there is a no instance, then there is no vertex cover V - S.

There form Above proofs we can conclude that both Vertex cover independent set are polynomially reducible to each other.

(ii) To determine whether for a given graph G=(V,E) there exists a vertex cover of size m we can use the above reductions.

From the second reduction, we need to find a independent set S of the graph G such that |S| $\geq$ |V|-m in order to find whether there is a vertex cover of size m.