2
$\begingroup$

I'm trying to create an algorithm in polynomial time, that detects wether or not a graph is in a language.

The language specifies that a graph is only part of this language if it has a cycle on 40 vertices. (The cycle doesn't need to be induced.)

Now, I'm considering the fact that there could be a huge number of vertices within this graph. For example, we could have 100000 vertices, and there could be a cycle of 300, but this would not be in the language. If this graph had a cycle of 300 AND a cycle of 40, then it is.

I'm thinking that depth-first search would be the proper way to approach this question. Then, using this, we'd possibly have check every vertex within the graph?

This is just a guess at the moment though, and help/thoughts would be greatly appreciated.

Improve this question
$\endgroup$
1
  • $\begingroup$ Is your graph directed or undirected? Are you looking for a simple cycle (no repeated vertices) or are you OK with allowing vertices to repeat (a walk that ends where it starts)? $\endgroup$
    – D.W. ♦
    Mar 9, 2015 at 3:17

3 Answers 3

Reset to default
3
$\begingroup$

When you say "cycle", do you mean a simple cycle of length 40 (so no vertex is allowed to be repeated), or would you allow an arbitrary walk of length 40 that ends where it starts (i.e., vertices are allowed to be repeated in the cycle)? The answer to your question depends on what you mean by cycle, so I'll answer both cases.

Simple cycles

The problem of testing whether a graph contains a simple cycle of length $k$ is hard.

No efficient algorithm is known; all known algorithms have running time that is exponential in $k$; and if $k$ is part of the input, the problem is NP-hard. See here and here. In your case, $k=40$. The best algorithms that I know of have either a $O(k!)$ factor or a $O(n^{k/2})$ factor in the running time, so they will be totally infeasible: $O(n^{20})$ is not feasible for any non-trivial value of $n$, and $k! \approx 2^{159} \approx 10^{48}$, which is also infeasibly large. (See Louis's answer for pointers to an algorithm of the former type.)

If you allow repeated vertices

If you allow the cycle to contain repeated vertices, then the problem becomes much easier, and there is a polynomial-time solution.

Hint: Consider the adjacency matrix of the graph, $M$. Look at $M^2$. Can you find any relationship between the $i,j$ entry of $M^2$ and paths of some length? Can you generalize?

(Since this looks like a natural exercise problem, I am just giving you a hint, and letting you take it from here.)

Improve this answer
$\endgroup$
6
  • 1
    $\begingroup$ The meaning of "cycle" in graph theory is well-defined and completely standard: a cycle has no repeated vertices. Every graph with at least one edge contains a closed walk of length 40. That makes the "If you allow repeated vertices" section so silly that you really ought to delete it. $\endgroup$
    – David Richerby
    Mar 9, 2015 at 8:07
  • $\begingroup$ @DavidRicherby I'm not certain if everybody uses these terms with the same precision. I seem to remember some sources which distinguish 'cycles' and 'simple cycles', but never use the word 'walk'. (Be especially mindful of material in other languages and from other academic cultures. There are more definitions of graphs et al. around that healthy for your mind...) $\endgroup$
    – Raphael ♦
    Mar 9, 2015 at 8:46
  • 1
    $\begingroup$ @Raphael OK, I can see situations in which cycles might have repeated vertices, but certainly not the repeated edges that come from powering the adjacency matrix. Nobody uses the term "40-cycle" to mean "thing that might just be an edge." $\endgroup$
    – David Richerby
    Mar 9, 2015 at 9:03
  • 1
    $\begingroup$ I've never seen "cycle" used to mean "any closed walk". The reason people use "simple cycle" is usually to distinguish between (algebraic) elements of the cycle space and graph theoretic cycles. $\endgroup$
    – Louis
    Mar 9, 2015 at 12:39
  • $\begingroup$ I agree that experts don't normally use the word "cycle" to allow repeated vertices. But non-experts sometimes would actually be OK with a "closed walk containing repeated vertices" (e.g., they'd be OK with a 20-cycle that is traced twice), and just haven't considered that possibility explicitly until it is raised. (@DavidRicherby) $\endgroup$
    – D.W. ♦
    Mar 9, 2015 at 15:31
2
$\begingroup$

It's worth noting that, as D.W. hints at, the running time of the best algorithms for even cycles has a form like $O(k!V^2)$ which is a lot better than $O(V^k)$ for small $k$. A relevant references is Finding even cycles even faster by Yuster and Zwick.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I think this is more of a comment to DW's answer than a standalone answer, isn't it? $\endgroup$
    – Raphael ♦
    Mar 9, 2015 at 8:43
  • 1
    $\begingroup$ No, since the references and ideas therein are totally different. $\endgroup$
    – Louis
    Mar 9, 2015 at 8:46
1
$\begingroup$

Since 40 is a constant, there is a very simple polynomial time algorithm that just goes over all possible cycles of length 40, and for each of them, tests whether it is in the graph. There are $O(n^{40})$ cycles, and testing whether each of them is in the graph takes $O(1)$ (or slightly more, depending on your machine model), for a total running time $O(n^{40})$. Although this algorithm is quite slow, it still counts as polynomial time. This shows one discrepancy between the concept of polynomial time and our intuitive notion of efficient computation, a notion that the concept was originally trying to model.

Improve this answer
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.