Using coloring optimization or coloring decision to solve coloring search

Question

How can you show that coloring search can be solved by making a polynomial number of calls to the solution for coloring optimization or coloring decision? (Coloring search is the algorithm to color the vertices of a graph such that adjacent vertices have a different color.)

I wasn't sure how to solve it, but here is what I attempted (I chose to use coloring optimization):

Coloring search can be solved by calling coloring optimization and finding the value $m$, which is the amount of colors needed so that no two adjacent vertices have the same color. Once $m$ is found, coloring search can color the vertices of the graph by rotating through the $m$ different colors for each vertex.

Am I on the right track?

Answer 1

Given a graph $G$, we want to do two things:

1. Find the smallest $k$ such that $G$ is $k$-colourable,
2. Given such a $k$, find a colouring of $G$ with $k$ colours.

If we have an oracle for the decision version of the colouring problem, we can do both.

For the first part we can perform a search to find the optimal $k$. Even the naive approach here is okay, we can just sequentially ask if $G$ is $k$-colourable for $k=1,2,\ldots,n$. Then we make at most $n$ calls to the oracle. Of course we can perform a binary search and cut this down to $\log n$ calls. (Note that this is also how we solve the optimization version with the decision version).

Then given that we've worked out what $k$ is optimal, we can find a $k$-colouring of $G$ using the decision oracle. The only wrinkle is that the oracle doesn't take partial colourings, so we need a way of encoding in the graph that a particular vertex has been coloured a particular colour.

To do this we actually use the oracle on an auxilliary graph, which we will call $G^{+}$, that is $G$ plus a $K_{k}$ with some additional edges. Of course the $K_{k}$ needs exactly $k$ colours, so we can use its vertices to indicate which colours are available for a vertex. Let the vertices $\{k_{1},\ldots,k_{k}\}$ of the $K_{k}$ correspond to the colours $\{c_{1},\ldots,c_{k}\}$. Then we will indicate that a vertex $v$ in $G$ cannot be coloured with colour $c_{i}$ by making it adjacent to $k_{i}$. Furthermore if we colour a vertex with colour $c_{j}$ we will make it adjacent to every $k_{i}$ with $i\neq j$ (and not adjacent to $k_{j}$).

Then we repeatedly do the following:

1. Pick an 'uncoloured' vertex $v \in V(G)$.
2. For every vertex $u \in N(v)$, if $u$ has been coloured, then there is one $k_{i}$ such that $uk_{i} \notin E(G)$. Add the edge $vk_{i}$ to $E$.
3. For the remaining vertices $k_{j}$ such that $vk_{j}$ is not yet in $E$, we add all other edges between $v$ and the $K_{k}$ and ask the oracle if the new graph is $k$-colourable. If it is, we keep this graph and move on to the next vertex, if the answer is No, we undo step 3 and try with the next $k_{j}$.

Note that as $G$ is $k$-colourable, there is some $k_{j}$ that step three will work with. Then when we have processed every vertex, each vertex in $G$ is not adjacent to exactly one vertex in the $K_{k}$, this indicates which colour the vertex can be coloured with to obtain the colouring. From step 2, we see that this cannot be the same colour as any of its neighbours.

At step three we make at most $k$ calls to the oracle, and we do this for each vertex in $G$, so in total we make at most $(k+1)n$ calls to the oracle (including the search for $k$).