Sparsity. Graphs, Structures, and Algorithms

Description

Cover Sparsity Graphs, Structures, and Algorithms Preface Contents List of Symbols Presentation Chapter 1 Introduction Chapter 2 A Few Problems 2.1 Breaking a Mesh 2.2 Forging Alliances 2.3 Are Symmetries Frequent? 2.4 Large Matchings on a Torus 2.5 Homomorphism Dualities The Theory Chapter 3 Prolegomena 3.1 Graphs 3.2 Average Degree and Minimum Degree 3.3 Graph Degeneracy and Orientations 3.4 Girth 3.5 Minors 3.6 Width, Separators and Expanders 3.7 Homomorphisms 3.8 Relational Structures and First-Order Logic 3.8.1 Relational Structures 3.8.2 First-Order Logic 3.8.3 Derived Graphs 3.8.4 Ehrenfeucht-Fraïssé Games 3.8.5 Interpretation 3.9 Ramsey Theory 3.10 Graph Parameters 3.11 Computational complexity Exercises Chapter 4 Measuring Sparsity 4.1 Basic Definitions 4.2 Shallow Minors 4.3 Shallow Topological Minors 4.4 Grads and Top-Grads 4.5 Polynomial Equivalence of Grads and Top-Grads 4.6 Relation with Chromatic Number 4.7 Stability of Grads by Lexicographic Product 4.8 Shallow Immersions 4.9 Generalized Coloring Numbers Exercises Chapter 5 Classes and Their Classification 5.1 Operations on Classes and Resolutions 5.1.1 Class Suprema and Class Limits 5.1.2 Class Operations 5.1.3 Class Resolutions 5.1.4 Topological Parameters 5.2 Logarithmic Density and Concentration 5.3 Classification of Classes by Clique Minors 5.4 Classification by Density—Trichotomy of Classes 5.5 Classes with Bounded Expansion 5.6 Classes with Locally Bounded Expansion 5.7 A Historical Note on Connection to Model Theory 5.8 Classes of Relational Structures Exercises Chapter 6 Bounded Height Trees and Tree-Depth 6.1 Definitions and Basic Properties 6.2 Tree-Depth, Minors and Paths 6.3 Compact Elimination Trees and Weak-Coloring 6.4 Tree-Depth, Tree-Width and Vertex Separators 6.5 Centered Colorings 6.6 Cycle Rank 6.7 Games and a Min-Max Formula for Tree-Depth 6.8 Reductions and Finiteness 6.9 Ehrenfeucht-Fraïssé Games 6.10 Well Quasi-orders 6.11 The Homomorphism Quasi-order Exercises Chapter 7 Decomposition 7.1 Motivation, Low Tree-Width and Low Tree-Depth 7.2 Low Tree-Depth Coloring and p-Centered Colorings 7.3 Transitive Fraternal Augmentation 7.4 Fraternal Augmentations of Graphs 7.5 The Weak-Coloring Approach Exercises Chapter 8 Independence 8.1 How Wide is a Class? 8.2 Wide Classes 8.3 Finding d-Independent Sets in Graphs 8.3.1 Finding 1-Independent Sets in Graphs 8.3.2 Finding a 2-Independent Set in a 1-Independent Set 8.3.3 Finding a (2r+1)-independent Set in a 2r-independent Set 8.3.4 Finding a (2r+2)-Independent Set in a (2r+1)-Independent Set 8.4 Quasi-Wide Classes 8.5 Almost Wide Classes 8.6 A Nice (Asymmetric) Application Exercises Chapter 9 First-Order CSP, Limits and Homomorphism Dualities 9.1 Introduction 9.2 Homomorphism Dualities and the Functor U 9.2.1 Finite Dualities 9.2.2 Tree Dualities and the Functor U 9.3 Metrics on the Homomorphism Order 9.3.1 Partially Ordered Sets 9.3.2 The Homomorphism Order of -Structures 9.3.3 Connectivity and Multiplicativity 9.3.4 Left and Right Distances for the Homomorphism Order 9.3.5 Density 9.3.5.1 Density and Ambivalence of the Homomorphism Order 9.4 Left Limits and Countable Structures 9.4.1 Left Limits 9.5 Right Limits and Full Limits 9.5.1 The Right Distance 9.5.2 Full Distance 9.5.3 Full Dualities Exercises Chapter 10 Preservation Theorems 10.1 Introduction 10.2 Primitive Positive Theories and Left Limits 10.3 Theories and Countable Structures 10.4 Primitive Positive Theories Again 10.5 Quotient Metric Spaces 10.6 The Topological Preservation Theorem 10.7 Homomorphism Preservation Theorems 10.8 Homomorphism Preservation Theoremsfor Finite Structures Exercises Chapter 11 Restricted Homomorphism Dualities 11.1 Introduction 11.2 Classes with All Restricted Dualities 11.3 Characterization of Classes with All Restricted Dualities by Distances 11.4 Characterization of Classes with All Restricted Dualities by Local Homomorphisms 11.5 Restricted Dualities in Bounded Expansion Classes 11.6 Characterization of Classes with All Restricted Dualities by Reorientations 11.7 Characterization of Classes with All Restricted Dualities by Subdivisions 11.8 First-Order Definable H-Colorings 11.9 Consequences and Related Problems 11.9.1 On Hadwiger Conjecture 11.9.2 On Bounded Expansion Classes 11.9.3 On Distance Colorings – Powers and Exact Powers Exercises Chapter 12 Counting 12.1 Introduction 12.2 Generalized Sunflowers 12.2.1 Generalized Sunflowers 12.3 Counting Patterns of Bounded Height in a Colored Forest 12.3.1 Patterns 12.3.2 Blowing Patterns 12.3.3 Warm Up: Counting Patterns of Height 1 12.3.4 Counting Patterns of Height h 12.4 Counting in Graphs with Bounded Tree Depth 12.5 Counting Subgraphs in Graphs 12.6 Counting Subgraphs in Graphs in a Class Exercises Chapter 13 Back to Classes 13.1 Resolutions 13.2 Parameters 13.3 Nowhere Dense Classes 13.4 Bounded Expansion Classes 13.5 Bounded Tree-Depth Classes 13.6 Remarks on Structures Applications Chapter 14 Classes with Bounded Expansion – Examples 14.1 Random Graphs (Erdos-Rényi Model) 14.2 Crossing Number 14.3 Queue and Stack Layouts 14.4 Queue Number 14.5 Stack Number 14.6 Non-repetitive Colorings Exercises Chapter 15 Some Applications 15.1 Finding Matching and Paths 15.1.1 Introduction 15.1.2 Finding a Big Subgraph with Low Degrees 15.1.3 Finding Matchings 15.1.4 Finding Paths 15.1.5 A Particular Application: Strong Star Chromatic Number 15.2 Burr–Erdos Conjecture 15.3 The Game Chromatic Number 15.4 Fiedler Value of Classes with Sublinear Separators Chapter 16 Property Testing, Hyperfiniteness and Separators 16.1 Property Testing 16.1.1 The Dense Model 16.1.2 The Bounded Degree Model 16.2 Weakly Hyperfinite Classes 16.3 Vertex Separators 16.4 Sub-exponential -expansion Exercises Chapter 17 Core Algorithms 17.1 Data Structures and Algorithmic Aspects 17.2 p-Tree-Depth Coloring 17.2.1 Fraternal Augmentation 17.2.2 Computing the Forest 17.3 Computing and Approximating Tree-Depth 17.4 Counting Homomorphisms to Graphs with Bounded Tree-Depth 17.5 First-Order Cores of Graphs with Bounded Tree-Depth Exercises Chapter 18 Algorithmic Applications 18.1 Introduction 18.2 Truncated Distances 18.3 The Subgraph Isomorphism Problem and Boolean Queries 18.4 The Distance-d Dominating Set Problem 18.5 General First-Order Model Checking 18.6 Counting Versions of Model Checking 18.6.1 Enumerating Isomorphs 18.6.2 Counting Versions 18.6.3 Counting the Number of Solutions of a Boolean Query Exercises Chapter 19 Further Directions Chapter 20 Solutions and Hints for some of the Exercises References Index