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.