Simplified algorithmic metatheorems beyond MSO: treewidth and neighborhood diversity
From MaRDI portal
DOI10.1007/978-3-319-68705-6_26zbMath1484.68072arXiv1703.00544WikidataQ62044471 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
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
68Q60: Specification and verification (program logics, model checking, etc.)
03B16: Higher-order logic
Related Items
Unnamed Item, Iterated Type Partitions, Parameterized shifted combinatorial optimization, On the minimum cycle cover problem on graphs with bounded co-degeneracy, 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, Simplified algorithmic metatheorems beyond MSO: treewidth and neighborhood diversity, Local linear set on graphs with bounded twin cover number, Parameterized complexity of immunization in the threshold model, Combinatorial \(n\)-fold integer programming and applications, Approximating max-cut under graph-MSO constraints, Parameterized complexity of fair feedback vertex set problem, An approval-based model for single-step liquid democracy
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
