Extended MSO model checking via small vertex integrity
From MaRDI portal
Publication:6185940
DOI10.1007/S00453-023-01161-9arXiv2202.08445OpenAlexW4385667336MaRDI QIDQ6185940FDOQ6185940
Authors: Tatsuya Gima, Yota Otachi 
Publication date: 9 January 2024
Published in: Algorithmica (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/2202.08445
Cites Work
- A partial k-arboretum of graphs with bounded treewidth
- Algorithmic meta-theorems for restrictions of treewidth
- Linear time solvable optimization problems on graphs of bounded clique-width
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Integer Programming with a Fixed Number of Variables
- Graph structure and monadic second-order logic. A language-theoretic approach
- Easy problems for tree-decomposable graphs
- Defective colorings of graphs in surfaces: Partitions into subgraphs of bounded valency
- Minkowski's Convex Body Theorem and Integer Programming
- Parameterized algorithms
- When trees grow low: shrubs and fast \(\mathrm{MSO}_{1}\)
- Algorithmic meta-theorems
- Title not available (Why is that?)
- Title not available (Why is that?)
- Kernelizing MSO properties of trees of fixed height, and some consequences
- Characterizing the easy-to-find subgraphs from the viewpoint of polynomial-time algorithms, kernels, and Turing kernels
- Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics
- An application of simultaneous diophantine approximation in combinatorial optimization
- The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
- Graph Layout Problems Parameterized by Vertex Cover
- Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
- The complexity of first-order and monadic second-order logic revisited
- Safe set problem on graphs
- Title not available (Why is that?)
- Bin packing with fixed number of bins revisited
- Subgraph isomorphism on graph classes that exclude a substructure
- On the complexity of some colorful problems parameterized by treewidth
- Title not available (Why is that?)
- Capacitated Domination and Covering: A Parameterized Perspective
- Parameterized complexity of coloring problems: treewidth versus vertex cover
- Methods for algorithmic meta theorems
- Expanding the expressive power of monadic second-order logic on restricted graph classes
- What makes equitable connected partition easy
- Defensive alliances in graphs of bounded treewidth
- Title not available (Why is that?)
- A survey on alliances and related parameters in graphs
- Fair edge deletion problems
- Safe number and integrity of graphs
- Parameterized complexity of fair vertex evaluation problems
- Parameterized (approximate) defective coloring
- Grundy distinguishes treewidth from pathwidth
- On structural parameterizations of the bounded-degree vertex deletion problem
- The complexity landscape of decompositional parameters for ILP: programs with few global variables and constraints
- Monadic second order logic on graphs with local cardinality constraints
- Exploring the gap between treedepth and vertex cover through vertex integrity
- An algorithmic framework for locally constrained homomorphisms
Cited In (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)
