Simplified algorithmic metatheorems beyond MSO: treewidth and neighborhood diversity

DOI10.1007/978-3-319-68705-6_26zbMath1484.68072arXiv1703.00544OpenAlexW2593126173WikidataQ62044471 ScholiaQ62044471MaRDI QIDQ1687933

Tomáš Toufar, Dušan Knop, Martin Koutecký, Tomáš Masařík

Publication date: 4 January 2018

Full work available at URL: https://arxiv.org/abs/1703.00544

zbMATH Keywords

treewidthparameterized complexityneighborhood diversitymetatheoremMSO extensions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Specification and verification (program logics, model checking, etc.) (68Q60) Higher-order logic (03B16)

Related Items (15)

Iterated Type Partitions ⋮ Parameterized complexity of immunization in the threshold model ⋮ Parameterized complexity of fair feedback vertex set problem ⋮ An approval-based model for single-step liquid democracy ⋮ On the minimum cycle cover problem on graphs with bounded co-degeneracy ⋮ Simplified algorithmic metatheorems beyond MSO: treewidth and neighborhood diversity ⋮ Immunization in the threshold model: a parameterized complexity study ⋮ Parameterized complexity for iterated type partitions and modular-width ⋮ Spanning trees with few branch vertices in graphs of bounded neighborhood diversity ⋮ Extended MSO model checking via small vertex integrity ⋮ Combinatorial \(n\)-fold integer programming and applications ⋮ Parameterized shifted combinatorial optimization ⋮ Unnamed Item ⋮ Local linear set on graphs with bounded twin cover number ⋮ Approximating max-cut under graph-MSO constraints

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Courcelle's theorem -- a game-theoretic approach
• Complexity of conflict-free colorings of graphs
• On the parameterized complexity of computing balanced partitions in graphs
• Monadic second-order evaluations on tree-decomposable graphs
• Elements of finite model theory.
• Upper and lower bounds for finding connected motifs in vertex-colored graphs
• The monadic second order logic of graphs. VI: On several representations of graphs by relational structures
• Treewidth. Computations and approximations
• Conjunctive-query containment and constraint satisfaction
• Simplified algorithmic metatheorems beyond MSO: treewidth and neighborhood diversity
• Algorithmic meta-theorems for restrictions of treewidth
• The monadic second-order logic of graphs. XIV: Uniformly sparse graphs and edge set quantifica\-tions.
• The complexity of first-order and monadic second-order logic revisited
• Linear time solvable optimization problems on graphs of bounded clique-width
• Parameterized complexity of fair deletion problems
• The graph motif problem parameterized by the structure of the input graph
• Parameterized complexity of distance labeling and uniform channel assignment problems
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Linear Time Algorithms for Happy Vertex Coloring Problems for Trees
• Expanding the Expressive Power of Monadic Second-Order Logic on Restricted Graph Classes
• Monadic datalog over finite structures of bounded treewidth
• On the (Parameterized) Complexity of Recognizing Well-Covered $$(r,\ell )$$ -graphs
• Integer Programming with a Fixed Number of Variables
• Problems Parameterized by Treewidth Tractable in Single Exponential Time: A Logical Approach
• Elections with Few Candidates: Prices, Weights, and Covering Problems
• Treewidth: Characterizations, Applications, and Computations
• Monadic Second Order Logic on Graphs with Local Cardinality Constraints
• A linear time algorithm for finding tree-decompositions of small treewidth
• Extension Complexity, MSO Logic, and Treewidth
• Model Checking Lower Bounds for Simple Graphs
• Parameterized Algorithms
• Extended formulations in combinatorial optimization

This page was built for publication: Simplified algorithmic metatheorems beyond MSO: treewidth and neighborhood diversity