电子科大在理论计算机科学领域COCOON上发表研究成果

近日，我校计算机科学与工程学院（网络空间安全学院）计算机科学与技术专业2020级本科生田康毅以第一作者身份在CCF理论计算机科学领域B类会议COCOON上发表题为《Parameterized Algorithms for Cluster Vertex Deletion on Degree-4 Graphs and General Graphs》的论文。计算机（网安）学院算法与逻辑团队的肖鸣宇教授为第二作者和通讯作者，加拿大里贾纳大学的Boting Yang教授为第三作者。

该论文研究了著名的聚类点删除问题（CVD问题）的算法与计算复杂性，得到该问题精确求解中，以点删除集大小k为参数的最佳运行时间上界，改进了Tsur于2021年给出的结果。本文给出的时间运行界和历史上该问题的运行时间如表1中所示。

CVD问题是图算法中一个著名的NP难问题，该问题关注是否能通过删除图中不超过k个顶点使得剩下图中每一个连通块都是一个完全图。由于CVD问题良好地刻画了聚类的性质，该问题在机器学习和计算生物学中有着广泛的应用。本论文首先针对低度图上的CVD问题进行了分析，在度数不超过4的图上先设计了一个快速算法；然后在4度图的结果基础上，使用自动生成搜索树（Automated Generation of Searching Trees）的技术对一般图进行了深入分析，最终改进该问题当前最好的算法。