2
$\begingroup$

I have a graph named $G$. degree of each node in $G$ is at most $10$. I need to find an algorithm to determine that this graph has any cycle with length less than $20$ with $O(n)$ .

I think it can solve with any theorem related to $Δ(G)$ and cycle in $G$ (but I'm not sure) .

I search it in google and stackoverflow , but I can't find any solution.

  • 0
    Is this homework?2012-04-02
  • 0
    no. it's not homework.2012-04-02
  • 2
    Re-tagged: [tag:graph] refers to [graphs of functions](http://en.wikipedia.org/wiki/Graph_of_a_function) and not to discrete graphs - please, read the tag wiki when you tag.2012-04-02
  • 0
    thaks . I will read tag wiki next time.2012-04-02
  • 0
    Your question in SO was very poor written, Also it doesn't show any effort, so It was not qualified for it, because of that removed, see my [meta question](http://meta.stackexchange.com/questions/127910/why-was-this-question-removed-from-stack-overflow) about it.2012-04-02
  • 0
    @Saeed thanks for your help. I am newbie here and a bit nonfamiliar with these kind of sites. I swear to improve :)2012-04-03

2 Answers 2

2

There are $O(n)$ vertices in $G$, each of which can be an endpoint of at most $10^1+10^2+10^3+\cdots+10^{19}=O(1)$ walks of lengths between $1$ and $19$.

Hence, brute-force checking all of these $O(n)$ walks (e.g. via depth-first search or breadth-first search) will run in $O(n)$ time (albeit with a horribly large implicit constant).

0

The algorithm for finding a short cycle is BFS. The reason why this has runtime $\mathcal{O}(n)$ in your case is the degree bound on the vertices, which yields that $m\le 5n$.

  • 0
    for finding girth of a graph we need to run BFS for any vertex . then for this it has O(n^2)2012-04-02
  • 0
    You do not need to run BFS at any of the vertices that you already visited in a previous run. If you ran BFS at a vertex and found no circuit, you have found a connected component without circuit and you can ignore it for the rest of the algorithm.2012-04-02
  • 0
    And by ignoring _it_, I mean you can ignore the entire component, of course.2012-04-02
  • 0
    and if we have a cycle bigger than 19 , how can we ignor this component ?2012-04-02
  • 0
    http://webcourse.cs.technion.ac.il/234247/Winter2003-2004/ho/WCFiles/Girth.pdf2012-04-02
  • 0
    -1 this isn't an answer, question asked for small loops not general loop finding algorithm.2012-04-02
  • 0
    @Saeed: This is a perfectly valid answer. For each vertex, determining if it is part of a cycle of length $\le 20$ requires looking at no more than $10 + 10^2 + 10^3 + \dots + 10^{20} = O(1)$ vertices! Hence, using BFS and truncating when we go past $20$ vertices will give an $O(n)$ algorithm. Of course, rattle gave a different reason as to why this is $O(n)$: he did so by counting the number of edges, which you only visit a constant number of times.2012-04-02
  • 0
    @Aryabhata, What you said is not same as what rattle said. Also in my opinion your suggestion is not interesting($O(10^{21} \cdot n)$ really not beautiful). P.S: your suggestion is like Douglas S. Stones's suggestion.2012-04-02
  • 0
    @Saeed: I am not suggesting anything. All I am saying is this answer does not deserve a downvote. Of course, you are free to vote as you please.2012-04-02