Alex's Notes

The k-colourings problem is NP-complete

6 min read

Statement

Lemma

The k-vertex-colouring problem is NP-complete.

Proof

We have already show The k-colourings problem is in NP. So all that is left to show is that it is NP-hard.

We can prove NP-complete using the SAT problem. (Which we have SAT is NP-complete.)

Proof outline.

Suppose we have an instance of the of the SAT problem with variables for and clauses for . Note we assume each variable appears in at most one literal per clause so the clauses are of size at most . Then we are going to define a graph for the colouring problem. (Note: If , we solve the problem in polynomial time using the 2-SAT algorithm using SCC - so from now on assume .)

The graph has the following vertices:

  • A and vertex for true and false,
  • Base vertices for ,
  • Variable vertices and with , and
  • Clause vertices with and Suppose clauses are of size at most.

The graph has the following edges:

  • With , and for make a clique of size ,
  • For each pair variable vertices and connect the to one another i.e. ,
  • For each variable vertex and connect them to all i.e. ,
  • For each clause the vertices form a clique of size ,
  • For each clause for some connect to i.e. , and
  • For connect to , i.e. .

This graph takes to build the graph as we need to iterate through clauses and variables so can be done in polynomial time. We provide graph to the -colouring problem.

If the graph has no colouring, say that has no assignment. If the graph has an colouring from Claim 1 we know each variable vertex and as the same colour as either or . Return the assignment as true if or false otherwise. This takes at most as we have to loop through the variables checking their assignment - so can be done in polynomial time.

Suppose the constructed colouring problem has a solution. From Claim 1 we have a valid assignment and from Claim 2 one literal in every clauses is assigned True. Therefore, this assignment satisfies .

Suppose we have an assignment to (where is 0 if it is False and 1 if it is True) that is a solution to the SAT problem . Then build the following colouring

  • Set , , and ,
  • Set and , and
  • Lastly for each clause find literal where we have is True set the corresponding and assign (note as there are at most literals ) then assign each other a different one of the remaining colours.

Lets check the edges to ensure this is a valid colouring:

  • As , and are assigned distinct colours these edges all connect vertices of different colours,
  • As then and the edge is respected,
  • As and we have these connected edges are respected,
  • As each of the clause vertices receive a distinct colour the clique edges are respected,
  • For each clause as the only have or and we have the rest of the literals connect to vertex with so these edges are respected, and lastly
  • As , and for all where we have all the edges are respected.

Therefore this is a valid -colouring of our constructed .

So we have this is a many-one reduction reduction of the SAT problem to the k-colourings problem (graphs). Giving it is NP-complete.

Claim 1

Claim 1

If the constructed graph has a -colouring then the following holds

  • moreover , , and all have distinct vertices that use all colours,
  • for every , and
  • for every .

Proof of Claim 1

The first statement holds as , , and are all connected in a clique of size .

The second statement holds as and are connected.

The last statement holds as , , and are all connected in a clique of size so have different colours from one another. Therefore the colours each and are assignment must be the same as that of and up to some order.

Claim 2

Claim 2

If the constructed graph has a -colouring then for each clause for some the following holds:

  • The clause vertices all have distinct colours that use the colours,
  • The clause vertex with the colouring is connected with a literal vertex of the clause , i.e. , and
  • The literal vertex has

Proof of Claim 2

The first statement holds as form a clique of size .

As the vertices have every colour there exists a vertex where . As vertices with are connected with vertex we have for all . So and it is connected to a literal vertex. This shows the second statement.

From Claim 1 we have , however as is connected to with by exclusion we have ). Giving the final statement.

Graph View

Backlinks