Extended MSO model checking via small vertex integrity
From MaRDI portal
Publication:6185940
Abstract: We study the model checking problem of an extended with local and global cardinality constraints, called , introduced recently by Knop, Kouteck'{y}, Masav{r}'{i}k, and Toufar [Log. Methods Comput. Sci., 15(4), 2019]. We show that the problem is fixed-parameter tractable parameterized by vertex integrity, where vertex integrity is a graph parameter standing between vertex cover number and treedepth. Our result thus narrows the gap between the fixed-parameter tractability parameterized by vertex cover number and the W[1]-hardness parameterized by treedepth.
Cites work
- scientific article; zbMATH DE number 5917571 (Why is no real title available?)
- scientific article; zbMATH DE number 5127204 (Why is no real title available?)
- scientific article; zbMATH DE number 4053662 (Why is no real title available?)
- scientific article; zbMATH DE number 2076807 (Why is no real title available?)
- scientific article; zbMATH DE number 2104820 (Why is no real title available?)
- A partial k-arboretum of graphs with bounded treewidth
- A survey on alliances and related parameters in graphs
- Algorithmic meta-theorems
- Algorithmic meta-theorems for restrictions of treewidth
- An algorithmic framework for locally constrained homomorphisms
- An application of simultaneous diophantine approximation in combinatorial optimization
- Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
- Bin packing with fixed number of bins revisited
- Capacitated Domination and Covering: A Parameterized Perspective
- Characterizing the easy-to-find subgraphs from the viewpoint of polynomial-time algorithms, kernels, and Turing kernels
- Defective colorings of graphs in surfaces: Partitions into subgraphs of bounded valency
- Defensive alliances in graphs of bounded treewidth
- Easy problems for tree-decomposable graphs
- Expanding the expressive power of monadic second-order logic on restricted graph classes
- Exploring the gap between treedepth and vertex cover through vertex integrity
- Fair edge deletion problems
- Graph Layout Problems Parameterized by Vertex Cover
- Graph structure and monadic second-order logic. A language-theoretic approach
- Grundy distinguishes treewidth from pathwidth
- Integer Programming with a Fixed Number of Variables
- Kernelizing MSO properties of trees of fixed height, and some consequences
- Linear time solvable optimization problems on graphs of bounded clique-width
- Methods for algorithmic meta theorems
- Minkowski's Convex Body Theorem and Integer Programming
- Monadic second order logic on graphs with local cardinality constraints
- On structural parameterizations of the bounded-degree vertex deletion problem
- On the complexity of some colorful problems parameterized by treewidth
- Parameterized (approximate) defective coloring
- Parameterized algorithms
- Parameterized complexity of coloring problems: treewidth versus vertex cover
- Parameterized complexity of fair vertex evaluation problems
- Safe number and integrity of graphs
- Safe set problem on graphs
- Subgraph isomorphism on graph classes that exclude a substructure
- The complexity landscape of decompositional parameters for ILP: programs with few global variables and constraints
- The complexity of first-order and monadic second-order logic revisited
- The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics
- What makes equitable connected partition easy
- When trees grow low: shrubs and fast \(\mathrm{MSO}_{1}\)
This page was built for publication: Extended MSO model checking via small vertex integrity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6185940)
