Блог пользователя zephyr_23

Graph problem.
Автор zephyr_23, история, 7 лет назад, По-английски

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 ?

  • Проголосовать: нравится
  • +21
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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

→ Ответить
»
7 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      7 лет назад, # ^ |
      ← Rev. 3   Проголосовать: нравится +8 Проголосовать: не нравится

      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.

      → Ответить