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.
What can we say about all cycles in graphs (connected undirected graph)
cc.complexity theory;graph theory;graph algorithms