Flip-Breakability: A Combinatorial Dichotomy for Monadically Dependent Graph Classes

Flip-Breakability: A Combinatorial Dichotomy for Monadically Dependent Graph Classes

27 Mar 2024 | Jan Dreier, Nikolas Mählmann, Szymon Toruńczyk
This paper addresses the conjecture in algorithmic model theory that the model-checking problem for first-order logic is fixed-parameter tractable on a hereditary graph class if and only if the class is *monadically dependent*. The authors provide two combinatorial characterizations of monadically dependent graph classes, leading to a dichotomy theorem. On the structure side, they introduce *flip-breakability*, a Ramsey-theoretic property that generalizes notions like uniform quasi-wideness, flip-flatness, and bounded grid rank. Flip-breakability characterizes monadically dependent classes and is crucial for designing efficient algorithms. On the non-structure side, they list specific *forbidden induced subgraphs* that monadically independent classes must avoid. This result resolves one half of the conjecture: first-order model checking is AW[*]-hard on every hereditary graph class that is monadically independent. Additionally, they show that small, hereditary graph classes with almost bounded twin-width or almost bounded flip-width are monadically dependent. The paper also extends these results to binary structures and discusses the implications for future research, including the potential development of a game characterization of monadic dependence.This paper addresses the conjecture in algorithmic model theory that the model-checking problem for first-order logic is fixed-parameter tractable on a hereditary graph class if and only if the class is *monadically dependent*. The authors provide two combinatorial characterizations of monadically dependent graph classes, leading to a dichotomy theorem. On the structure side, they introduce *flip-breakability*, a Ramsey-theoretic property that generalizes notions like uniform quasi-wideness, flip-flatness, and bounded grid rank. Flip-breakability characterizes monadically dependent classes and is crucial for designing efficient algorithms. On the non-structure side, they list specific *forbidden induced subgraphs* that monadically independent classes must avoid. This result resolves one half of the conjecture: first-order model checking is AW[*]-hard on every hereditary graph class that is monadically independent. Additionally, they show that small, hereditary graph classes with almost bounded twin-width or almost bounded flip-width are monadically dependent. The paper also extends these results to binary structures and discusses the implications for future research, including the potential development of a game characterization of monadic dependence.
Reach us at info@study.space