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

作者简介:

通讯作者:

中图分类号:

TP311

基金项目:

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


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

Fund Project:

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

    图上的诸多计算问题都是NP难问题, 因此研究中经常尝试将问题限定在一些具有良好结构的特定图类上. 这类研究在过去的几十年间收获了大量自然图类上的高效算法, 其中很大一部分都能统一到算法元定理框架下. 算法元定理是一类通用的结论, 主要研究模型检测问题, 即在特定结构上判定特定逻辑框架下任意公式的满足性. 现有的算法元定理大多借助结构图论工具研究图的性质, 并且考虑参数复杂性意义下的高效性. 在许多良构的图类上, 一些常见逻辑的模型检测问题具有参数复杂性意义下的高效算法, 即是固定参数易解的. 由于不同逻辑的表达能力不同, 对应的模型检测问题的易解范围也有显著的区别, 探索这些易解范围也是算法元定理研究的重要课题. 研究发现, 一阶逻辑模型检测的易解性与图的稀疏性密切关联. 目前学界对于稀疏图类的认识已经较为成熟, 近年的研究重心逐渐转向一些良构的稠密图类, 研究面临着更多的挑战. 研究表明, 在许多复杂的稠密图类上, 模型检测问题仍有可能是易解的. 对易解范围的探索至今仍在继续, 该领域中仍存在大量的未解问题. 本文将全局性地介绍算法元定理的研究, 旨在为国内的相关研究提供一些线索和助力.

    Abstract:

    Many computational problems on graphs can be attributed to the NP-hard problem, so these problems are often restricted within well-structured graphs. This approach has seen many efficient algorithms in the natural graph class, many of which can be subsumed under the framework of algorithmic meta-theorems. Algorithmic meta-theorems are general results that provide efficient algorithms for model-checking problems, which means the satisfiability of any formula under certain logic frameworks is verified on a specific structure. Most existing algorithmic meta-theorems rely on structural graph theory in studying graph properties and take efficiency under parameterized complexity into consideration. On many well-structured graphs, some model-checking problems with common logics have efficient algorithms under parameterized complexity, in other words, they turn out to be fixed-parameter tractable. Due to the varying expressive power of different logics, the tractability of the corresponding model-checking problems has huge differences Therefore, understanding the tractability is a significant question for algorithmic meta-theorems. Results have shown that the tractability of first-order logic model checking is closely related to the sparsity of input graphs. As the understanding of sparse graphs is fairly complete now, the focus of current research has shifted towards well-structured dense graphs, where challenging problems are abundant. Results show that model-checking problems may be tractable for many complex dense graphs, but many unsolved problems in this field still require further exploration. By giving an overview of the research about algorithmic meta-theorems, this survey aims to offer assistance and momentum to related research 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号