On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic

DOI10.1016/S0166-218X(00)00221-3zbMath0972.05023OpenAlexW2109716789WikidataQ126582646 ScholiaQ126582646MaRDI QIDQ5928867

Udi Rotics, Bruno Courcelle, Johann A. Makowsky

Publication date: 9 November 2001

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0166-218x(00)00221-3

zbMATH Keywords

combinatorial enumeration fixed parameter complexity monadic second-order logic treewidth

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

On finding short resolution refutations and small unsatisfiable subsets, The monadic second-order logic of graphs. XIV: Uniformly sparse graphs and edge set quantifica\-tions., Algorithms for vertex-partitioning problems on graphs with fixed clique-width., The parametrized complexity of knot polynomials, Efficient computation of permanents, with applications to boson sampling and random matrices, Community Structure Inspired Algorithms for SAT and #SAT, Harary polynomials, Backdoors to Satisfaction, A Graph Polynomial for Independent Sets of Bipartite Graphs, The relative clique-width of a graph, Model counting for CNF formulas of bounded modular treewidth, Combinatorics of TCP reordering, On spectra of sentences of monadic second order logic with counting, Courcelle's theorem for triangulations, Inductive computations on graphs defined by clique-width expressions, Algorithmic uses of the Feferman-Vaught theorem, Satisfiability of acyclic and almost acyclic CNF formulas, A SAT Approach to Clique-Width, The complexity of approximating bounded-degree Boolean \(\#\)CSP, Algorithms for Propositional Model Counting, On the expressive power of CNF formulas of bounded tree- and clique-width, Complexity and Algorithms for Well-Structured k-SAT Instances, On the Expressive Power of Permanents and Perfect Matchings of Matrices of Bounded Pathwidth/Cliquewidth (Extended Abstract), Farrell polynomials on graphs of bounded tree width, Tree-width and the monadic quantifier hierarchy., A survey of parameterized algorithms and the complexity of edge modification, An efficient tree decomposition method for permanents and mixed discriminants, Query efficient implementation of graphs of bounded clique-width, Algorithmic aspects of switch cographs, Satisfiability, branch-width and Tseitin tautologies, Fast evaluation of interlace polynomials on graphs of bounded treewidth, Unnamed Item, Complexity and approximability of the cover polynomial, Clique-width of countable graphs: A compactness property., The enumeration of vertex induced subgraphs with respect to the number of components, On the Expressive Power of Planar Perfect Matching and Permanents of Bounded Treewidth Matrices, Solving \#SAT using vertex covers, An Extended Tree-Width Notion for Directed Graphs Related to the Computation of Permanents, New width parameters for SAT and \#SAT, Circle graphs and monadic second-order logic, Linear-Time Algorithms for Graphs of Bounded Rankwidth: A Fresh Look Using Game Theory, Characterizing Arithmetic Circuit Classes by Constraint Satisfaction Problems, Counting truth assignments of formulas of bounded tree-width or clique-width, Efficient computation of the characteristic polynomial of a tree and related tasks, An extended tree-width notion for directed graphs related to the computation of permanents, The modular decomposition of countable graphs. Definition and construction in monadic second-order logic, A Practical Approach to Courcelle's Theorem, GETGRATS, Coloured Tutte polynomials and Kauffman brackets for graphs of bounded tree width, Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable, Satisfactory graph partition, variants, and generalizations, Algorithms for propositional model counting, Bounded treewidth as a key to tractability of knowledge representation and reasoning, A logician's view of graph polynomials, On the expressive power of permanents and perfect matchings of matrices of bounded pathwidth/cliquewidth, Connection Matrices for MSOL-Definable Structural Invariants, Unnamed Item, Computing LOGCFL certificates, Linear Recurrence Relations for Graph Polynomials, Graph classes and the switch Markov chain for matchings, Coalitional games induced by matching problems: complexity and islands of tractability for the Shapley value, From a zoo to a zoology: Towards a general theory of graph polynomials, Semantic Equivalence of Graph Polynomials Definable in Second Order Logic, Spanning tree constrained determinantal point processes are hard to (approximately) evaluate, The Maximum Time of 2-neighbour Bootstrap Percolation in Grid Graphs and Parametrized Results, Integrating and Sampling Cuts in Bounded Treewidth Graphs, Chordal bipartite graphs of bounded tree- and clique-width, The monadic second-order logic of graphs. XIII: Graph drawings with edge crossings, Complexity of abstract argumentation under a claim-centric view, Parameterized counting problems, Unnamed Item, Edge dominating set and colorings on graphs with fixed clique-width, Counting \(H-\)colorings of partial \(k-\)trees

Uses Software

Leibniz

Cites Work