Computer Science ›› 2016, Vol. 43 ›› Issue (9): 23-26.doi: 10.11896/j.issn.1002-137X.2016.09.004

Previous Articles     Next Articles

Research on Complexity and Approximation Algorithm for Counting 3-Set Packings of Size k

LIU Yun-long   

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

Abstract: Counting 3-Set Packings of size k is to count distinct packings of size k in a given instance of 3-Set Packing.We first showed that the complexity of this problem is #W[1]-hard,which indicates that there exists no efficient fixed-parameter tractable algorithm for it(unless #W[1]=FPT).Subsequently,by extending the algorithm for counting 3-D Matchings of size k,we obtained a generalized approximation algorithm for counting 3-Set Packings of size k.This algorithm is heavily based on the Monte-Carlo self-adjusting coverage algorithm and the recent improved color-coding techniques.

Key words: 3-Set Packing,Counting,Complexity,Approximation algorithm

[1] McCartin C.Parameterized counting problems[C]∥Proceedings of the 27th International Symposium on Mathematical Foundations of Computer Science(MFCS’02).2002:556-567
[2] Flum J,Grohe M.The parameterized complexity of countingproblems[J].SIAM Journal on Computing,2004,33(4):892-922
[3] Zhang Chi-hao,Chen Yi-jia.Counting problems in parameterized complexity[J].TsingHua Science and Technology,2014,19(4):410-420
[4] Flum J, Grohe M.Parameterized complexity theory[M].Springer-Verlag Berlin Heidelberg,2006
[5] Curticapean R.Counting matching of size k is #W[1]-hard[C]∥Proceedings of the 40th International Colloquium on Automata,Languages and Programming(ICALP’13).2013:352-363
[6] Arvind V,Raman V.Approximation algorithms for some para-meterized counting problems[C]∥Proceedings of the 13th International Symposium on Algorithms and Computation (ISAAC’02).2002:453-464
[7] Garey M R,Johnson D S.Computers and Intractability:A Guide to the Theory of NP-Completeness[M].W.H.Freeman,New York,1979
[8] Wang Jian-xin,Feng Qi-long.An O*(3.523k) parameterized algorithm for 3-Set Packing[C]∥Proceedings of the 5th International Conference on Theory and Applications of Models of Computation (TAMC’08).2008:82-93
[9] Abu-Khzam F N.A quadratic kernel for 3-Set Packing [C]∥Proceedings of the 6th Annual Conference on Theory and Applications of Models of Computation (TAMC’09).2009:81-87
[10] Feng Qi-long,Wang Jian-xin,Chen Jian-er.Improved algorithms for weighted 3-Set Packing[J].Journal of Software,2010,21(5):886-898(in Chinese) 冯启龙,王建新,陈建二.加权3-Set Packing 的改进算法[J].软件学报,2010,21(5):886-898
[11] Li Shao-hua,Feng Qi-long,Wang Jian-xin,et al.Kernelizaitonfor weighted 3-Set Packing problem[J].Journal of Computer Research and Development,2012,49(8):1781-1786(in Chinese) 李绍华,冯启龙,王建新,等.加权3-Set Packing 问题的核心化[J].计算机研究与发展,2012,49(8):1781-1786
[12] Dahllof V,Jonsson P.An algorithm for counting maximumweighted independent sets and its application [C]∥Proceedings of the 13th annual ACM-SIAM Symposium on Discrete Algorithms (SODA’02).2002:292-298
[13] Liu Yun-long, Chen Jian-er, Wang Jian-xin.On counting 3-DMatchings of size k [J].Algorithmica,2009,54:530-543
[14] Chen Jian-er,Lu Song-jian,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
[15] Karp R M,Luby M,Madras N.Monte-Carlo approximation algorithms for enumeration problems [J].Journal of Algorithms,1989,10:429-448
[16] Liu Yun-long,Wang Jian-xin.On counting parameterized matching and packing [C]∥Proceedings of the 10th International Frontiers of Algorithmics Workshop (FAW’16).2016:125-134

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] 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 .
[6] 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 .
[7] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[8] 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 .
[9] LIU Qin. Study on Data Quality Based on Constraint in Computer Forensics[J]. Computer Science, 2018, 45(4): 169 -172 .
[10] ZHONG Fei and YANG Bin. License Plate Detection Based on Principal Component Analysis Network[J]. Computer Science, 2018, 45(3): 268 -273 .