Cheap and Secure Web Hosting Provider : See Now

Euler graph k-coloring (np-completeness proof)

, , No Comments
Problem Detail: 

I've been studying np-completeness proofs by reduction, and was wondering whether my approach to the following problem is viable.

Define an Euler graph as a graph that 1) is connected, and 2) has every vertex with even degree.

Input: An Euler graph and an integer $k$. Problem: is the given graph $k-colorable$?

Show that the above is NP-complete.

My attempt: The problem is in NP since, given some solution "certificate" consisting of $k$ sets of vertices (where all vertices in a set are assigned the same colors), the solution can be verified in polynomial time: Just go thru each vertex and ensure that none of its neighboring vertices are contained in the same set as that vertex. Since a vertex can have at most $n - 1$ neighbors (where $n = |V|$), this should take asymtotically $O(n^2)$ time.

Reduction: reduce the general $k-coloring$ (chromatic number) problem (which is known to be NP complete). Here is where I run into some questions...

My initial thinking was that, given an instance of the general $k-coloring$ problem, with a graph $G$ and an integer $k$, we can construct $G'$ and $k'$ by adding a single vertex to $G$, and connecting that vertex to every odd vertex in $G$, while letting $k' = k$. But then I saw this wouldn't work for a 2-vertex tree graph. Letting $k' = k + 1$ is no good either, because this wouldn't work for the graph consisting of the shape of a square with a diagonal segment added to it.

So now I'm thinking, why not just locate every pair of odd-degree vertices in $G$ and connect each pair with a single edge, while letting $k' = k$? Would this reduction work, or are there still cases where this wouldn't work?

Asked By : user3280193

Answered By : Yuval Filmus

A major part of proving that a problem is NP-hard by reduction is proving that the reduction works. It's not enough to find some procedure which takes an instance of problem A and transforms it to an instance of problem B; you have to figure out the connection betweens solutions of the one instances and solutions of the other.

In your case, one idea that does work pairs up odd-degree vertices and connects every pair to a new vertex. Now all the degrees are even, and the new graph is $k$-colorable iff the old one is $k$-colorable, assuming $k > 2$. I'll let you figure out why this works.

While this idea is similar to your own idea of connected pairs of odd-degree vertices, your idea is problematic since it is not clear that if the original graph is $k$-colorable then so is the new graph. Indeed, if two vertices that you connected were colored using the same color then you cannot use the same coloring for the new graph. The idea described in the previous paragraph is very similar but doesn't suffer from this shortcoming.

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback