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