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

Clc Number:

TP311

Fund Project:

  • Article
  • |
  • Figures
  • |
  • Metrics
  • |
  • Reference
  • |
  • Related
  • |
  • Cited by
  • |
  • Materials
  • |
  • Comments
    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.

    Reference
    Related
    Cited by
Get Citation

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

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:July 31,2023
  • Revised:December 14,2023
  • Adopted:
  • Online: June 20,2024
  • Published:
You are the firstVisitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063