2
$\begingroup$

G is a planar graph with n nodes.
What are the complexity of following problems?

1-A: Does G contain an m-cycle? (m-cycle is a simple cycle with m nodes, m< n)
2-B: complexity of counting all m-cycles in G, (Complexity of #A).

3- what is the complexity of A and B if G is an arbitrary given graph?

Pointing to books and papers is also useful...

$\endgroup$
13
  • 6
    $\begingroup$ For 1, since by adding one node to G and letting $m=n-1$ we have reduced to the Hamiltonian cycle problem, it is NP-hard in general. For $m$ is a fixed constant, see my questions on MathOverflow: mathoverflow.net/questions/16393/…, mathoverflow.net/questions/35560/… $\endgroup$ Dec 5, 2010 at 10:37
  • 3
    $\begingroup$ What problem are you working on? Why is this question relevant? What do you already know? (For example: You should have said that problem 1 is NP-hard when $m=n-1$ but clearly in P when $m=O(1)$. Otherwise, we're led to believe that you haven't thought about the problem at all.) What have you tried? $\endgroup$
    – Jeffε
    Dec 5, 2010 at 17:02
  • 2
    $\begingroup$ @marjoonjan, the commenters are merely trying to help you craft a better question. Your original question should have described the set of results that are already known (m = n-1, constant, or even), and then focused on the range of values of m that you care about for your application. Given the comments, it is really your job to now explain why the question remains interesting, because Hsien-Chih's answer already captures many interesting cases. Explaining your original motivation might also help because it's possible that this isn't even the right question. $\endgroup$ Dec 5, 2010 at 19:30
  • 2
    $\begingroup$ @marjoonjan: While your questions can be answered as a [reference-request] problem in your current presentation, however, we want to help more!! Maybe you think that the community is strict and want you to provide lots of background information which you may not think it is needed. But that will take you a lot of time surveying all the literatures we provided (and maybe there is too much so we do not know how to start). Maybe after explaining some of your motivations, we can concentrate on what you really need, and answer you questions more precisely and accurately. Help us to help you!! :) $\endgroup$ Dec 6, 2010 at 0:55
  • 2
    $\begingroup$ @marjonnan: If you want to get help from this community, you need to make a good faith effort to convince us that you're not just asking us to do your work for you. Please meet us halfway. $\endgroup$
    – Jeffε
    Dec 6, 2010 at 2:01

1 Answer 1

2
$\begingroup$

Perhaps this paper which deals with cycle lengths in planar graphs might be of value:

Li, Ming-Chu; Corneil, Derek G.; Mendelsohn, Eric (2000), "Pancyclicity and NP-completeness in planar graphs", Discrete Applied Mathematics 98 (3): 219–225.

$\endgroup$

Your Answer

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

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