Computer Science ›› 2017, Vol. 44 ›› Issue (1): 1-6, 31.doi: 10.11896/j.issn.1002-137X.2017.01.001

    Next Articles

Survey of Cycle Packing Problem

LUO Wei-dong, WANG Jian-xin and FENG Qi-long   

  • Online:2018-11-13 Published:2018-11-13

Abstract: Cycle packing problem was first presented by Erds and Pósa.Since then researchers have been studying the problem in graph theory and theoretical computer science.Recently,researchers find that the problem has improtant applications in computational biology,especially for reconstruction of evolutionary trees and genomic analysis.In this paper,an introduction to the research status of this problem was given.First and foremost,some results of cycle packing problem in graph theory were discussed.Then,we analyzed and discussed approximation algorithms,parameterized algorithms,parameterized complexity and inapproximability of the problem.At last,some further research directions on this problem were given.

Key words: Cycle packing,Graph theory,Approximation algorithms,Parameterized algorithms,Inapproximability,Parameterized complexity

[1] ERDS P,PSA L.On the maximal number of disjoint circuits of a graph[J].Publicationes Mathematicae Debrecen,1962(9):3-12.
[2] ERDS P,PSA L.On independent circuits contained in a g-raph[J].Canadia Journal of Mathematics,1965,17:347-352.
[3] CARPARA A,PANCONESI A,RIZZI R.Packing cycles in undirected graphs[J].Journal of Algorithms,2003,48(1):239-256.
[4] CARPARA A,PANCONESI A,RIZZI R.Packing cuts in undirected graphs[J].Networks,2004,44(1):1-11.
[5] FRANK A.Conservative weightings and ear decompositions of graphs[J].Combinatorica,1993,13(1):65-81.
[6] HOLYER I.The NP-completeness of some edge-partition problems[J].SIAM Journal on Computing,1981,10:713-717.
[7] KRIVELEVICH M,NUTOV Z,YUSTER R.Approximationalgorithms for cycle packing problems[C]∥ Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms.Vancouver,British Columbia,Canada,2005:556-561.
[8] FRIGGSTAD Z,SALAVATIPOUR M R.Approximability ofPacking Disjoint Cycles[J].Algorithmica,2010,60(2):395-400.
[9] DU Ding-zhu,GE Ke-yi,HU Xiao-dong.Design and analysis of approximation algorithms[M].Beijing:China Higher Education Press,2011.(in Chinese) 堵丁柱,葛可一,胡晓东.近似算法的设计与分析[M].北京:高等教育出版社,2011.
[10] GAREY M R,JOHONSON D S.Computers and Intractability:A Guide to the Theory of Incompleteness[M].San Francisco,1979.
[11] CAPRARA A,RIZZI R.Packing triangles in bounded degree graphs[J].Information Processing Letters,2002,84(4):175-180.
[12] RAUTENBACH D,REGEN F.On packing shortest cycles in graphs[J].Information Processing Letters,2009,109:816-821.
[13] SLIVKINS A.Parameterized tractability of edge disjoint paths on directed acyclic graphs[J].SIAM Journal on Discrete Mathematics,2010,4(1):146-157.
[14] GROHE M,GRUBER M.Parameterized Approximability of the Disjoint Cycle Problem[C]∥Automata,Languages and Programming,34th International Colloquium.Wroclaw,Poland,2007:363-374.
[15] BODLAENDER H L,JANSEN B M P,K RATSCH S.Kernel bounds for path and cycle problems[J].Theoretical Computer Science,2013,511:117-136.
[16] BODLAENDER H L,PENNINKX E,TAN R B.A Linear Kernel for the k-Disjoint Cycle Problem on Planar Graphs[C]∥ Algorithms and Computation,19th International Symposium.Gold Coast,Australia,2008:306-317.
[17] VOSS H J,JRGEN H,GRAPHEN E V.die keine k+1 knotenfremde Kreise enthalten[J].Mathematische Nachrichten,1969,40:19-25.
[18] YOUNGER D H.Graphs with interlinked directed circuits[C]∥Proceedings of the International Midwest Symposium on Circuit and Systems.1973:XVI 2.1-XVI 2.7.
[19] MCCUAIG W.Intercyclic digraphs.Graph Structure Theory[M]∥AMS Contemporary Math,1991:203-245.
[20] SEYMOUR P D.Packing Directed Circuits Fractionally[J].Combinatorica,1995,15(2):281-288.
[21] REED B,ROBERTSON N,Seymour P,et al.Packing Directed Circuits[J].Combinatorica,1996,16(4):535-554.
[22] ENOMOTO H.On the existence of disjoint cycles in a graph[J].Combinatorica,1998,18(4):487-492.
[23] WANG Hong.On the maximum number of independent cycles in a graph[J].Discrete Mathematics,1999,205(1-3):183-190.
[24] 王建新,冯启龙.参数计算导论[M].长沙:科学出版社,2014.
[25] EGAWA Y,HAGITA M, KAWARABAYASHI K,et al.Cove-ring vertices of a graph by k disjoint cycles[J].Discrete Mathematics,2003,270(1-3):114-124.
[26] EGAWA Y,FUJITA S,KAWARABAYASHI K,et al.Exis-tence of two disjoint long cycles in graphs[J].Discrete Mathematics,2005,305(1-3):154-169.
[27] BRANDT S,CHEN G,FAUDREE R,et al.Degree conditions for 2-factors[J].Journal of Graph Theory,1997,24(2):165-173.
[28] ENOMOTO H,LI H.Partition of a graph into cycles and degene-rated cycles[J].Discrete Mathematics,2004,276(1-3):177-181.
[29] KAWARABAYASHI K.Degree sum conditions and graphswhich are not covered by k cycles[J].Discrete Mathematics,2008,308:1620-1627.
[30] HU Zhi-quan,LI Hao.Weak cycle partition involving degreesum conditions[J].Discrete Mathematics,2009,309(4):647-654.
[31] FUJITA S.Degree conditions for the partition of a graph intocycles,edges and isolated vertices[J].Discrete Mathematics,2009,309(11):3534-3540.
[32] FUJITA S.Recent Results on Disjoint Cycles in Graphs[J].Electronic Notes in Discrete Mathematics,2005,2:409-412.
[33] PONTECORVI M,WOLLAN P.Disjoint cycles intersecting aset of vertices[J].Jounal of Combinatrias Theory,Series B,2012,102(5):1134-1141.
[34] KAWARABAYASHI K,KRL D,KRCl M,et al.Packing directed cycles through a specified vertex set[C]∥ Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms.New Orleans,Louisiana,USA,2013:365-377.
[35] REED B,SHEPHERD B.The Gallai-Younger conjecture forplanar graphs[J].Combinatorica,1996,16:555-566.
[36] KAKIMURA N,KAWARABAYASHI K,MARX D.Packingcycles through prescribed vertices[J].Journal of Combinational Theory,2011,1(5):378-381.
[37] KAKIMURA N,KAWARABAYASHI K.Packing Directed Circuits through Prescribed Vertices Bounded Fractionally[J].SIAM Jounal of Discrete Mathematics,2012,6(3):1121-1133.
[38] CORRDI K,HAJNAL A.On the maximal number of inde-pendent circuits in a graph[J].Acta Mathematics,1963,14:423-443.
[39] CHIBA S,FUJITA S,KAWARABAYASHI K,et al.DisjointEven Cycles Packing[J].Electronic Notes in Discrete Mathematics,2009,34:113-119.
[40] JUSTESEN P.On independent circuits in nite graphs and a conjecture of Erds and Pósa[J].Annals of Discrete Mathematics,1989,41:299-306.
[41] WANG Hong.Independent cycles with limited size in a graph[J].Graphs and Combinatorial,1994,10:271-281.
[42] GEELEN J,GERARDS B,REED B,et al.On the odd-minor variant of Hadwiger’s conjecture[J].Journal of Combinatorial Theory,Series B,2009,99:20-29.
[43] METZLAR A,MURTY U S R.Disjoint Circuits in Planar Digraphs[J].Journal of Combinatorial,Theory Series B,1993,57(2):228-238.
[44] KANN V.Maximum bounded 3-dimensional matching is MAX SNP-complete[J].Information Processing Letters,1991,37:27-35.
[45] AUSIELLO G,CRESCENZI P,Gambosi G,et al.Combinatorial Optimization Problems and Their Approximability Properties[M].Berlin:Springer,1999.
[46] HURKENS C A J,SCHRIJVER A.On the size of systems of sets every t,of which have an SDR,with an application to the worstcase ratio of heuristics for packing problems[J].SIAM Journal on Discrete Mathematics,1989,2(1):68-72.
[47] EIMABROUK N.Genome Rearrangement by Reversals and Insertions/Deletions of Contiguous Segments[C]∥ Combinatorial Pattern Matching,11th Annual Symposium.Montreal,Canada,2000:222-234.
[48] BAFNA V,PEVZNER P A.Genome Rearrangements and Sorting by Reversals[J].SIAM Journal on Computing,1996,25(2):272-289.
[49] SHAO Ming-fu,LIN Yu.Approximating the edit distance for genomes with duplicate genes under DCJ,insertion and deletion[J].BMC Bioinformatics,2012,13(S-19):S13.
[50] SHAO Ming-fu,LIN Yu,BERNARD M.An Exact Algorithm to Compute the DCJ Distance for Genomes with Duplicate Genes[C]∥ Research in Computational Molecular Biology 19th Annual International Conference.Pittsburgh,PA,USA,2014:280-292.
[51] CHEN Xin,ZHENG Jie,FU Zheng,et al.Assignment of ortho-logous genes via genome rearrangement[J].IEEE/ACM Tran-sactions on Computational Biology Bioinformatics,2005,2(4):302-315.
[52] LI Shao-hua,WANG Jian-xin,FENG Qi-long,et al.Kerneliza-tion techniques and its application to parameterized computation[J].Journal of Software,2009,0(9):2307-2319.(in Chinese) 李绍华,王建新,冯启龙,等.参数计算中核心化计算及其应用的研究进展[J].软件学报,2009,0(9):2307-2319.
[53] ZHOU Xing,PENG Wei.Several techniques used in paramete-rized computation[J].Computer Science,2014,41(6A):18-23.(in Chinese) 周星,彭伟.参数计算中使用的若干技术[J].计算机科学,2014,41(6A):18-23.
[54] LU Sheng-guo,LI Shuang,ZHU Jian-guo,et al.Survey of genome rearrangements[J].China Biotechnology,2013,30(7):108-111.(in Chinese) 卢胜国,李霜,朱建国,等.基因组重排技术应用及进展[J].中国生物工程杂志,2013,30(7):108-111.

