本项目主要用计算理论中的新发展起来的分支——参数算法等方法来研究若干基本NP难问题，主要包括：独立集、点覆盖、边支配集、图多分割等问题。项目按照计划全部完成，研究成果超过计划的一倍。项目期间共研获10余个当前最佳的算法等。其中两个基本参数算法被参数计算新闻快报《Parameterized Complexity News》中的Table of Races栏目收录，是该栏目目前收录的仅有两项来自中国的研究结果；在图多分割问题上解决了一个10余年的公开难题；在超图上的多分割研究结果及后续研究在EGRES Open等科学网站上被介绍。项目期间以项目负责人为第一作者在Algorithmica、Theoretical Computer Science、MFCS、ISAAC等国际重要期刊和会议发表学术论文21篇，接收并网上发表论文2篇，其中5篇属于中国计算机协会2013年公布的的B区论文，6篇属于C区论文。另外在投C区以上论文4篇。项目主要取得的研究结果如下： 1. 给出了超图上3块割问题的第一个多项式算法，被EGRES Open网站介绍同时算法被日本京都大学实现，在VLSI上得到应用。 2. 给出了多块割问题一个常用的贪心分而治之算法的的紧致近似率从而解决此问题中的一个10余年的公开问题，同时得到多块割问题目前最好的近似算法。 3. 改进了3度图点覆盖问题和边支配集问题两个基本问题的最佳参数算法，其结果在《Parameterized Complexity News》中的Table of Races栏目中被列出。 4. 改进了低度图上独立集问题的最佳精确算法，基于该结果有望改进1986年Robson给出的一般图上的最佳结果。 5. 在其它图多分割、反馈集、TSP、支配集等问题上给出了8个最佳参数算法、精确算法、核心化算法等。 项目（包括地方人才计划等配套）资助学术交流包括：海外高校访问7人次，参加国际并报告会议13人次，邀请海外专家访问11人次等，国内高校访问8人次。共培养10余本科生和8名硕士研究生。