2
$\begingroup$

Given the following definition of Careful 5COLORING:

A 5-coloring is careful if the colors assigned to adjacent vertices are not only distinct, but differ by more than 1(mod 5)

how would a reasonable reduction to prove NP hardness work? Suggestion is to reduce from standard 5COLOR, but I am not able to find a correct one.

I have tried reducing from an instance $G$ of the standard 5COLOR as suggested creating one extra vertex between every edge in $G$. That is, let $\{u,v\}$ be an edge in $G$, create a new vertex $w$ and add edges $\{u,w\}$ and $\{w,v\}$. Fix the color of every new vertex to the same color, for example 3. This results in a new graph $H$.

When proving "$G$ is 5COLORABLE iff $H$ is carefully 5COLORABLE", I can prove the first $G$ is 5COLORABLE $\rightarrow$ $H$ is carefully 5COLORABLE since $H$ actually requires only 3 colors (if every new vertex is colored as 3, I only need colors 1 and 5 for the original vertexes in $G$).

On the other hand, the proof doesn't work since there are instances where $G$ isn't 5COLORABLE but $H$ is carefully 5COLORABLE. This has led me to believe my reduction is wrong.

$\endgroup$
2
$\begingroup$

There is a dichotomy theorem that covers this. For a graph $H$, let $P_H$ be the following problem: On input of graph $G$, decide whether there is a homomorphism from $G$ to $H$. A homomorphism is a function that maps vertices of $G$ to vertices of $H$ in such a way that edges of $G$ are mapped to edges of $H$.

Observe how $5$-colouring is $P_{K_5}$, where $K_5$ is the complete graph with $5$ vertices: The only constraint for a homomorphism to $K_5$ is that the endpoints of edges are mapped to different vertices. Furthermore, careful $5$-colouring is $P_{C_5}$, where $C_5$ is a cycle of length $5$. (To see how that works out, let the vertices of said cycle be in the order $0,2,4,1,3$.)

Now the theorem states that:

  1. If $H$ is bipartite, then $P_H$ is in PTIME.
  2. If $H$ is not bipartite, then $P_H$ is NP-complete.

If you still want a reduction from $5$-colouring, I suggest to look for a suitable gadget. The gadget should be a graph $I$ with two special vertices $v$ and $w$, such that

  1. There is no careful $5$-colouring of $I$ that assigns the same colour to $v$ and $w$.
  2. For all colours $c$ and $d$ such that $c\not=d$, there is a careful $5$-colouring of $I$ that assigns $c$ to $v$ and $d$ to $w$.

Then, for a reduction you would replace every edge with a copy of $I$.

[EDIT]

Wikipedia has the following reference for the dichotomy theorem:

Hell, Pavol; Nešetřil, Jaroslav (1990), "On the complexity of H-coloring", Journal of Combinatorial Theory Series B, 48 (1): 92–110

$\endgroup$
  • $\begingroup$ Can you give a reference for the dichotomy theorem? $\endgroup$ – Yuval Filmus Jun 30 '18 at 6:30
  • $\begingroup$ Perhaps the author refers to the Feder-Vardi CSP conjecture? The Dichotomy Conjecture $\endgroup$ – Pål GD Jun 30 '18 at 7:28
  • $\begingroup$ The theorem is a special case where the CSP dichotomy conjecture has been proven. I'm sorry that I don't know the author. I tend to forget who proved what unless I met the people in person. $\endgroup$ – kne Jun 30 '18 at 8:45
  • $\begingroup$ The conjecture is now proven apparently, but you might need to do some work to deduce the condition of bipartiteness in this special case. $\endgroup$ – Yuval Filmus Jun 30 '18 at 14:24
  • $\begingroup$ @Yuval Filmus: Oh, do you happen to have a pointer to the proof of the CSP conjecture? $\endgroup$ – kne Jun 30 '18 at 21:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.