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

I have an algorithm that receives a labeled graph on n vertices and a number k as input and proceeds by checking whether the cycles of length less than k are contained in the graph. A cycle in this context is a closed path where each vertex is only allowed to appear once.

For a given k, I'm interested in how often I can expect to not find all cycles there are so that I'm able to get a better feeling for the cost-value ratio of k - the computations get more and more costly with rising k (which is no surprise, given that finding a hamilton cycle is NP-hard).

Checking each cycle is not an option - the algorithm is supposed to be used with k strict less than n and I want to know whether its worth it to increase k by a certain amount. So I'd like to know how big the propability is that an input graph contains a cycle of length at least k - given that every graph on n vertices is equally likely to be the input.

Equally, I'm interested in the number of labelled graphs on n vertices that contain a cycle of length at least k. Are there any explicit formulas or results in general for this?

share|improve this question
    
Do you mean a cordless cycle or merely a path with no repeats until the end? Although it is hard to say if a particular graph has a Hamilton cycle, it might be easy most of the time (sparse enough? probably not and you can easily find an obstacle. dense enough? quite likely that you will find one quickly) For "large enough" $c$ and $cn\log{n}$ edges the probability of such a cycle goes to 1 as n increase. With every graph equally likely you would have roughly $n^4/4$ edges on average and be extremely likely to have cycles of all lengths. Are you thinking of $k$ close to $n$ or much smaller? –  Aaron Meyerowitz Mar 27 '13 at 20:47
    
Although I'm not sure what a cordless cycle is, I'm interested in cycles as closed paths where each vertex can appear once at most. I also know about some of the asymptotic tendencies like the ones you describe but i really want to know the exact numbers involved. I'd like to be able to answer questions like "For given n and propability p, how big has k to be in order that the algorithm succeeds in finding every cycle with propability at least p?" –  Fran Mar 27 '13 at 23:12
    
    
thank you. so i guess this is an open problem? I'll have a look at the references given there. still, if there is some literature on the subject, I'd be grateful to look into it. –  Fran Mar 28 '13 at 10:00
add comment

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

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.