On the xed parameter complexity of graph enumeration problems de nable in monadic second-order logic
On the xed parameter complexity of graph enumeration problems de nable in monadic second-order logic
复制标题
一元二阶逻辑中可定义的图枚举问题的固定参数复杂度
DOI：
--
复制
发表时间：
2000
期刊：
影响因子：
--
通讯作者：
U. Roticsc
中科院分区：
文献类型：
--
作者：
B. Courcellea;J. A. Makowskyb;U. Roticsc
本文讨论了一元二阶逻辑（MSOL）中计数范围是可定义的图的计数和求值问题的参数化复杂性。我们表明，有界树的宽度，这些问题是可解的多项式时间。同样适用于有界团宽度的情况下，其中的分解，它建立了对团宽度的限制，可以在多项式时间内计算，并为一元二阶公式表示的问题，没有边集量化。在树宽有界的图的情况下，这样的量化是允许的。作为应用程序，我们详细讨论了这方面如何影响参数化的复杂性的永久性和矩阵的哈密顿量，更一般地说，各种生成函数的MSOL可定义的图形属性。最后，我们的结果也适用于SAT和]SAT。? 2001 Elsevier Science B.V.保留所有权利。
We discuss the parametrized complexity of counting and evaluation problems on graphs where the range of counting is de nable in monadic second-order logic (MSOL). We show that for bounded tree-width these problems are solvable in polynomial time. The same holds for bounded clique width in the cases, where the decomposition, which establishes the bound on the clique-width, can be computed in polynomial time and for problems expressible by monadic second-order formulas without edge set quanti cation. Such quanti cations are allowed in the case of graphs with bounded tree-width. As applications we discuss in detail how this a ects the parametrized complexity of the permanent and the hamiltonian of a matrix, and more generally, various generating functions of MSOL de nable graph properties. Finally, our results are also applicable to SAT and ]SAT . ? 2001 Elsevier Science B.V. All rights reserved.