Reducing CMSO model checking to highly connected graphs

DOI10.4230/LIPIcs.ICALP.2018.135zbMath1499.68203arXiv1802.01453OpenAlexW2964266750MaRDI QIDQ5002822

M. S. Ramanujan, Saket Saurabh, Daniel Lokshtanov, Meirav Zehavi

Publication date: 28 July 2021

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

zbMATH Keywords

model checkingfixed-parameter tractabilityrecursive understanding

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Logic in computer science (03B70) Specification and verification (program logics, model checking, etc.) (68Q60) Parameterized complexity, tractability and kernelization (68Q27)

Related Items

A Fixed-Parameter Tractable Algorithm for Elimination Distance to Bounded Degree Graphs, Distance from triviality 2.0: hybrid parameterizations, Parameterized analysis and crossing minimization problems, FPT algorithms to compute the elimination distance to bipartite graphs and more, Finding connected secluded subgraphs, Deletion to scattered graph classes. I: Case of finite number of graph classes, Path-contractions, edge deletions and connectivity preservation, Parameterized Complexity of Multi-Node Hubs, Parameterized complexity of multi-node hubs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
• Parameterized algorithms for min-max multiway cut and list digraph homomorphism
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Fixed-Parameter Tractability, Definability, and Model-Checking
• A Parameterized Algorithm for Mixed-Cut
• (Meta) Kernelization
• Designing FPT Algorithms for Cut Problems Using Randomized Contractions
• Deciding first-order properties of locally tree-decomposable structures
• Easy problems for tree-decomposable graphs
• Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
• FO Model Checking of Interval Graphs
• The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
• Model checking existential logic on partially ordered sets
• Strong Parameterized Deletion: Bipartite Graphs
• Deciding First-Order Properties of Nowhere Dense Graphs
• Testing first-order properties for subclasses of sparse graphs
• Finding topological subgraphs is fixed-parameter tractable
• The Minimum k-way Cut of Bounded Size is Fixed-Parameter Tractable
• Parameterized Algorithms
• Faster Existential FO Model Checking on Posets