图上若干基本NP难问题的算法研究

结题报告

项目介绍

AI项目解读

基本信息

批准号：
60903007
项目类别：
青年科学基金项目
资助金额：
18.0万
负责人：
肖鸣宇
依托单位：
电子科技大学
学科分类：
F0201.计算机科学的基础理论
结题年份：
2012
批准年份：
2009
项目状态：
已结题
起止时间：
2010-01-01 至2012-12-31

项目参与者：
张胜誉；吴立军；钟秀琴；丁博麟；程伟；黄东；曾荣强；
关键词：
图算法 NP难独立集点覆盖参数计算

项目摘要

本项目主要从参数算法、精确算法和近似算法的角度来研究计算机中一些基本的图问题，其中包括被称之为六个基本NP难问题的独立集和点覆盖问题，以及经典的最大流最小割问题的扩展- - 图多分割问题。这些问题非常基础，且应用相当广泛，在整个计算机学科中影响深远，同时这些问题也被研究得非常透彻，任何改进都将在计算机学科内受到强烈关注。项目申请者在这些问题上具有较强的科研基础，近两年研究获得七个当前最优的参数算法、精确算法和近似算法，并解决一个近二十年的公开难题。.参数计算是本项目主要研究方法之一，研究的是一个很难的问题在某个参数较小的时候是否存在有效算法（参数算法）。基于申请人提出的最远最小割技术和新的分支理论，本项目将有望进一步改进并简化图多分割问题的参数算法，3度图及稀疏图上独立集和点覆盖问题的各项算法。在新理论下参数计算中另一个公开难题还有望被解决。目前以上科研进展顺利，预计3年完成。

结项摘要

本项目主要用计算理论中的新发展起来的分支——参数算法等方法来研究若干基本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名硕士研究生。