良构图类上的模型检测问题  

Model-checking Problem on Well-structured Graph Classes

作　　者：刘国航 陈翌佳 LIU Guo-Hang;CHEN Yi-Jia(School of Electronic Information and Electrical Engineering,Shanghai Jiao Tong University,Shanghai 200240,China)

机构地区：[1]上海交通大学电子信息与电气工程学院,上海200240

出　　处：《软件学报》2025年第3期1107-1130,共24页Journal of Software

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

摘　　要：图上的诸多计算问题都是NP难问题,因此经常会将问题限定在一些特定的图类上.这类方法在过去的几十年间收获了大量特定图类(如度有界图类、树宽有界图类、平面图类等)上的高效算法,其中很大一部分都能统一到算法元定理的框架下.算法元定理是一类通用的结论,主要描述模型检测问题(即判定结构的逻辑性质)的高效算法.现有的算法元定理主要基于现代结构图论,并且大多研究固定参数易解算法,即参数复杂性意义下的高效算法.在许多良构的图类上,一些常见逻辑(如一阶逻辑和一元二阶逻辑)的模型检测问题是固定参数易解的.由于不同逻辑的表达能力不同,不同图类上的模型检测问题的易解性也有显著的区别,因此探索易解的最大范围也是算法元定理研究的重要课题.研究表明,一阶逻辑模型检测问题的易解性与图的稀疏性密切关联.经过数十年的努力,目前学界对于稀疏图类的认识已经较为成熟,近年的研究重心逐渐转向一些良构的稠密图类,研究也面临着更多的挑战.目前在稠密图类上已经得到了若干深刻的算法元定理,相关的探索仍在继续.将全局性地介绍算法元定理领域的发展,旨在为国内的相关研究提供一些线索和助力.Many computational problems on graphs are NP hard,so a natural strategy is to restrict them to some special graphs.This approach has seen many successes in the last few decades,and many efficient algorithms have been designed for problems on graph classes including graphs of bounded degree,bounded tree-width,and planar graphs,to name a few.As a matter of fact,many such algorithmic results can be understood in the framework of the so-called algorithmic meta-theorems.They are general results that provide efficient algorithms for decision problems of logic properties on structural graphs,which are also known as model-checking problems.Most existing algorithmic meta-theorems rely on modern structural graph theory,and they are often concerned with fixed-parameter tractable algorithms,i.e.,efficient algorithms in the sense of parameterized complexity.On many well-structured graphs,the modelchecking problems for some natural logics,e.g.,first-order logic and monadic second-order logic,turn out to be fixed-parameter tractable.Due to varying expressive power,the tractability of the model-checking problems of those logics have huge differences as far as the underlying graph classes are concerned.Therefore,understanding the maximum graph classes that admit efficient model-checking algorithms is a central question for algorithmic meta-theorems.For example,it has been long known that efficient model-checking of firstorder logic is closely related to the sparsity of input graphs.After decades of efforts,our understanding of sparse graphs are fairly complete now.So much of the current research has been focused on well-structured dense graphs,where challenging open problems are abundant.Already there are a few deep algorithmic meta-theorems proved for dense graph classes,while the research frontier is still expanding.This survey aims to give an overview of the whole area in order to provide impetus of the research of algorithmic meta-theorem in China.

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

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]