1
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$ Mar 27, 2013 at 20:47
  • $\begingroup$ 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?" $\endgroup$
    – Fran
    Mar 27, 2013 at 23:12
  • $\begingroup$ mathoverflow.net/questions/123111/number-of-graphs-with-a-cycle $\endgroup$ Mar 28, 2013 at 8:20
  • $\begingroup$ 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. $\endgroup$
    – Fran
    Mar 28, 2013 at 10:00

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.