Self-reducibility

When studying the complexity of problems, we often focus on decision problems. For example, NP-complete problems must be decision problems since they must be in NP. What about problems which aren't answered by a simple yes or no? What about finding the minimum vertex cover, or finding an actual $3$-coloring?

Well it turns out that most of the time, if we have an oracle TM with access to the decider for $X$, we can solve the search/optimisation version of $X$. This means that the search version of $X$ cook reduces to the decision version of $X$.

We take the search problem of finding a $3$-coloring of a graph $G=(V,E)$ as an example. Suppose we have access to an oracle which decides if its input graph has a valid $3$-coloring. We want to use this oracle to actually construct a $3$-coloring on $G$ in polynomial time.

First, we should check if $G$ has a valid $3$-coloring to begin with. If it does not then we halt. Otherwise, we can start building the $3$-coloring.

Let's impose an ordering on the vertices, $v_1<v_2<...<v_n$. We will color these vertices one by one starting from $v_1$. Suppose we have colored all vertices $v_1,...,v_{i-1}$ in a way that can be extended to the entire graph $G$. Let $C_i$ be the set of valid colors for $v_i$, for each $c\in C_i$ we assign $c$ to $v_i$. Now we need a way to test if our new coloring can be extended to the entire graph $G$. 

Since our oracle takes as input a graph and that is all, we can't just call the oracle on our graph since it will just ignore the colors we have assigned to it. We need a way to encode the choices of colors into a new graph $G'$ which is $3$-colorable iff the partial coloring can be extended to the entire graph $G$.

We propose the following construction for $G'$: merge all vertices with the same color into one super-vertex whose neighborhood is the union of the neighborhoods of all the vertices being merged. Uncolored vertices are left as in $G$.

Claim: The partial coloring over $v_1,...,v_i$ is extendable to the entire graph $G$ iff $G'$ is $3$-colorable.

proof. Suppose $v_1,...,v_i$ is extendable to the entire graph $G$. Then uncolored vertices in $G$ have a valid assignment of colors. If we construct $G'$, then all uncolored vertices are still adjacent to the same set of colors, so the coloring is still valid, hence $G'$ is $3$-colorable. Suppose $G'$ is $3$-colorable. Then if we undo our construction, we can still color the uncolored vertices since they will be adjacent to the same colors as in $G'$.

Thus we can simply construct $G'$ and call the oracle on it. If the oracle returns yes, then we fix $c$ as the color assigned to $v_i$. Otherwise we move to the next valid color in $C_i$ and do the same. Note that for some color in $c\in C_i$, the assignment of $c$ to $v_i$ must be a valid assignment for a $3$-coloring over the entire graph $G$, since we know that the coloring over $v_1,...,v_{i-1}$ is extendable to the entire graph $G$ and we know that $G$ is $3$-colorable to begin with.

This informal walkthrough demonstrates an example of self-reducibility. In this case we call the oracle $O(n)$ times and the construction of $G'$ can be done in polynomial time. Pretty neat!