Can I read A Logic-based Algorithmic Meta-theorem for Mim-width on EtoBox?

A Logic-based Algorithmic Meta-theorem for Mim-width by Bergougnoux, Benjamin; Dreier, Jan; Jaffke, Lars is a scholarly article available to read on EtoBox.

What is A Logic-based Algorithmic Meta-theorem for Mim-width about?

We introduce a logic called distance neighborhood logic with acyclicity and connectivity constraints ($\mathsf{A\&C~DN}$ for short) which extends existential $\mathsf{MSO_1}$ with predicates for querying neighborhoods of vertex sets and for verifying connectivity and acyclicity of vertex sets in various powers of a graph. Building upon [Bergougnoux and Kant\'e, ESA 2019; SIDMA 2021], we show that the model checking problem for every fixed $\mathsf{A\&C~DN}$ formula is solvable in $n^{O(w)}$ time when the input graph is given together with a branch decomposition of mim-width $w$. Nearly all problems that are known to be solvable in polynomial time given a branch decomposition of constant mim-width can be expressed in this framework. We add several natural problems to this list, including problems asking for diverse sets of solutions. Our model checking algorithm is efficient whenever the given branch decomposition of the input graph has small index in terms of the $d$-neighborhood equivalence [Bui-Xuan, Telle, and Vatshelle, TCS 2013]. We therefore unify and extend known algorithms for tree-width, clique-width and rank-width. Our algorithm has a single-exponential dependence on thes

Author

Bergougnoux, Benjamin; Dreier, Jan; Jaffke, Lars

Published

2022

Language

EN