On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
type: Item
instance of: scholarly article
title: On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
zbMATH Open document ID: 0972.05023
DOI: 10.1016/S0166-218X(00)00221-3
author: Johann A. Makowsky
author: Udi Rotics
author: Bruno Courcelle
published in: Discrete Applied Mathematics
publication date: 2001-11-09T00:00:00Z
review text: 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.
reviewed by: Hans L. Bodlaender
Mathematics Subject Classification ID: 05C30
Mathematics Subject Classification ID: 03B15
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 1584464
zbMATH Keywords: fixed parameter complexity
zbMATH Keywords: combinatorial enumeration
zbMATH Keywords: treewidth
zbMATH Keywords: monadic second-order logic
describes a project that uses: Leibniz
MaRDI profile type: Publication
cites work: Easy problems for tree-decomposable graphs
cites work: Recognition and isomorphism of tree-like \(P_4\)-connected graphs
cites work: On the \(p\)-connectedness of graphs---a survey
cites work: Two Algorithmic Results for the Traveling Salesman Problem
cites work: Q4291429
cites work: Q4699283
cites work: A partial k-arboretum of graphs with bounded treewidth
cites work: Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
cites work: Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
cites work: A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
cites work: A Tutte Polynomial for Coloured Graphs
cites work: Q4331740
cites work: Logical definability of counting functions
cites work: Q4508369
cites work: Complement reducible graphs
cites work: Monadic second-order definable graph transductions: a survey
cites work: Q4852905
cites work: Handle-rewriting hypergraph grammars
cites work: Q4232773
cites work: Linear time solvable optimization problems on graphs of bounded clique-width
cites work: Monadic second-order evaluations on tree-decomposable graphs
cites work: Upper bounds to the clique width of graphs
cites work: Q3999150
cites work: Q4850061
cites work: Monotone monadic SNP and constraint satisfaction
cites work: The first order properties of products of algebraic systems
cites work: Q4198056
cites work: Q3836509
cites work: On extended \(P_4\)-reducible and extended \(P_4\)-sparse graphs
cites work: Q4717945
cites work: Modest theory of short chains. I
cites work: Q4003410
cites work: Q4843270
cites work: A linear-time recognition algorithm for \(P_{4}\)-reducible graphs
cites work: Linear time optimization algorithms for \(P_ 4\)-sparse graphs
cites work: Q4385525
cites work: Q2753688
cites work: Q4502591
cites work: Arity and alternation in second-order logic
cites work: ON THE CLIQUE–WIDTH OF GRAPH WITH FEW P4'S
cites work: On the complexity of quadratic programming in real number models of computation
cites work: Q4298260
cites work: Descriptive complexity of \(\#\)P functions
cites work: The monadic theory of order
cites work: Q4004142
cites work: Q4705311
cites work: The complexity of computing the permanent
cites work: \(k\)-NLC graphs and polynomial algorithms
full work available at URL: s0166-218x(00)00221-3
OpenAlex ID: W2109716789
Wikidata QID: Q126582646
Recommended article: Graph decompositions definable in monadic second-order logic
Recommended article: The monadic second-order logic of graphs. V: On closing the gap between definability and recognizability
Recommended article: Monadic second order logic on graphs with local cardinality constraints
Recommended article: Monadic Second Order Logic on Graphs with Local Cardinality Constraints
Recommended article: The monadic second-order logic of graphs. IV: Definability properties of equational graphs
Recommended article: The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
Recommended article: Monadic Second-Order Logic for Graphs: Algorithmic and Language Theoretical Applications

On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic (Recommended article)
Recommended article: Q4205068
Similarity Score: 0.9105115
Recommender Run: Recommender Run 3

On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic (Recommended article)
Recommended article: The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
Similarity Score: 0.90994966
Recommender Run: Recommender Run 3

On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic (Recommended article)
Recommended article: The monadic second-order logic of graphs, II: Infinite graphs of bounded width
Similarity Score: 0.9072137
Recommender Run: Recommender Run 3