良构图类上的模型检测问题
CSTR:
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

TP311

基金项目:

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


Model-checking Problem on Well-structured Graph Classes
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

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

    Abstract:

    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 model-checking 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 first-order 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.

    参考文献
    相似文献
    引证文献
引用本文

刘国航,陈翌佳.良构图类上的模型检测问题.软件学报,,():1-24

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2023-07-31
  • 最后修改日期:2023-12-14
  • 录用日期:
  • 在线发布日期: 2024-06-20
  • 出版日期:
文章二维码
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号