核心化算法中的新技术研究

Kernelizaiton is one of the most active branches in parameterized algorithms. This project will focus on how to use the idea of “extremal graph theory” and “approximation kernelization” to design kernelizaiton algorithms. In details, we will investigate for which problems we can use extremal graph theory to design kernelization algorithms, and study kernelizations for some problems in planar graphs. The project will also investigate the possibility of the approximation kernelization model. These lay a foundation for our further research on kernelization algorithms.

核心化算法是目前参数计算理论中非常活跃的一个研究分支。本项目主要对“基于极值图论的思想进行核心化算法设计”和“新的核心化模型”这两个问题进行探索性研究。探索那些类型的问题易于利用极值图论思想来进行核心算法设计，并解决平面图上一些具体的核心化问题。同时研究近似核心化这种模型的可行性和实用性。为今后进一步研究核心化算法打下基础。

本项目被批准为一年期的培育项目，批获的研究周期为：2018 年1 月至2018 年12 月。因此研究内容进行了相应的调整。本项目主要对“基于极值图论的思想进行核心化算法设计”和“新的核心化模型”这两个问题进行探索性研究。虽然研究时限较短，但是项目组仍然取得了系列科研成果，在过去一年多的时间里，已经发表了论文6篇，按CCF分区类来算，其中A区论文2篇，B区论文2篇，C区论文1篇。所有这6篇论文均第一标注了该项目基金号。另外在投论文9篇。..该项目深入研究了极值图论中的一些图性质，更加明确了这些性质和思想能用于核心化的设计。在该项目立项期（2017年），已经研究了多项重要结果，在JCSS上发表两篇相关论文。2018年，试探性研究了边不相交三角形装箱问题（the Edge-Disjoint Triangle Packing problem）和平面图上圈装箱问题（the Cycle Packing Problem in planar graphs）的核心化算法，对前个问题充分利用边不相交三角形的一些图论性质，设计了一个可以无限逼近3k大小的问题核，改进了原有的3.5k大小的问题核；对后一个问题也设计出了一个大小在300k以内的问题核。同时，考虑参数算法和核心化算法在物品分配系列问题上的应用，得到系列有意义的结果，发表在系列重要会议上，如ICALP 2018，IJCAI 2018，AAMAS 2018和AAAI 2019等。对新的核心化模型的探索性研究，主要研究了近似问题核的可行性，总结了各种不同的近似化模型并对它们的合理性进行了研究，总结了近似核心化研究的可行方向。..总体来说，通过该项目的研究，更加明确了该研究方向具有较大研究意义和前景。