软件学报

作者：刘国航，陈翌佳

单位：刘国航，上海交通大学 电子信息与电气工程学院, 上海 20024011,陈翌佳，上海交通大学 电子信息与电气工程学院, 上海 20024002

关键词：模型检测;算法元定理;稀疏性;结构图论;参数复杂性

基金：国家自然科学基金面上项目(62372291)

图上的诸多计算问题都是NP难问题, 因此经常会将问题限定在一些特定的图类上. 这类方法在过去的几十年间收获了大量特定图类(如度有界图类、树宽有界图类、平面图类等)上的高效算法, 其中很大一部分都能统一到算法元定理的框架下. 算法元定理是一类通用的结论, 主要描述模型检测问题(即判定结构的逻辑性质)的高效算法. 现有的算法元定理主要基于现代结构图论, 并且大多研究固定参数易解算法,即参数复杂性意义下的高效算法. 在许多良构的图类上, 一些常见逻辑(如一阶逻辑和一元二阶逻辑)的模型检测问题是固定参数易解的. 由于不同逻辑的表达能力不同, 不同图类上的模型检测问题的易解性也有显著的区别, 因此探索易解的最大范围也是算法元定理研究的重要课题. 研究表明, 一阶逻辑模型检测问题的易解性与图的稀疏性密切关联. 经过数十年的努力, 目前学界对于稀疏图类的认识已经较为成熟, 近年的研究重心逐渐转向一些良构的稠密图类, 研究也面临着更多的挑战. 目前在稠密图类上已经得到了若干深刻的算法元定理, 相关的探索仍在继续. 将全局性地介绍算法元定理领域的发展, 旨在为国内的相关研究提供一些线索和助力.

来源：2025年第3期

《软件学报》期刊编辑部

查看软件学报杂志2025年第3期