Monadically dependent graphs have nearly limited merge-width measures
Monadically Dependent Graph Classes Have Almost Bounded Merge-Width
Discrete MathematicsData Structures and AlgorithmsLogic in Computer Science
Summary
The paper looks at special groups of graphs called monadically dependent graph classes, which avoid being too complex in a specific logical way. The authors prove these graphs can be described using a method called merge-width that is almost bounded, meaning it doesn’t grow too large. They also provide an algorithm to find these descriptions efficiently. This finding helps with understanding how to quickly check logical properties on such graphs in future work.
What this means in practice
- •For algorithm engineers: Design algorithms for efficiently processing monadically dependent graph classes using almost bounded merge-width decompositions.
- •For database system designers: Optimize query evaluation for data modeled by graphs that fit monadically dependent classes using new structural graph measures.
A theory result. No direct application yet.
Authors
Jan Dreier, Nikolas Mählmann, Michał Pilipczuk, Szymon Toruńczyk
Abstract
A graph class $\mathcal{C}$ is monadically dependent if one cannot interpret all graphs in vertex-colored graphs from $\mathcal{C}$ using a fixed formula of first-order logic. We prove that every monadically dependent graph class has almost bounded merge-width, thereby confirming a conjecture of the first and the last author [STOC '25]. Our proof is algorithmic and the witnessing decompositions in the form of merge sequences can be computed in nearly-cubic time. This is a step towards the proof of fixed-parameter tractability of model checking first-order logic on monadically dependent graph classes, which is achieved in a companion paper.