Alex's Notes

Week 10 - Graph problem complexity

2 min read

Week 10 - Graph problem complexity

Independent set problem

Independent set (graph)

Independent set (graph)

In a graph a subset is an independent set if the induced subgraph on has no edges. (i.e. for all either or .)

Link to original

Therefore we have the following problem.

Statement

Max independent set problem

Given a undirected graph what is the size of the largest independent set in ?

Link to original

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.

Statement

Independent set of a given size

Given a undirected graph and positive integer . Does have an independent set of size ?

Link to original

Independent set of a given size is NP-Complete

Independent set of a given size is in NP

Statement

Lemma

Independent set of a given size is in NP.

Proof

This problem is in the form of a search problem as either you provide an independent set of the required size or you say no such set exists.

For a undirected graph , positive integer , and supposed solution to the Independent set of a given size. It takes to check this solution. We have to do two steps:

  • Check .
  • Check for all that or . The first step takes and the second .

Therefore this problem is in NP.

Link to original

More over we have it is NP-Complete.

Independent set of a given size is NP-complete

Statement

Lemma

Independent set of a given size is NP-complete.

Proof

As Independent set of a given size is in NP all we need to show is that Independent set of a given size is NP-hard.

To show this we are going to find a many-one reduction of the 3-SAT problem to Independent set of a given size problem. (We know 3-SAT is NP-complete so this gives us that Independent set of a given size is also NP-complete.) This will involve:

Suppose we are given a 3-SAT problem with variables and clauses . We know each clause has at most 3 literals , , and (maybe less). Set be the set of literals in the clauses . We are going to construct a graph where each clauses is a clique and we connect any literals to their inverses. So we will two sets of edges, clause edges and negation edges Then an independent set of size will indicate a set of literals to set to true to get a correct assignment. Define the undirected graph We now apply the solution of Independent set of a given size to and .

To make we need to scan through each clause and make at most 3 vertices, this is . Then to connect the edges we need to first add the which takes again. To find all the negation edges for each variable we need to find all the literals using that, this takes . Therefore this process takes and is polynomial time in the size of the input.

When we have a solution to the Independent set of a given size problem we all the literals in the independent set to true. (This is valid as we know no 2 literals in this independent set can be the negation of one another from the negation edges.) Then for any left over variables we just set them to be true.

This process takes time as we have to check if a variable is in the set of returned literals.

Suppose the 3-SAT problem has an assignment that solves it.

For each clause at least one literal must be correct, define this set .

The set forms the independent set in of size . As is a valid assignment for we have . By definition each literal in belongs to a different clause.

Suppose we have an independent set in of size .

As this is an independent set the negation edges guarantee for we have . Therefore we can define a partial assignment of the original variables where True for . This can be extended to a full assignment of the original variables where if is not assigned we just set True.

As each clause is a clique in from the clause edges every element of belongs to a different clause. As it is of size each clause has an element in . So .

As we have at least one literal in each clause being true, the assignment satisfies the original CNF . Therefore is satisfiable.

This gives the reduction of 3-SAT to the Independent set of a given size problem and makes it NP-complete.

Link to original

Max independent set is NP-hard

Max independent set problem is NP-hard

Statement

Lemma

Max independent set problem is NP-hard.

Proof

We know the Independent set of a given size is NP-complete, therefore it is NP-hard. We can reduce the Independent set of a given size to max independent set problem using the straight forward Many-one reduction.

Suppose we have a graph and integer . Pass this graph to the max independent set problem. This step is as we need to do no manipulation.

The solution provides a max independent set. If then return , otherwise return no. This step takes so it is polynomial in the input size.

If the graph has an independent set of size at least then its max independent set is of size , so we return true in the case.

If the graph has a max independent set of size greater than then it has an independent set of size by definition.

Link to original

Clique problem

Clique (graph)

Clique (graph)

In an undirected graph a set of vertices is a clique if the induced subgraph on is the complete graph on . (i.e. .)

Link to original

So similarly with the Independent set problem we can define two problems.

Statement

Max clique size problem

Given an undirected graph what is the largest such that the induced graph on forms a clique.

Link to original

Statement

Clique of a given size problem

Given an undirected graph and a positive integer . Does there exist a clique of size at least if so what is it?

Link to original

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

Statement

Lemma

Clique of a given size problem is in NP.

Proof

This problem is in the form of a search problem as either you provide a clique of the required size or you say no such set exists.

For a undirected graph , positive integer , and supposed solution to the Clique of a given size problem. It takes to check this solution. We have to do two steps:

  • Check .
  • Check for all for all . The first step takes and the second .

Therefore this problem is in NP.

Link to original

Notice that really clique problems and independent set problems are dual to one another. Through the concept of the complement graph.

Complement graph

Complement graph

Given an undirected graph or directed graph . We define the complement graph

Link to original

This is formalised through the following lemma.

Cliques in G are independent sets in the complement

Statement

Lemma

For a undirected graph and we have the following equivalence: is a clique in if and only if is an independent set in the complement graph.

Proof

Suppose is clique in then for all with . As then for all with we have so is a independent set in .

Similarly if is an independent set in then for all with . Therefore by definition , and we have is a clique.

