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, 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 enumerationfixed parameter complexitymonadic second-order logictreewidth

Mathematics Subject Classification ID

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

Cites Work

• The complexity of computing the permanent
• A linear-time recognition algorithm for \(P_{4}\)-reducible graphs
• Monadic second-order evaluations on tree-decomposable graphs
• Complement reducible graphs
• The monadic theory of order
• A partial k-arboretum of graphs with bounded treewidth
• On the \(p\)-connectedness of graphs---a survey
• Monadic second-order definable graph transductions: a survey
• \(k\)-NLC graphs and polynomial algorithms
• On the complexity of quadratic programming in real number models of computation
• On extended \(P_4\)-reducible and extended \(P_4\)-sparse graphs
• Logical definability of counting functions
• Descriptive complexity of \(\#\)P functions
• Linear time optimization algorithms for \(P_ 4\)-sparse graphs
• Arity and alternation in second-order logic
• Recognition and isomorphism of tree-like \(P_4\)-connected graphs
• Linear time solvable optimization problems on graphs of bounded clique-width
• Upper bounds to the clique width of graphs
• Handle-rewriting hypergraph grammars
• The first order properties of products of algebraic systems
• Easy problems for tree-decomposable graphs
• Modest theory of short chains. I
• A Tutte Polynomial for Coloured Graphs
• Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
• Two Algorithmic Results for the Traveling Salesman Problem
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• Monotone monadic SNP and constraint satisfaction
• ON THE CLIQUE–WIDTH OF GRAPH WITH FEW P₄'S
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

Related Items (77)

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 ⋮ Fast FPT-approximation of branchwidth ⋮ 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 ⋮ How I got to like graph polynomials ⋮ 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 ⋮ On the parameterized intractability of determinant maximization ⋮ Coalitional games induced by matching problems: complexity and islands of tractability for the Shapley value ⋮ Counting on rainbow \(k\)-connections ⋮ 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

This page was built for publication: On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic