近日，第32届国际人工智能联合会议IJCAI（International Joint Conference on Artificial Intelligence）放榜，我校计算机科学与工程学院（网络空间安全学院） 2019级本科生王正仁以第一作者身份撰写的关于松弛团搜索问题的论文《A Fast Maximum k-Plex Algorithm Parameterized by the Degeneracy Gap》被接收，届时该学生将在会议上展示成果并进行学术报告。该论文是在电子科技大学算法与逻辑团队周毅副教授（通讯作者）和肖鸣宇教授指导下完成，参与作者还有硕士生罗春雨同学。这也是王正仁同学继WWW 2022之后，本科阶段以第一作者发表的第二篇CCF-A类会议论文。

k-Plex是一种松弛团模型，相比于传统团模型提高了对数据噪声的容忍度，在社区发现算法中常被用于社区的图论建模。最大k-Plex问题旨在搜索图中规模最大的k-Plex，该问题属于NP难问题。该论文基于参数算法理论，给出了一个快速的最大k-Plex的搜索算法，可以在大规模稀疏图中高效地搜索出最大k-Plex。

论文揭示了大规模稀疏图中存在的小参数——退化差，并设计了相应的固定参数可解（Fixed-Parameter Tractable，FPT）算法。即在退化差参数有界的情况下，最大k-Plex问题能够在多项式时间内求解。此外，论文通过广泛地实验证明，退化差参数通常在输入图规模的对数数值范围内，并且所提出的固定参数可解算法达到了目前的最优性能。

该论文中所提出的固定参数可解算法，其算法框架和运行实例分别如算法1和表1所示。

IJCAI是人工智能领域顶级会议，位列中国计算机学会推荐国际会议CCF-A类。本年度会议投稿超过4500篇，录用率仅为15%，会议将于8月在中国澳门召开。除以上介绍的这篇论文以外，算法与逻辑团队的研究生彭俊强以第一作者身份撰写的另一篇论文《Fast Algorithms for SAT with Bounded Occurrences of Variables》也被IJCAI 2023接收。

王正仁，2022年度“成电杰出学生（本科生）”，现计算机学院大四本科生。他从大一开始以学院拔尖人才计划的形式进入算法与逻辑团队学习，主要专注于算法工程与理论方向上的前沿问题，以第一作者身份在CCF-A类会议WWW 2022和IJCAI 2023上发表两篇论文。

电子科技大学算法与逻辑团队由新西兰院士Bakh Khoussainov教授和肖鸣宇教授共同组建，周毅副教授、郝东副教授和许超助理教授等多位老师参与。该团队致力于基础理论研究，以探索算法难题和解决重要的科学问题为宗旨，激发和培养学生及青年老师对算法和基础理论的兴趣，为算法及相关研究方向感兴趣的师生提供一个交流平台。团队目前重点关注的研究方向包括：算法设计与分析（包括近似算法、参数算法、精确算法、在线算法等）、逻辑、图论与图算法、组合优化、算法工程、机制设计与算法博弈论、形式化方法与认证等。

每年有10余名对算法和数学感兴趣的本科生进入团队学习，科研能力明显提升，高水平论文等学术成果层出不穷。长期以来，学生在多项科技竞赛中斩获奖项，多名学生在程序设计竞赛和数学建模竞赛中取得非常优异的成绩。在ACM程序设计竞赛中，团队多名学生打进了世界总决赛；在IEEE极限编程竞赛中团队学生连续两年获得世界第二名，五次进入世界前十名；团队学生在2022年和2023年连续两年获得华为软件精英挑战赛全球总决赛冠军。

本文转载自【电子科技大学】官方网站