Link to original

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

Statement

Lemma

Clique of a given size problem is NP-Complete.

Proof

We have already shown that Clique of a given size problem is in NP.

We will show that Independent set of a given size has a many-one reduction to Clique of a given size problem.

Suppose we have an undirected graph and a positive integer. If we are looking for an independent set of size , we will pass the complement graph and to the Clique of a given size problem.

Calculating the complement graph takes , therefore this reduction is in polynomial time.

Then if a clique is returned in then we return this as our independent set in .

This takes as we are doing no transformations to the output.

As Cliques in G are independent sets in the complement we have a solution to the Independent set of a given size if and only if we have a solution to the Clique of a given size problem.

This gives Clique of a given size problem is NP-hard making it NP-complete.

Link to original

We get a similar result for the max problem.

Max clique problem is NP-hard

Statement

Lemma

Max clique problem is NP-hard.

Proof

We know the Clique of a given size problem is NP-complete, therefore it is NP-hard. We can reduce the Clique of a given size problem to Max clique problem using the straight forward Many-one reduction.

Suppose we have a graph and integer . Pass this graph to the Max clique problem. This step is as we need to do no manipulation.

The solution provides a max clique. If then return , otherwise return no. This step takes so it is polynomial in the input size.

If the graph has a clique of size at least then its max clique is of size , so we return true in the case.

If the graph has a max clique of size greater than then it has an clique of size by definition.

Link to original

Vertex cover problem

First we define a new concept.

Vertex cover

Vertex cover

Given an undirected graph a set is a vertex cover if for all we have or .

Link to original

Then similarly to before we get two logical problems.

Statement

Minimum vertex cover problem

Given an undirected graph provide a vertex cover of smallest size.

Link to original

Statement

Vertex cover of a given size

Given an undirected graph and a positive integer , is there a vertex cover using at most vertices, if so what is it?

Link to original

Like before the minimum problem is not known to be in NP, however the second is.

Vertex cover of a given size is NP

Statement

Lemma

Vertex cover of a given size is NP.

Proof

First note that this problem is of the correct form to be a search problem. Either there is a vertex cover of the required size and we return it or we say no such cover exists.

For a undirected graph if we are provided with a purposed solution to the problem there are two steps to checking it:

  • Check that , this takes .
  • Check for every edge that or , that takes . Therefore checking a solution takes polynomial time in the input size.

This gives that the Vertex cover of a given size is in NP.

Link to original

The vertex cover is closely related to the independent set.

Vertex cover if and only if the complement is an independent set

Statement

Lemma

Suppose we have an undirected graph with . Then is a vertex cover if and only if is an independent set.

Proof

Suppose is a vertex cover.

For all either or , therefore no edge in connects two vertices in making an independent set.

Suppose is an independent set.

Let , as is an independent set either or . Therefore is a vertex cover by definition.

Link to original

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

Statement

Lemma

Vertex cover of a given size is NP-complete.

Proof

As Vertex cover of a given size is NP we only need to show the problem is NP-hard.

We will show that the Independent set of a given size has a many-one reduction to the Vertex cover of a given size.

Suppose we have a undirected graph and a positive integer and we are looking for a independent set of size .

Provide and to the Vertex cover of a given size problem. This takes as we are doing no manipulation to the graph.

If we are provided a vertex cover of size at most return the set as the solution to the Independent set of a given size problem. This takes to run so is polynomial time in the input size. (Here so is of the correct size.)

If there is a solution to the Independent set of a given size with the size of at least then the compliment is a vertex cover of size at most from Vertex cover if and only if the complement is an independent set.

Similarly if there is a solution to the Vertex cover of a given size with size of at most then the compliment is a independent set of size at least from Vertex cover if and only if the complement is an independent set.

Therefore as Independent set of a given size is NP-complete we have Vertex cover of a given size is NP-hard, which from above gives us it is NP-complete.

Link to original

From this we get the Minimum vertex cover problem is NP-hard.

Minimum vertex cover problem is NP-hard

Statement

Lemma

Minimum vertex cover problem is NP-hard.

Proof

We have shown that Vertex cover of a given size is NP-complete. So we will find a many-one reduction of Vertex cover of a given size to Minimum vertex cover problem to show it is NP-hard.

Suppose we have an undirected graph and a positive integer . If we are looking for a vertex cover of size at most , pass to our solution to the Minimum vertex cover problem.

This takes as we are doing no manipulations.

We get back minimum cover . If return to the Vertex cover of a given size problem, otherwise return no. This step takes so is polynomial time in the input size.

If there is a vertex cover of size less than then the minimum vertex cover will have size less than .

Equally if the minimum vertex cover has size less than then there is a vertex cover of size less than .

So we have that Vertex cover of a given size has a many-one reduction to Minimum vertex cover problem. Giving that Minimum vertex cover problem is NP-hard.

Link to original

Practice problems

From Algorithms by S. Dasgupta, C. Papadimitriou, and U. Vazirani.

8.4 NP-completeness error

8.10 Proof by generalisation

8.14 Clique + Independent set (HW 6 assessed)

8.19 Kite

Graph View

Backlinks