Week 10 - Graph problem complexity
Independent set problem
Therefore we have the following problem.
Though this problem is not known to be in NP as to verify if a set is the largest set we would require to calculate the set of largest size. However, we can edit this question to make one that is in NP.
Independent set of a given size is NP-Complete
Independent set of a given size is in NP
More over we have it is NP-Complete.
Independent set of a given size is NP-complete
Max independent set is NP-hard
Max independent set problem is NP-hard
Clique problem
So similarly with the Independent set problem we can define two problems.
Similarly to before the first problem is not know to be in NP however the second is.
Clique of a given size problem is in NP
Notice that really clique problems and independent set problems are dual to one another. Through the concept of the complement graph.
This is formalised through the following lemma.
Cliques in G are independent sets in the complement
So we can easily show Clique of a given size problem is NP-complete by finding a many-one reduction of Independent set of a given size.
Clique of a given size problem is NP-complete
We get a similar result for the max problem.
Vertex cover problem
First we define a new concept.
Then similarly to before we get two logical problems.
Like before the minimum problem is not known to be in NP, however the second is.
Vertex cover of a given size is NP
The vertex cover is closely related to the independent set.
Vertex cover if and only if the complement is an independent set
So we can prove Vertex cover of a given size is NP-complete by finding a many-one reduction of Independent set of a given size to it.
Vertex cover of a given size is NP-complete
From this we get the Minimum vertex cover problem is NP-hard.
Minimum vertex cover problem is NP-hard
Practice problems
From Algorithms by S. Dasgupta, C. Papadimitriou, and U. Vazirani.