4
$\begingroup$

The discussion at Decision problem restricted to inputs that satisfy some necessary condition. got me thinking about specific promises on a graph that would reduce the complexity of the coloring problem from NP-complete to some (presumably) tighter class; in particular, are there any classes of graphs $G$ for which the 3-coloring question (can a given $g \in G$ be 3-colored?) is reducible to Graph Isomorphism? This seems like the natural intermediate complexity class for the problem, but at least a quick web survey didn't show any related results.

Editing to make the question more concrete: To try and maintain some non-triviality, is there some 'reasonably definable' set of graphs $G$ such that three-colorability of graphs in $G$ is equivalent (mutually reducible) to GI? My first inclination was to define 'reasonable' as 'first-order with quantifiers ranging over individual graphs' (and of course, edge and vertex quantifiers 'within' those graphs, presumably even second-order quantifiers over sets of verts and edges), but from doing some web scouring it's not even clear that many nice and even relevant properties like planarity are so defineable. (Although being 3-colorable itself is, of course: ∃V0,V1,V2(∀v∈V0∀w∈V0(⟨v,w⟩∉E), etc.) ) I'm thinking of equivalence in terms of mutual oracularity; given an oracle for GI we can decide (in polynomial time) for any given graph $g\in G$ whether $g$ is 3-colorable, and contrariwise given an oracle that decides 3-colorability for any graph $g\in G$ we can decide in polynomial time any instance of GI.

Improve this question
$\endgroup$
2
  • $\begingroup$ For any complexity class inside NP one can define a promise version of any NP-hard problem that falls in that class, as pointed out in Scott's answer. Is that what you're asking? $\endgroup$
    – Rune
    Jul 12, 2010 at 20:59
  • $\begingroup$ Yes and no - in this case, we can (loosely) define a promise version, but it's not clear that we can explicitly define one - more specifically, I don't see how the construction gives a first-order definable $G$. I'll say more about this in a reply to Scott's comment below, and try to edit my question for clarity... $\endgroup$
    – Steven Stadnicki
    Jul 13, 2010 at 17:24

1 Answer 1

Reset to default
5
$\begingroup$

Hi Steven,

(1) To start with the "duh" observation, you could define an artificial class, namely "those 3-coloring instances that are obtained by starting from Graph Isomorphism and then applying a standard NP-completeness reduction." That would indeed give you a subclass of 3-coloring instances that are provably polynomially equivalent to graph isomorphism, but I'm guessing it's not what you had in mind. :-)

(2) I can't think of a "natural" subclass of 3-coloring instances that are reducible to graph isomorphism and not as a consequence of being in P. I'd be interested and surprised if there was one -- 3-coloring and GI are both about graphs, but in complexity terms they're extremely different! GI has lots of special group-theoretic structure, which in some sense can't be shared by 3-coloring (or any other NP-complete problem) unless the polynomial hierarchy collapses.

(3) On the other hand, if you're willing to talk about nonuniform algorithms (i.e., algorithms that can take "advice" depending on the input length n), then here's another "duh" observation. Suppose you have a fixed graph G on n vertices, together with a 3-coloring of G. Then you can 3-color any graph G' that happens to be isomorphic to G, provided you can compute an isomorphism between G and G'. Or if you prefer decision problems: given as advice a graph G that's 3-colorable and another graph H that isn't, and also given a decision oracle for GI, you can decide 3-colorability for those graphs that happen to be isomorphic to either G or H.

Sorry the above wasn't more helpful... :-)

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks! I should certainly have made my question more clear, particularly to eliminate issues (1) and (3) (although 3 doesn't really solve my particular question - I'm looking for an equivalency and not simply a reduction, mea culpa). Can you speak a bit more about the structure in (2)? I know that GI is self-reducible, but I presume that's not what you're talking about there. Regardless, thank you! $\endgroup$
    – Steven Stadnicki
    Jul 13, 2010 at 19:10
  • $\begingroup$ Indeed, it's not what I was talking about, since NP-complete problems are self-reducible too! Probably the most interesting property of GI that differentiates it from any known NP-complete problem, is that GI has what's called a Statistical Zero-Knowledge (SZK) proof protocol, by which a verifier can be convinced that two graphs are isomorphic (or non-isomorphic) without learning anything else about them. That's what implies that GI can't be NP-complete unless the polynomial hierarchy collapses. For more about this, google "Goldreich-Micali-Wigderson" $\endgroup$
    – Scott Aaronson
    Jul 21, 2010 at 6:27
  • $\begingroup$ Or try my lecture notes: stellar.mit.edu/S/course/6/sp08/6.080/courseMaterial/topics/… $\endgroup$
    – Scott Aaronson
    Jul 21, 2010 at 6:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .