A Dynamic Programming Approach for the Max-Min Cycle Packing Problem in Even Graphs

Peter  Recht

doi:10.4236/ojdm.2016.64027

Peter Recht

Abstract: Let

be an undirected graph. The maximum cycle packing problem in G then is to find a collection

of edge-disjoint cycles C_{iin G such that s is maximum. In general, the maximum cycle packing problem is NP-hard. In this paper, it is shown for even graphs that if such a collection satisfies the condition that it minimizes the quantityon the set of all edge-disjoint cycle collections, then it is a maximum cycle packing. The paper shows that the determination of such a packing can be solved by a dynamic programming approach. For its solution, an-shortest path procedure on an appropriate acyclic networkis presented. It uses a particular monotonous node potential.}

Keywords: Maximum Edge-Disjoint Cycle Packing, Extremal Problems in Graph Theory, Dynamic Programming, -Shortest Path Procedure

Cite this paper: Recht, P. (2016) A Dynamic Programming Approach for the Max-Min Cycle Packing Problem in Even Graphs. Open Journal of Discrete Mathematics, 6, 340-350. doi: 10.4236/ojdm.2016.64027.

References

[1] Harant, J., Rautenbach, D., Recht, P., Schiermeyer, I. and Sprengel, E.-M. (2010) Packing Disjoint Cycles over Vertex Cuts. Discrete Mathematics, 310, 1974-1978.
http://dx.doi.org/10.1016/j.disc.2010.03.009

[2] Antonakopulos, S. and Zhang, L. (2011) Approximation Algorithms for Grooming in Optical Network Design. Theoretical Computer Science, 412, 3783-3751.

[3] Bafna, V. and Pevzner, P.A. (1996) Genome Rearrangement and Sorting by Reversals. SIAM Journal on Computing, 25, 272-289.
http://dx.doi.org/10.1137/S0097539793250627

[4] Fertin, G., Labarre, A., Rusu, I., Tannier, é. and Vialette, S. (2009) Combinatorics of Genome Rearrangement. MIT Press, Cambridge.
http://dx.doi.org/10.7551/mitpress/9780262062824.001.0001

[5] Kececioglu, J. and Sankoff, D. (1997) Exact and Approximation Algorithms for Sorting by Reversals with Application to Genome Rearrangement. Algorithmica, 13, 180-210.
http://dx.doi.org/10.1007/BF01188586

[6] Caprara, A. (1999) Sorting Permutations by Reversals and Eulerian Cycle Decompositions. SIAM Journal on Discrete Mathematics, 12, 91-110.

[7] Caprara, A., Panconesi, A. and Rizzi, R. (2003) Packing Cycles in Undirected Graphs. Journal of Algorithms, 48, 239-256.
http://dx.doi.org/10.1016/S0196-6774(03)00052-X

[8] Krivelevich, M., Nutov, Z., Salvatpour, M.R., Yuster, J. and Yuster, R. (2007) Approximation Algorithms and Hardness Results for Cycle Packing Problems. ACM Transactions on Algorithms, 3, Article No. 48.

[9] Harant, J., Rautenbach, D., Recht, P. and Regen, F. (2010.) Packing Edge-Disjoint Cycles in Graphs and the Cyclomatic Number. Discrete Mathematics, 310, 1456-1462,
http://dx.doi.org/10.1016/j.disc.2009.07.017

[10] Recht, P. and Sprengel, E.-M. (2015) Maximum Cycle Packing in Eulerian Graphs Using Local Traces. Discussiones Mathematicae Graph Theory, 35, 121-132.
http://dx.doi.org/10.7151/dmgt.1785

[11] Ore, O. (1951) A Problem Regarding the Tracing of Graphs. Elemente der Mathematik, 6, 49-53.

[12] Baebler, F. (1953) über eine spezielle Klasse Euler'scher Graphen. Commentarii Mathematici Helvetici, 27, 81-100.
http://dx.doi.org/10.1007/BF02564555

[13] Recht, P. and Stehling, S. (2014) On Maximum Cycle Packings in Polyhedral Graphs. Electronic Journal of Graph Theory and Applications, 2, 18-31.
http://dx.doi.org/10.5614/ejgta.2014.2.1.2

[14] Hart, P.E., Nilsson, N. and Raphael, B. (1968) A Formal Basis for the Heuristic Determination of Minimum Cost Paths. IEEE Transactions on Systems Science and Cybernetics, 4, 100-107.
http://dx.doi.org/10.1109/TSSC.1968.300136

[15] Karger, D., Motwani, R. and Ramkumar, G.D.S. (1997) On Approximating the Longest Path in a Graph. Algorithmica, 18, 82-98.
http://dx.doi.org/10.1007/BF02523689