Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Suppose you are given two graphs $G$ and $H$ and are told that one of the following two situations occurs. Either they are isomorphic, or one of the graphs contains a Hamilton cycle and the other doesn't. Can you tell in polynomial time which situation you are in? Obviously you can if graph isomorphism is easy or if finding Hamilton cycles is easy, so let's assume that they are both hard.

There may be a trivial answer, but it seems to me that the question is not obviously as hard as graph isomorphism, since if you can always solve it, it isn't clear that you can modify the algorithm to tell whether an arbitrary pair of graphs is isomorphic. If there isn't a trivial answer, then my guess is that the question is more or less as hard as resolving the P versus NP problem or the graph isomorphism problem, but maybe it isn't, since you're allowed to assume answers to those problems. Anyhow, the question has just occurred to me and I haven't yet found a reason not to like it, so here it is.

share|improve this question
    
A quick remark: one can of course ask the same question for many other NP-complete problems -- I'd be just as interested, for example, in the same question but with "clique of size m" instead of "Hamilton cycle". –  gowers Sep 5 '12 at 23:02
    
You have heard of how to convince someone you have a proof without showing it to them? (Assume reputation is not a consideration.) Look up zero knowledge proofs. Or have you already, and is there something you aren't telling us? Gerhard "I'm Sure It's The Latter" Paseman, 2012.09.05 –  Gerhard Paseman Sep 5 '12 at 23:20
    
By the way, it is not known whether the graph isomorphism problem is NP-complete. –  Richard Stanley Sep 6 '12 at 0:23
4  
@Gerhard "I'm sure it's the latter" Paseman, it's only half the latter. I know what zero-knowledge proofs are, but don't immediately see how they answer the question. Could you spell it out? –  gowers Sep 6 '12 at 6:43
3  
@Suvrit, if you were to take two typical hard instances for the Hamilton cycle problem, one that contains a Hamilton cycle and one that doesn't, then it is very likely that it will be easy to tell that they are non-isomorphic. (For example, their degree sequences are likely to differ.) In the other direction, if you have two graphs of large minimal degree that are a difficult case for graph isomorphism, they will both contain Hamilton cycles. I'm not sure whether this is answering your question though. –  gowers Sep 6 '12 at 8:35

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.