近日，理论计算机科学领域顶级会议SODA 2027公布论文录用结果，我校计算机科学与工程学院（网络空间安全学院）算法与逻辑团队论文《Faster Parameterized Vertex Multicut》被录用。该论文由刘雨曦、彭俊强、田康毅三位博士生在肖鸣宇教授指导下，与美国加利福尼亚大学圣巴巴拉分校的Huairui Chu博士生（原算法与逻辑团队本科生）、Daniel Lokshtanov教授合作完成。
该论文主要研究顶点多割问题（Vertex Multicut）。这是图论与组合优化中的经典问题，也是最小割问题的重要推广，其目标是在无向图中删除少量顶点，使多对指定顶点之间不再连通。如何在允许删除的顶点数较小时高效求解这一问题，是参数算法领域的重要研究课题。
与分离一对顶点的最小割问题不同，多对顶点的分离要求会相互影响：分别求解每一对顶点的最小割，并不能保证得到整体最优解。顶点多割是NP难问题，参数算法则将允许删除的顶点数k作为衡量难度的关键参数，寻求在k较小时高效求解。自2011年该问题首次被证明具有固定参数可解性以来，进一步降低算法对k的依赖一直是重要研究方向。
此次研究重点改进了“影子消除”技术。在算法处理中，删除作为解的顶点集合后，部分顶点会与预先选定的参考顶点集失去联系，这些顶点构成该解的“影子”。影子消除在保留解的前提下简化这部分结构，是多类图分离算法的重要步骤。团队利用小规模顶点集合即可命中相关“重要分离集”的性质，减少随机采样中需要同时约束的顶点，降低了这一关键步骤的计算开销。
针对另一处计算瓶颈，团队引入线性规划，结合剩余删除预算和放宽约束后问题的最优值衡量搜索进展，并通过分支与图收缩，将实例化简为每个相关连通分量至多连接两个参考顶点的“双足”结构。两项改进共同减少了需要考察的候选情形，得到更快的精确算法。
基于上述两项改进，研究团队显著改进了顶点多割问题此前最佳已知的运行时间上界。借助改进后的影子消除技术，研究团队还进一步改进了有向子集反馈顶点集（Directed Subset Feedback Vertex Set）和有向多路割（Directed Multiway Cut）两个问题的算法。三项结果与此前最佳已知算法的对比如下表所示。
具体而言，研究将顶点多割的运行时间由O^* (k^(O(k^2)))改进为O^* (k^(O(k)))，其中k表示允许删除的顶点数。这一改进降低了运行时间上界随k增长的速度，为小参数情形下的精确求解提供了更好的理论保证。
改进后的影子消除技术还能用于有向图，支撑上述两个问题的算法提速，体现了这一方法对不同图分离问题的适用性。
SODA（ACM-SIAM Symposium on Discrete Algorithms）由计算机协会（ACM）与工业与应用数学学会（SIAM）共同主办，与STOC、FOCS并列为理论计算机科学领域的三大顶级学术会议，属于中国计算机学会推荐的A类国际会议，在国际计算机科学界具有重要学术影响力。
计算机（网安）算法与逻辑团队由欧洲科学院院士、新西兰皇家学会院士Bakh Khoussainov教授和算法著名专家肖鸣宇教授共同组建，现有许超教授、Toru Takisaka教授、周毅教授、郝东教授等多位骨干成员。团队长期深耕算法设计与分析（包括近似算法、参数算法、精确算法、在线算法等），逻辑，图论与图算法，组合优化，算法工程，机制设计与算法博弈论，形式化方法与认证等理论方向，是我国西部地区理论计算机科学研究方向的高地之一。近年来指导学生在SODA、EC、WINE、CAV、SAT、WWW、AAAI、I&C、JCSS等理论方向顶级会议和期刊上连续发表高水平成果。
论文信息如下（作者按姓氏字母顺序排列）：
标题：Faster Parameterized Vertex Multicut
作者：Huairui Chu, Yuxi Liu, Daniel Lokshtanov, Junqiang Peng, Kangyi Tian, Mingyu Xiao
论文链接：https://arxiv.org/abs/2602.13981
