-2
$\begingroup$

I am considering one optimization problem who is known to be NP hard in the general setting.

But there is application of this problem on the cylces of graph. This problem involves several sets and in this setting each set is the set of nodes of cycle in connected unidrected graph. And all cycles of connected unidrected graphs are the all sets for this problem. This is quite specific setting for the problem and I wonder whether there can be improvements in this specific setting.

I would like to work out all the details myself but the question is - is there the general theory of all cycles in grpahs (connected undirected). Like - what is the number of cycles, what is the minimum and maximum lenght of them, how much common nodes they can have and so on? Mybe there are connections with group theory - e.g. cycle could be some kind of orbit for a group element (in rude language). Any such information provides the constraint on the initial problem and therefore - the complexity improvements can be possible to achieve in this specific setting.

Google gives a lot about Hamiltonian and similar specific cycles. My question is about all possible cycles in graph.

Any references could be helpful. Any names for the problems and keywords in this are could be appreciated as well. Thanks.

$\endgroup$

closed as unclear what you're asking by Sasho Nikolov, Jeffε, Kaveh, R B, Ryan Williams Aug 3 '14 at 4:06

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 5
    $\begingroup$ I have no idea what a "general theory of all cycles in graphs" would mean. Can you describe a "general theory of X" for some other X? $\endgroup$ – Jeffε Jun 19 '14 at 21:28
  • $\begingroup$ As I said - I guess that my optimization problem in the undirected graph setting can have improved complexity. To investigate this and prove this it would be nice to know the maximal number of cycles in graph, how the lengths of cycles are distributed and so on. Ari answer about cycle bases seemed promising - it could be great to find some kind of generators from which other cycles can be construced and so on. All those questions forms the theory and it would be nice to have one and to have it ready for applications. But I am not sure whether such theory exists. $\endgroup$ – TomR Jun 20 '14 at 17:02
5
$\begingroup$

The cycles of a graph form a vector space with its own cycle basis of simple cycles. Is that what you mean?

$\endgroup$

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