No related articles found!
Full text



[1] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75, 88 .
[2] XIA Qing-xun and ZHUANG Yi. Remote Attestation Mechanism Based on Locality Principle[J]. Computer Science, 2018, 45(4): 148 -151, 162 .
[3] LI Bai-shen, LI Ling-zhi, SUN Yong and ZHU Yan-qin. Intranet Defense Algorithm Based on Pseudo Boosting Decision Tree[J]. Computer Science, 2018, 45(4): 157 -162 .
[4] WANG Huan, ZHANG Yun-feng and ZHANG Yan. Rapid Decision Method for Repairing Sequence Based on CFDs[J]. Computer Science, 2018, 45(3): 311 -316 .
[5] SUN Qi, JIN Yan, HE Kun and XU Ling-xuan. Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem[J]. Computer Science, 2018, 45(4): 76 -82 .
[6] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[7] WU Jian-hui, HUANG Zhong-xiang, LI Wu, WU Jian-hui, PENG Xin and ZHANG Sheng. Robustness Optimization of Sequence Decision in Urban Road Construction[J]. Computer Science, 2018, 45(4): 89 -93 .
[8] LIU Qin. Study on Data Quality Based on Constraint in Computer Forensics[J]. Computer Science, 2018, 45(4): 169 -172 .
[9] ZHONG Fei and YANG Bin. License Plate Detection Based on Principal Component Analysis Network[J]. Computer Science, 2018, 45(3): 268 -273 .
[10] SHI Wen-jun, WU Ji-gang and LUO Yu-chun. Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading[J]. Computer Science, 2018, 45(4): 94 -99, 116 .