论文标题
扩展MSO模型通过小顶点完整性检查
Extended MSO Model Checking via Small Vertex Integrity
论文作者
论文摘要
我们研究了带有本地和全球基数约束的扩展$ \ Mathsf {MSO} $的模型检查问题，称为$ \ MathSf {MSO}^{\ Mathsf {\ Mathsf {gl}} _ {\ Mathsf {linsf {lin}} $，最近由Knop，Knop，Knop，kuteck ifectect- koteck masa月夫[\ Masa》（Masa场）介绍。方法计算。 Sci。，15（4），2019年]。我们表明，问题是通过顶点完整性对参数进行参数的固定参数，其中顶点完整性是顶点盖号和TreeDeptth之间的图参数。因此，我们的结果缩小了通过顶点覆盖号参数参数的固定参数障碍与通过TreeDepth参数参数的w [1] hardness之间的差距。
We study the model checking problem of an extended $\mathsf{MSO}$ with local and global cardinality constraints, called $\mathsf{MSO}^{\mathsf{GL}}_{\mathsf{Lin}}$, introduced recently by Knop, Koutecký, Masařík, and Toufar [Log. Methods Comput. Sci., 15(4), 2019]. We show that the problem is fixed-parameter tractable parameterized by vertex integrity, where vertex integrity is a graph parameter standing between vertex cover number and treedepth. Our result thus narrows the gap between the fixed-parameter tractability parameterized by vertex cover number and the W[1]-hardness parameterized by treedepth.
