On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic |
| |
Affiliation: | 1. LabRI, Université de Bordeaux, Talence, France;2. Department of Computer Science, Technion-Israel Institute of Technology, Haifa, Israel;3. Department of Computer Science, University of Toronto, Toronto, Canada |
| |
Abstract: | We discuss the parametrized complexity of counting and evaluation problems on graphs where the range of counting is definable 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 quantification. Such quantifications are allowed in the case of graphs with bounded tree-width. As applications we discuss in detail how this affects the parametrized complexity of the permanent and the hamiltonian of a matrix, and more generally, various generating functions of MSOL definable graph properties. Finally, our results are also applicable to SAT and ♯SAT. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|