算法与逻辑团队成果被SODA 2027录用

近日，理论计算机科学领域顶级会议SODA 2027公布论文录用结果，算法与逻辑团队论文《Faster Parameterized Vertex Multicut》被录用。该论文由刘雨曦、彭俊强、田康毅三位博士生在肖鸣宇教授指导下，与美国加利福尼亚大学圣巴巴拉分校的Huairui Chu博士生（原算法与逻辑团队本科生）、Daniel Lokshtanov教授合作完成。

该论文主要研究顶点多割问题（Vertex Multicut）。这是图论与组合优化中的经典问题，也是最小割问题的重要推广，其目标是在无向图中删除少量顶点，使多对指定顶点之间不再连通。如何在允许删除的顶点数较小时高效求解这一问题，是参数算法领域的重要研究课题。该论文通过改进图分离问题中的关键算法技术，显著改进了顶点多割问题此前最佳已知的运行时间上界。并进一步改进了有向子集反馈顶点集（Directed Subset Feedback Vertex Set）和有向多路割（Directed Multiway Cut）两个问题的算法。三项结果与此前最佳已知算法的对比如下表所示。

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