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... :-)
No comments:
Post a Comment