微信服务号

微信订阅号

2025年5月1日 11:16 星期四
首页 > 过刊浏览>2009年第20卷第9期 >2307-2319
PDF HTML阅读 XML下载 导出引用 引用提醒
参数计算中核心化技术及其应用
作者:
基金项目:

Supported by the National Basic Research Program of China under Grant No.2008CB317107 (国家重点基础研究发展计划(973)); the National Natural Science Foundation of China under Grant Nos.60433020, 60773111 (国家自然科学基金); the Program for New Century Excellent Talents in University of China under Grant No.NCET-05-0683 (新世纪优秀人才支持计划); the Program for Cheung Kong Scholars and Innovative Research Team in University of China under Grant No.IRT0661 (长江学者和创新团队发展计划)


Kernelization Techniques and Its Applications to Parameterized Computation
Author:
  • 摘要
    • | |
  • 访问统计
    • |
  • 参考文献 [80]
    • |
  • 相似文献 [20]
    • | | |
  • 文章评论
    摘要:

    在参数计算与复杂性理论中,一个参数问题是固定参数可解的问题当且仅当该问题是可核心化的.核心化技术是参数化算法设计中应用最为广泛、有效的技术,是参数理论中的一个研究热点.通过实例分析对比了最主要的4种核心化技术的基本思想、应用特点和方法,总结了核心化技术在cover类、packing类和cut类等几个重要领域中的应用成果,展望核心化技术的进一步研究方向并加以分析讨论,针对核心化新技术研究和某些热点问题,提出了可能采取的核心优化方法和思路.

    Abstract:

    According to parameterized complexity theory, a decidable parameterized problem is fixed-parameter tractable if and only if it can be kernelized. Kernelization is the most widely applied and effective technique in the parameterized algorithm design. It is one of the hottest issues in parameterized complexity theory. This paper firstly introduces four main kernelization techniques, which are compared and analyzed with practical examples. Then it discusses how to apply these techniques to parameterized problems, such as covering problems, packing problems and cutting problems. Finally, the paper gives the future research directions about kernelization, especially the new possible kernelization technique and the kernel optimization of several FPT problems.

    参考文献
    [1] Chen J. Parameterized computation and complexity: A new approach dealing with NP-hardness. Journal of Computer Science and Technology, 2005,20(1):18-37.
    [2] Downey RG, Fellows MR. Parameterized computational feasibility. Feasible Mathematics II, Birkhauser, 1992. http://www.mcs.vuw.ac.nz/math/papers/feasible.ps
    [3] Chen J, Kanj IA, Jia W. Vertex cover: Further observations and further improvements. Journal of Algorithms, 2001,41:280-301.
    [4] Roth-Korostensky C. Algorithm for building multiple sequence alignments and evolutionary trees [Ph.D. Thesis]. Diss.ETH No.13550, 2000.
    [5] Garey MR, Johnson DS. Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W.H.Freeman & Co., 1979.
    [6] Chen J, Friesen DK, Jia WJ, Kanj IA. Using nondeterminism to design efficient deterministic algorithms. Algorithmica 40, 2004. 83-97.
    [7] Dehne F, Fellows M, Rosamond F, Shaw P. Greedy localization, iterative compression and modeled crown reductions: New FPT techniques and improved algorithms for max set splitting, and a novel 2k kernelization for vertex cover. LNCS 3162, 2004. 271-281.
    [8] Jia WJ, Zhang CL, Chen J. An efficient parameterized algorithm for m-set packing. Journal of Algorithms, 2004,50(1):106-117.
    [9] Alon N, Yuster R, Zwick U. Color-Coding. Journal of the ACM, 1995,42(4):844-856.
    [10] Sloper C, Telle JA. An overview of techniques for designing parameterized algorithms. The Computer Journal, 2008,51:122-136.
    [11] Wang JX, Huang YN, Chen JE. A motif finding algorithm based on color coding technology. Journal of Software, 2007,18(6): 1298-1307 (in Chinese with English abstract). http://www.jos.org.cn/1000- 9825/18/1298.htm
    [12] Wang JX, Liu YL, Chen JE. An effective coloring algorithm for close relationship between the scales of element set and color set and its application. Chinese Journal of Computers, 2008,31(1):32-42 (in Chinese with English abstract).
    [13] Fellows M. Blow-ups, win/win’s, and crown rules: some new directions in FPT. LCNS 2880, Berlin: Springer-Verlag, 2003. 1-12
    [14] Mathieson L, Prieto E, Shaw P. Packing edge disjoint triangles: A parameterized view. LNCS 3162, 2004. 127-137.
    [15] Abu-Khzam FN, Collins RL, Fellows MR, Langston MA, Suters WH, Symons CT. Kernelization algorithms for the vertex cover problem: Theory and experiments. ALENEX/ANALC, 2004.62-69.
    [16] Wang JX, Ning D, Feng QL, Chen JE. An improved parameterized algorithm for a generalized matching problem. In: Agrawal M, et al., eds. Proc. of the 5th Annual Conf. on Theory and Applications of Models of Computation (TAMC2008). LNCS 4978, Berlin: Springer-Verlag, 2008. 212-222.
    [17] Fellows M, Heggernes P, Rosamond F, Sloper C, Telle JA. Finding k disjoint triangles in an arbitrary graph. LNCS 3353, 2004. 235-244.
    [18] Fellows MR, McCartin C, Rosamond FA, Stege U. Coordinatized kernels and catalytic reductions: An improved FPT algorithm for max leaf spanning tree and other problems. LNCS 1974, 2000. 240-251.
    [19] Guo J. A more effective linear kernelization for cluster editting. LNCS 4614, 2007. 36-47.
    [20] Prieto E, Sloper C. Reducing to independent set structure-the case of k-internal spanning tree. Nordic Journal of Computing, 2005,12(3):308-318.
    [21] Prieto E, Sloper C. Looking at the stars. Theoretical Computer Science 351, 2006. 437-445.
    [22] Chen J, Lu S. Improved parameterized set splitting algorithms: A probabilistic approach. Algorithmica, 2008.
    [23] Zhang HJ, Ling CX. An improved learning algorithm for augmented naive bayes. LNCS 2035, 2001. 581-586.
    [24] Dehne F, Fellows MR, Rosamond FA. An FPT algorithm for set splitting. LNCS 2880, 2003. 180-191.
    [25] Lokshtanov D, Sloper C. Fixed parameter set splitting, linear kernel and improved running time. In: Proc. of the Algorithms and Complexity in Durham 2005. King’s College Press, 2005.105-113.
    [26] Chang L. The parameterized vertex problem and the minimum vertex cover problem [MS. Thesis]. Changsha: Central South University, 2007 (in Chinese with English abstract).
    [27] Buss JF, Goldsmith J. Nondeterminism within P. SIAM Journal on Computing, 1993,22(4):560-572.
    [28] Stege U, Fellows M. An improved fixed parameter algorithm for vertex cover. Technical Report, ETH Zurich: Department of Computer Science, 1999.
    [29] Downey RG, Fellows MR, Stege U. Parameterized complexity: A framework for systematically confronting computational intractability. In: Abello J, Vitter J, eds. Proc. of the AMS(DIMACS). 1999. 49-99.
    [30] Niedermeier R, Rossmanith P. Upper bounds for vertex cover further improved. LNCS 1563, 1999. 561-570.
    [31] Chlebfk M, Chlebikova J. Crown reductions for the minimum weighted vertex cover problem. Electrunic Colloquium on Computational Complexity, 2004.
    [32] Rajagopalan S, Vachharajani M, Malik S. Handling irregular ILP within conventional VLIW chedulers using artificial resource constraints. In: Chair T, et. al., eds. Proc. of the CASES. ACM Press, 2000. 157-164.
    [33] Piepho HP. An algorithm for a letter-based representation of all-pairwise comparisons. Journal of Computational and Graphical Statistics, 2004,13(2):456-466.
    [34] CaPrara A, Paneonesi A, Rizzi R. Packing cycles in undirected graphs. Algorithms, 2003,48(l):239-256.
    [35] Gramm J, Guo J, Huffner F, Niedermeier R. Data reduction, exact, and heuristic algorithms for clique cover. In: Raman R, ed. Proc. of the 8th ACM-SIAM ALENEX. ACM-SIAM, 2006. 86-94.
    [36] Megiddo N, Tamir A. On the complexity of locating linear facilities in the plane. Operations Research Letters, 1982,1:194–197, 662, 671.
    [37] Langerman S, Morin P. Covering things with things. LNCS 2461, 2002. 662-674.
    [38] Ma ZY. Research and application of measure and conquer in set packing [MS. Thesis]. Changsha: Central South University, 2007 (in Chinese with English abstract).
    [39] Cesati M. Compendium of parameterized problems. 2001. http://citeseer.ist.psu.edu/ viewdoc/cesati01compendium.html
    [40] Arkin EM, Hassin R. On local search for weighted k-set packing. LNCS 1284, 1997. 13-22.
    [41] Fomin FV, Grandoni F, Kratsch D. Measure and conquer: A simple O(20.288n) independent set algorithm. In: Stein C, ed. Proc. of the 17th Annual ACM-SIAM Symp. on Discrete Algorithm. 2006. 18-25.
    [42] Gabow H. An efficient implementation of Edmonds’ algorithm for maximum matching on graphs. STAN-CS-72-328, Technical Report, No.31, Stanford University, 1972.
    [43] Hazan E, Safra S, Schwartz O. On the Complexity of Approximating k-Set Packing. Computational Complexity, 2006. 20-39.
    [44] Berman P. A d/2 approximation for maximum weight independent set in d-claw free graphs. LNCS 1851, 2000. 214-219.
    [45] Fellows MR, Knauer C, Nishimura N, Ragde P. Faster fixed-parameter tractable algorithms for matching and packing problems. LN CS 3221, 2004. 311-322.
    [46] Liu Y, Lu S, CJ, Sze SH. Greedy localization and color-coding:improved matching and packing algorithms. LNCS 4169, 2006. 84-95.
    [47] Wang JX, Feng QL. An O*(3.523k) parameterized algorithm for 3-set packing. In: Agrawa M, et al., eds. Proc. of the Theory and Applications of Models of Computation (TAMC 2008). LNCS 4978, 2008. 82-93.
    [48] Ning D. Parameterized algorithm for the matching and packing problem [MS. Thesis]. Changsha: Central South University, 2007 (in Chinese with English abstract).
    [49] Hassin R, Rublnstein S. An approximation algorithm for maximum packing of 3-edge Paths. Information processing Letters, 1997, 63-67.
    [50] Holyer I. The NP-completeness of some edge-partition problems. SIAM Journal of Computer, 1981, 713-717.
    [51] Fellows M, Heggernes P, Rosamond F, Sloper C, Telle JA. Finding k disjoint triangles in an arbitrary graph. In: Hromkovic J, et al., eds. Proc. of the WG 2004. 2004. 235-244.
    [52] Wang JX, Ning D, Feng QL, Chen JE. An improved parameterized algorithm for P2-packing problem. Journal of Software, 2008,19(11):2879-2886 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/19/2879.htm
    [53] Prieto E. The method of extremal structure on the k-MAXIMUM CUT Problem. Proc. of Computing: Australian Computer Science Communications, 2005,27(4):119-126.
    [54] Paradimitriou CH, Yannakakis M. Optimization, approximation, and complexity classes. Journal of Computer and System Sciences 43, 1991. 425-440.
    [55] Mahajan M, Raman V. Parameterizing above guaranteed values: MaxSat and MaxCut. Journal of Algorithms, 1999,31(2):335-354.
    [56] Fedin SS, Kulikov AS. A 2|E|/4-time algorithm for MAX-CUT. Zapiski Nauchnyh Seminarov POMI, 2002,293:129-138.
    [57] Costa MC, Létocart L, Roupin F. Minimal multicut and maximal integer multiflow: A survey. European Journal of Operation Research, 2005,162:55-69.
    [58] Gupta A. Improved results for directed multicut. In: Farach-Colton M, ed. Proc. of the 14th annual ACM-SIAM Symp. on Discrete Algorithms (SODA 2003). Society for Industrial & Applied Mathematics, 2003. 454-455.
    [59] Calinescu G, Fernandes CG, Reed B. Multicuts in unweighted graphs and digraphs with bounded degree and bounded tree-width. Journal of Algorithms, 2003,48:333-359.
    [60] Marx D. Parameterized graph separation problems. In: Downey R, et al., eds. Proc. of the 1st IWPEC. LNCS 3162, Springer-Verlag, 2004. 71-82.
    [61] Guo J, Hüffner F, Kenar E, Niedermeier R, Uhlmann J. Complexity and exact algorithms for multicut. LNCS 3831, Springer-Verlag, 2006. 303-312.
    [62] Guo J. Rolf Niedermeier. Fixed-Parameter tractability and data reduction for multicut in trees. Networks, 2005,46(3):124-135.
    [63] Niedermeier R, Rossmanith P. An efficient fixed-parameter algorithm for 3-hitting set. Journal of Discrete Algorithms, 2003,1:89-102.
    [64] Nishimura N, Ragde P, Thilikos DM. Smaller kernels for hitting set problems of constant arity. In: Downey R, et al., eds. Proc. of the IWPEC 2004. Springer-Verlag, 2004. 121-126.
    [65] Dehne F, Fellows MR, Rosamond FA. An FPT algorithm for set splitting. LNCS 2880, 2003. 180-191.
    [66] Alber J, Fellows M, Niedermeier R. Polynomial time data reduction for dominating set. Joural of the ACM 51, 2004. 363-384.
    [67] Chen J, Fernau H, Kanj IA, Xia G. Parametric duality and kernelization: Lower bounds and upper bounds on kernel size. STACS 2005. 269-280.
    [68] Niedermeier R. Ubiquitous parameterized-invitation to fixed parameter algorithms. LNCS 3153, Springer-Verlag, 2004. 84–103.
    [69] Mujuni E, Rosamond F. Parameterized complexity of the clique partition problem. In: Harland J, et al., eds. Proc. of the CATS 2008. 2008.
    [70] Guo J, Uhlmann J. Kernelization and complexity results for connectivity augmentation problems. In: Dehne F, et al., eds. Proc. of the WADS 2007. LNCS 4619, 2007. 484-495.
    [71] Bonsma P, Zickfeld F. Spanning trees with many leaves in graphs without diamonds and blossoms. In: Eduardo SL, et al., eds. Proc. of the LATIN 2008. 2008. 531-543.
    [72] Dehne F, Fellows M, Fernau H, Prieto E, Rosamond F. Nonblocker: Parameterized algorithms for minimum dominating set. In: Wiedermann J, et al., eds. Proc. of the SOFSEM 2006. 2006.
    [73] Bodlaender HL, Downey RG, Fellows MR, Hermelin D. On problems without polynomial kernels. In: Proc. of the ICALP(1)2008. 2008. 563-574. http://www.informatik.uni-trier.de/~ley/db/conf/icalp/icalp2008-1.html#BodlaenderDFH08
    [74] Bodlaender HL, Demaine ED, Fellows MR, Guo J, Hermelin D, Lokshtanov D, Muller M, Raman V, van Rooij J, Rosamond FA. Open problems in parameterized and exact computation—IWPEC 2008. Technical Report, CS-2008-017, 2008. 附中文参考文献:
    [11] 王建新,黄元南,陈建二.一种基于彩色编码技术的基序发现算法.软件学报,2007,18(6):1298-1307. http://www.jos.org.cn/1000- 9825/18/1298.htm
    [12] 王建新,刘云龙.陈建二.一种在元素与颜色规模相近时的有效着色算法及其应用.计算机学报,2008,31(1):32-42.
    [26] 常乐.参数化点覆盖及最小点覆盖问题研究[硕士学位论文].长沙:中南大学,2007.
    [38] 马振宇.加权分治技术在Set Packing问题中的应用与研究[硕士学位论文].长沙:中南大学,2007.
    [48] 宁丹.Matching和Packing问题的参数算法研究[硕士学位论文].长沙:中南大学,2007.
    [52] 王建新,宁丹,冯启龙,陈建二.P2-Packing问题参数算法的改进.软件学报,2008,19(11):2879-2886. http://www.jos.org.cn/1000- 9825/19/2879.htm
    引证文献
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

李绍华,王建新,陈建二.参数计算中核心化技术及其应用.软件学报,2009,20(9):2307-2319

复制
分享
文章指标
  • 点击次数:7114
  • 下载次数: 11090
  • HTML阅读次数: 0
  • 引用次数: 0
历史
  • 最后修改日期:2009-02-16
文章二维码
友情链接:中国科学院软件研究所中国计算机学会中国科学院国家自然科学基金委员会CCF数字图书馆Int'l J of Softw Info计算机系统应用
您是第19893203位访问者
版权所有：中国科学院软件研究所 京ICP备05046678号-3
地址：北京市海淀区中关村南四街4号,邮政编码：100190
电话：010-62562563 传真：010-62562533 Email：jos@iscas.ac.cn
技术支持：北京勤云科技发展有限公司

京公网安备 11040202500063号