arXiv preprint ·
Monadically Dependent Graph Classes Have Almost Bounded Merge-Width
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Discrete Mathematics
An Engineering Reading of the Bounded Halting Problem and Observable Properties of a Universal Machine
First-Order Model Checking on Monadically Dependent Graph Classes
Classical and Quantum Logics with Multiple Non-Equivalent and Non-Isomorphic Models
Polyteam logics for quantum contextuality
On the gradient conjecture at infinity: Finite spherical length for gradient trajectories of definable potentials
Get the few papers worth your time in Discrete Mathematics every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.