paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Graphs of unbounded linear cliquewidth must transduce all trees

具有无界线性团宽的图必然可转导所有树
LICS 2025 40th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)2025匹配度 1/10 · 论文属于结构图论与逻辑/自动机方向，研究线性团宽与MSO转导，而用户研究画像聚焦于程序分析、LLM/Agent与静态分析/形式化验证的交叉，二者几乎没有直接关联。引用 0 inbox
Mikołaj Bojanczyk, Pierre Ohlmann
逻辑与自动机
crossref: 2026-09-12

AI 速览

一句话：证明图类若线性团宽无界，则存在固定 MSO 转导可由其生成所有树，将路径宽度定理推广到稠密图。

路径宽度定理指出，若一个图类的路径宽度无界，则该类包含所有树作为图子式。本文为稠密图给出类似刻画：若一个图类的线性团宽（linear cliquewidth）无界，则存在一个固定的 MSO 转导，它能从该类中的图生成所有树。作者通过 MSO 转导与线性团宽的结构性质进行证明，表明线性团宽无界同样会导致可由固定逻辑转换产生全部树。该结果将仅适用于稀疏图的路径宽度/图子式框架推广到稠密图与 MSO 转导框架。

问题
如何为稠密图类建立类似路径宽度定理的刻画：路径宽度无界蕴含包含所有树作为图子式。
方法
使用 MSO 转导与线性团宽的结构性质，证明线性团宽无界的图类能通过某个固定 MSO 转导生成所有树。
评估
以数学证明给出一般性定理，不涉及实验评估。
原文摘要（Abstract）

The Pathwidth Theorem states that if a class of graphs has unbounded pathwidth, then it contains all trees as graph minors. We prove a similar result for dense graphs: if a class of graphs has unbounded linear cliquewidth, then it can produce all trees via some fixed MSO transduction.

链接与引用

DOI 原文 · PDF（开放获取） ·

BibTeX 
@inproceedings{paperbot8660,
  title = {Graphs of unbounded linear cliquewidth must transduce all trees},
  author = {Mikołaj Bojanczyk and Pierre Ohlmann},
  booktitle = {LICS},
  year = {2025},
  doi = {10.1109/lics65433.2025.00058}
}