3
$\begingroup$

Consider to following decision problem:

Input: Undirected graph $G=(V,E)$

Question: Is the minimum numbers of colors needed to color the vertices (such that every two adjacent vertices aren't colored the same) exactly 2015?

Note that 2015 could be any fixed number. This number is not part of the input.

I need to understand what is the minimal complexity class that contain this problem, between $\sf P,NP,coNP,NP\cup coNP,\Sigma _{2} \cap \Pi _{2}, \Sigma _{2} \cup \Pi _{2}$.

I don't it's $\sf NP$ or $\sf coNP$ since I can't think of a verifier for both the language or it's complement. The problem is maybe in $\sf \Sigma _{2} \cap \Pi {2}$ since we can think of it as

exists $f$ some 2009-coloring function, for-all $g$, 2008-coloring function, $f$ is a correct coloring and $g$ isn't a correct coloring.

So by the above, it seems that the language is in $\sf \Sigma _{2}$, but the quantifiers order doesn't really matter here, so the language is also in $\sf \Pi _{2}$, I think.

And maybe the there is some deterministic polynomial-time algorithm?

$\endgroup$
  • $\begingroup$ That problem is in DP. ​ ​ $\endgroup$ – user12859 Jan 10 '16 at 12:31
3
$\begingroup$

The problem is always in $\Delta_2 = \Sigma_2 \cap \Pi_2$, as you mention. For some values of 2015 it is easier: deciding whether a graph has chromatic number 3 is NP-complete, and deciding whether a graph has chromatic number 2 or 1 is in P (since you can check whether a graph is bipartite in polytime).

Since deciding whether a graph has chromatic number 3 is NP-hard, so is deciding whether it has chromatic number 2015, by reduction: add a clique of size 2012, and connect it to all vertices; this increases the chromatic number by exactly 2012. So there is no hope for a polynomial time algorithm.

$\endgroup$

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.