paperbot · PL 论文追踪

全部论文 待读 收藏

P2 On Supergraphs Satisfying CMSO Properties

论满足 CMSO 性质的母图
LMCS vol.Volume 17, Issue 42021匹配度 1/10 · 该论文研究 CMSO 逻辑、有界树宽超图构造与图补全的固定参数算法,属于图论与逻辑/自动机理论,与用户关注的静态分析、LLM/Agent、浮点程序分析及贝叶斯程序分析均无直接关联。仅在形式化方法背景上有非常遥远的联系,不匹配核心研究方向。引用 1 inbox
Mateus de Oliveira Oliveira
crossref: 2026-09-10

AI 速览

一句话:给出构造性元定理,可在参数化时间内判定图是否存在满足 CMSO 性质且有界树宽的母图,并用于图补全问题。

本文研究图补全问题:给定 CMSO 句子 φ、整数 t 以及最大度数至多 Δ 的连通图 G,判定是否存在包含 G 且树宽至多 t 的母图 G′ 使 G′ ⊨ φ。作者通过构造性证明给出算法 A,其运行时间为 f(|φ|,t)·2^{O(Δ·t)}·|G|^{O(t)},其中 f 为可计算函数。作为应用,该元定理可判定 G 是否存在直径至多 d 的平面母图,并证明固定 k 时 k-外平面母图直径判定关于 d 强一致固定参数可处理。结果还可推广:直径参数可替换为任意收缩封闭且有效 CMSO 可定义的参数(如顶点覆盖数、支配数等),平面性可放宽到有界亏格与有界局部树宽。

问题
给定 CMSO 公式、树宽上界 t 和最大度数有界的连通图 G,判定 G 是否可扩展为满足该 CMSO 性质且树宽不超过 t 的母图。
方法
构造性证明一个算法元定理,结合树宽与 CMSO 的自动机方法及图补全技术,给出参数化算法和运行时间界。
评估
通过推导平面母图直径、k-外平面母图直径等图补全问题的算法来展示元定理的应用,并推广到收缩封闭有效 CMSO 可定义参数、有界亏格和有界局部树宽。
原文摘要(Abstract)

Let CMSO denote the counting monadic second order logic of graphs. We give a constructive proof that for some computable function $f$, there is an algorithm $\mathfrak{A}$ that takes as input a CMSO sentence $\varphi$, a positive integer $t$, and a connected graph $G$ of maximum degree at most $\Delta$, and determines, in time $f(|\varphi|,t)\cdot 2^{O(\Delta \cdot t)}\cdot |G|^{O(t)}$, whether $G$ has a supergraph $G'$ of treewidth at most $t$ such that $G'\models \varphi$. The algorithmic metatheorem described above sheds new light on certain unresolved questions within the framework of graph completion algorithms. In particular, using this metatheorem, we provide an explicit algorithm that determines, in time $f(d)\cdot 2^{O(\Delta \cdot d)}\cdot |G|^{O(d)}$, whether a connected graph of maximum degree $\Delta$ has a planar supergraph of diameter at most $d$. Additionally, we show that for each fixed $k$, the problem of determining whether $G$ has an $k$-outerplanar supergraph of diameter at most $d$ is strongly uniformly fixed parameter tractable with respect to the parameter $d$. This result can be generalized in two directions. First, the diameter parameter can be replaced by any contraction-closed effectively CMSO-definable parameter $\mathbf{p}$. Examples of such parameters are vertex-cover number, dominating number, and many other contraction-bidimensional parameters. In the second direction, the planarity requirement can be relaxed to bounded genus, and more generally, to bounded local treewidth.

链接与引用

DOI 原文 · PDF(开放获取) ·

BibTeX
@article{paperbot1261,
  title = {On Supergraphs Satisfying CMSO Properties},
  author = {Mateus de Oliveira Oliveira},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 17, Issue 4},
  year = {2021},
  doi = {10.46298/lmcs-17(4:14)2021}
}