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 presents the first combinatorial characterizations of monadically dependent graph classes, leading to a dichotomy for these classes. The key results are: 1. **Flip-Breakability**: A graph class is monadically dependent if and only if it is flip-breakable. Flip-breakability is a Ramsey-like property that guarantees the existence of two large subsets of vertices that are strongly separated in some k-flip of the graph. 2. **Forbidden Induced Subgraphs**: A graph class is monadically dependent if and only if it avoids certain induced subgraphs, including flipped star, clique, and half-graph r-crossings, and comparability grids. This characterization generalizes previous results for nowhere dense and monadically stable classes. 3. **Algorithmic Implications**: The results imply that first-order model checking is AW[*]-hard on every hereditary graph class that is monadically independent. This resolves one half of the conjecture that a hereditary graph class is monadically dependent if and only if its first-order model checking problem is fixed-parameter tractable. 4. **Generalization to Binary Structures**: The results are extended to binary structures, showing that monadically dependent classes of binary structures can be characterized by flip-breakability. The paper also discusses the relationship between flip-breakability and other notions like uniform quasi-wideness, flip-flatness, and bounded twin-width. It shows that flip-breakability generalizes these concepts and provides a unified framework for understanding tractability in graph classes. The results have implications for both algorithmic and combinatorial theory, and they contribute to the broader goal of unifying sparsity theory, twin-width theory, and stability theory into a single theory of tractability.This paper presents the first combinatorial characterizations of monadically dependent graph classes, leading to a dichotomy for these classes. The key results are: 1. **Flip-Breakability**: A graph class is monadically dependent if and only if it is flip-breakable. Flip-breakability is a Ramsey-like property that guarantees the existence of two large subsets of vertices that are strongly separated in some k-flip of the graph. 2. **Forbidden Induced Subgraphs**: A graph class is monadically dependent if and only if it avoids certain induced subgraphs, including flipped star, clique, and half-graph r-crossings, and comparability grids. This characterization generalizes previous results for nowhere dense and monadically stable classes. 3. **Algorithmic Implications**: The results imply that first-order model checking is AW[*]-hard on every hereditary graph class that is monadically independent. This resolves one half of the conjecture that a hereditary graph class is monadically dependent if and only if its first-order model checking problem is fixed-parameter tractable. 4. **Generalization to Binary Structures**: The results are extended to binary structures, showing that monadically dependent classes of binary structures can be characterized by flip-breakability. The paper also discusses the relationship between flip-breakability and other notions like uniform quasi-wideness, flip-flatness, and bounded twin-width. It shows that flip-breakability generalizes these concepts and provides a unified framework for understanding tractability in graph classes. The results have implications for both algorithmic and combinatorial theory, and they contribute to the broader goal of unifying sparsity theory, twin-width theory, and stability theory into a single theory of tractability.
Reach us at info@study.space