zephyr_23's blog

Graph problem.
By zephyr_23, history, 6 years ago, In English

Given a connected, undirected graph, find maximum number of non overlapping cycles ?

Example:-

Here in the above example we can have 2 (maximum number) non overlapping cycles, 0-1-2 and 4-5-6.

Any idea of how to solve this problem efficiently ?

  • Vote: I like it
  • +21
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
6 years ago, # |
  Vote: I like it +6 Vote: I do not like it

By overlapping cycles do you mean 2 cycles that share at least 1 edge? or share at least 1 vertex?

→ Reply
»
6 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Surely, for a graph with 3N nodes, the best one can ever do is N 3-cycles. Checking whether this is possible is the same as partitioning the graph into N disjoint triangles. As stated here, this is NP-Complete.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    What if the number of the nodes are not multiple of 3 ? I just showed n=6 as an example, n can be anything.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 3   Vote: I like it +8 Vote: I do not like it

      Well, you asked for a solution that works for all N. I've stated that there are some N (in particular, multiples of 3) for which the problem reduces to something which is known to be NP-complete, so the whole problem (in its full generality) can't be any easier than NP-complete.

      Edit: For the record, if N = 1/2 (mod 3), consider a graph G with 1/2 isolated nodes and an arbitrary subgraph G' induced by the other N' = 0 (mod 3) nodes. Then the problem once again reduces to finding a triangle partition of G'.

      Note that this G is not connected, this can be easily fixed by adding arbitrary edges from the isolated nodes to some nodes in G' such that the extra nodes now have degree 1.

      → Reply