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

上海交通大学

作者简介:

通讯作者:

中图分类号:

基金项目:


Model-Checking Problem on Well-Structured Graph Classes
Author:
Affiliation:

Shanghai Jiao Tong University

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.

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

京公网安备 11040202500063号