Computer Science ›› 2016, Vol. 43 ›› Issue (8): 7-12, 54.doi: 10.11896/j.issn.1002-137X.2016.08.002

Previous Articles     Next Articles

Advances in Fixed-parameter Tractable Approximation Algorithms for NP-hard Problems

LIU Yun-long and CUI Meng-tian   

  • Online:2018-12-01 Published:2018-12-01

Abstract: Fixed-parameter tractable approximation algorithm produces the approximation solution by using the approach of parameterized computation,which becomes one of the practical approaches to deal with NP-hard problems.In this paper,we investigated the fixed-parameter tractable approximation algorithms for various NP-hard problems according to their parameterized computational complexity.More specifically,we gave a survey on the fixed-parameter tractable approximation algorithms for the fixed-parameter tractable problems,the problems with unknown parameteri-zed computational complexity,and the W[t]-hard problems (t≥1) respectively.For each kind of problems,we summarized typical examples with their results obtained in recent years,analyzed the main techniques employed in the algorithms and discussed some issues to be further studied.

Key words: Fixed-parameter tractable approximation algorithm,W[t]-hard,Branching and searching

[1] Hochbaum D S.Approximation algorithms for NP-hard problems [M].PWS Publishing Company,Boston,MA,1997
[2] Cygan M,Kowalik L,Pilipczuk M,et al.Exponential-time approximation of hard problems [EB/OL].
[3] Escoffier B,Paschos V T,Tourniaire E.Moderately exponential time and fixed parameter approximation algorithms [J].Optimization,2013,62(8):1019-1036
[4] Downey R G,Fellows M R.Parameterized Complexity [M].Springer,New York,1999
[5] Downey R G,Fellows M R,McCartin C.Parameterized approximation algorithms [C]∥Proceedings of the 2nd International Workshop on Parameterized and Exact Computation (IWPEC’06).2006:121-129
[6] Chen Y,Grohe M,Grüber M.On parameterized approximability [C]∥Proceedings of the 2nd International Workshop on Parame-terized and Exact Computation (IWPEC’06).2006:109-120
[7] Cai L,Huang X.Fixed-parameter approximation:conceptualframework and approximability results [C]∥Proceedings of the 2nd International Workshop on Parameterized and Exact Computation (IWPEC’06).2006:96-108
[8] Marx D.Parameterized complexity and approximation algo-rithms [J].The Computer Journal,2008,51(1):60-78
[9] Grohe M,Grüber M.Parameterized approximability of the disjoint cycle problem [C]∥Proceedings of the 34th International Colloquium on Automata,Languages and Programming (ICALP’07,Track A).2007:363-374
[10] Brankovic L,Fernau H.Combining two worlds:parameterised approximation for vertex cover [C]∥Proceedings of the 21st International Symposium on Algorithms and Computation (ISAAC’10).2010:390-402
[11] Brankovic L,Fernau H.Parameterized approximation algorithms for hitting set [C]∥Proceedings of the 9th International Workshop on Approximation and Online Algorithms (WAOA’11).2011:63-76
[12] Fellows M R,Kulik A,Rosamond F,et al.Parameterized approximation via fidelity preserving transformations [C]∥Proceedings of the 39th International Colloquium on Automata,Languages and Programming (ICALP’12).2012:351-362
[13] Kolay S,Misra P,Ramanujan M S,et al.Parameterized approximations via d-skew-symmetric multicut [C]∥Proceedings of the 39th International Symposium on Mathematical Foundations of Computer Science (MFCS’14).2014:457-468
[14] Escoffier B,Monnot J,Paschos V T,et al.New results on polynomial inapproximability and fixed parameter approximability of edge dominating set [C]∥Proceedings of the 7th International Symposium on Parameterized and Exact Computation (IPEC’12).2012:25-36
[15] Bar-Yehuda R.One for the price of two:a unified approach for approximating covering problems[J].Algorithmica,2000,27:131-144
[16] Chen J,Kanj I A,Jia W.Vertex cover:further observations and further improvements [J].Journal Algorithms,2001,41:280-301
[17] Gaspers S,Ordyniak S,Ramanujan M S,et al.Backdoors to q-Horn [C]∥Proceedings of the 30th Symposium on Theoretical Aspects of Computer Science (STACS’13).2013:67-79
[18] Ford Jr L R,Fulkerson D R.Maximal flow through a network [J].Canadian Journal of Mathematics,1956,8:399-404
[19] Kociumaka T,Pilipczuk M.Faster deterministic feedback vertex set [J].Information Processing Letters,2014,114(10):556-560
[20] Liu Yun-long,Wang Jian-xin,Xu Chao,et al.An efficientbranching strategy based on structural relationship among multiple forbidden induced subgraphs [J].Journal of Combinatorial Optimization,2015,29(1):257-275
[21] Liu Yun-long,Wang Jian-xin,You Jie,et al.Edge deletion problems:branching facilitated by modular decomposition [J].Theoretical Computer Science,2015,573:63-70
[22] Downey R G,Fellows M R.Fundamentals of ParameterizedComplexity [M].Springer,2013
[23] Gaspers S,Szeider S.Backdoors to acyclic SAT [C]∥Procee-dings of the 39th International Colloquium on Automata,Languages and Programming (ICALP’12).2012:363-374
[24] Gaspers S,Szeider S.Strong backdoors to nested satisfiability [C]∥Proceedings of the 15th International Conference on Theo-ry and Applications of Satisfiability Testing (SAT’12).2012:72-85
[25] Gaspers S,Szeider S.Strong backdoors to bounded treewidth SAT [C]∥Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS’13).2013:489-498
[26] Marx D,Razgon I.Constant ratio fixed-parameter approximation of the edge multicut problem [J].Information Processing Letters,2009,109 (20):1161-1166
[27] Bousquet N,Daligault J,Thomassé S.Multicut is FPT [C]∥Proceedings of the 43th Annual ACM Symposium on Theory of Computing (STOC’11).2011:459-468
[28] Ramanujan M S,Saurabh S.Linear time parameterized algo-rithms via skew-symmetric multicut [C]∥Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’14).2014:1739-1748
[29] Bodlaender H L.On disjoint cycles [J].International Journal of Foundations of Computer Science,1994,5(1):59-68
[30] Chitnis R,Hajiaghayi M T,Kortsarz G.Fixed-parameter and approximation algorithms:a new look [C]∥Proceedings of the 8th International Symposium on Parameterized and Exact Computation (IPEC’13).2013:110-122
[31] Arvind V,Raman V.Approximation algorithms for some parameterized counting problems [C]∥Proceedings of the 13th International Symposium on Algorithms and Computation (ISAAC’02).2002:453-464
[32] Chen Jian-er,Liu Yang,Lu Song-jian,et al.A fixed-parameter algorithm for the directed feedback vertex set problem [C]∥Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC’08).2008:177-186
[33] Karp R M,Luby M,Madras N.Monte-Carlo approximation algorithms for enumeration problems [J].Journal of Algorithms,1989,10:429-448
[34] Liu Yun-long,Chen Jian-er,Wang Jian-xin.On counting 3-Dmatchings of size k [J].Algorithmica,2009,54:530-543
[35] Chen Jian-er,Lu Songjian,Sze S H,et al.Improved algorithms for path,matching,and packing problems [C]∥Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’07).2007:298-307
[36] Liu Yun-long,Wang Jian-xin,Chen Jian-er.Improved parameteri-zed algorithm for the Multicut problem [J].Journal of Software,2010,21(7):1515-1523(in Chinese) 刘运龙,王建新,陈建二.Multicut问题参数算法的改进[J].软件学报,2010,21(7):1515-1523
[37] Marx D.Can you beat treewidth? [J].Theory of Computing,2010,6:85-112
[38] Fellows M R,Guo J,Marx D,et al.Data reduction and problem kernels (Dagstuhl Seminar 12241) [R].Dagstuhl Reports,2012,2(6):26-50

No related articles found!
Full text



[1] . [J]. Computer Science, 2018, 1(1): 1 .
[2] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75, 88 .
[3] XIA Qing-xun and ZHUANG Yi. Remote Attestation Mechanism Based on Locality Principle[J]. Computer Science, 2018, 45(4): 148 -151, 162 .
[4] 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 .
[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] 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 .
[10] ZHOU Yan-ping and YE Qiao-lin. L1-norm Distance Based Least Squares Twin Support Vector Machine[J]. Computer Science, 2018, 45(4): 100 -105, 130 .