On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic (Q5928867): Difference between revisions

This paper considers counting and evaluation problems on graphs, where the range of counting is definable in monadic second-order logic. In this paper, the graphs are restricted to those with some upper bound on the treewidth. Problems that are otherwise computationally intractable become polynomial time solvable with this restriction. Similar results are given when the clique width is bounded, but now we must have in addition some algorithm that finds appropriate clique decompositions, and no edge set quantification is allowed in the monadic second-order logic formulas. Several applications of the theory are discussed.