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 ?
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3823 |
3 | Benq | 3738 |
4 | Radewoosh | 3633 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3390 |
10 | gamegame | 3386 |
# | User | Contrib. |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | maomao90 | 162 |
4 | atcoder_official | 161 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 156 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
9 | nor | 153 |
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 ?
Name |
---|
By overlapping cycles do you mean 2 cycles that share at least 1 edge? or share at least 1 vertex?
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.
What if the number of the nodes are not multiple of 3 ? I just showed n=6 as an example, n can be anything.
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.
Ok, thanks for the reply :)