Ton Kloks · Mingyu Xiao A Guide to Graph Algorithms A Guide to Graph Algorithms Ton Kloks (cid:129) Mingyu Xiao A Guide to Graph Algorithms Ton Kloks Mingyu Xiao Computer Science and Engineering Computer Science and Engineering University of Electronic Science University of Electronic Science and Technology of China and Technology of China Chengdu, Sichuan, China Chengdu, Sichuan, China ISBN 978-981-16-6349-9 ISBN 978-981-16-6350-5 (eBook ) https://doi.org/10.1007/978-981-16-6350-5 © The Editor(s) (if applicable) and The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. 2022 This work is subject to copyright. All rights are solely and exclusively licensed by the Publisher, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilms or in any other physical way, and transmission or information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now known or hereafter developed. The use of general descriptive names, registered names, trademarks, service marks, etc. in this publication does not imply, even in the absence of a specific statement, that such names are exempt from the relevant protective laws and regulations and therefore free for general use. The publisher, the authors and the editors are safe to assume that the advice and information in this book are believed to be true and accurate at the date of publication. Neither the publisher nor the authors or the editors give a warranty, expressed or implied, with respect to the material contained herein or for any errors or omissions that may have been made. The publisher remains neutral with regard to jurisdictional claims in published maps and institutional affiliations. This Springer imprint is published by the registered company Springer Nature Singapore Pte Ltd. The registered company address is: 152 Beach Road, #21-01/04 Gateway East, Singapore 189721, Singapore Contents Preface XI Acknowledgments XV Graphs 1 1.1 Isomorphic Graphs. . . . . . . . . . . . . . . . . . . 2 1.2 Representing graphs . . . . . . . . . . . . . . . . . . 2 1.3 Neighborhoods . . . . . . . . . . . . . . . . . . . . . 3 1.4 Connectedness . . . . . . . . . . . . . . . . . . . . . 4 1.5 Induced Subgraphs . . . . . . . . . . . . . . . . . . 4 1.6 Paths and Cycles . . . . . . . . . . . . . . . . . . . 5 1.7 Complements . . . . . . . . . . . . . . . . . . . . . . 7 1.8 Components . . . . . . . . . . . . . . . . . . . . . . . 7 1.8.1 Rem’s Algorithm . . . . . . . . . . . . . . . 7 1.9 Separators . . . . . . . . . . . . . . . . . . . . . . . . 10 1.10 Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.11 Bipartite Graphs . . . . . . . . . . . . . . . . . . . . 12 1.12 Linegraphs . . . . . . . . . . . . . . . . . . . . . . . 14 1.13 Cliques and Independent Sets . . . . . . . . . . . . 14 1.14 On Notations . . . . . . . . . . . . . . . . . . . . . . 15 Algorithms 17 2.1 Finding and counting small induced subgraphs . . . 18 2.2 Bottleneck domination . . . . . . . . . . . . . . . . . 20 2.3 The Bron & Kerbosch Algorithm . . . . . . . . . . . 22 2.3.1 A Timebound for the B&K {Algorithm . 28 2.4 Total Order! . . . . . . . . . . . . . . . . . . . . . . . 30 2.4.1 Hypergraphs . . . . . . . . . . . . . . . . . . 34 V VI Contents 2.4.2 Problem Reductions . . . . . . . . . . . . . . 35 2.5 NP{Completeness . . . . . . . . . . . . . . . . . . . 38 2.5.1 Equivalence covers of splitgraphs . . . . . . . 39 2.6 Lov(cid:19)asz Local Lemma . . . . . . . . . . . . . . . . . . 42 2.6.1 Bounds on dominating sets . . . . . . . . . . 46 2.6.2 The Moser & Tardos algorithm . . . . . . . . 48 2.6.3 Logs and witness trees . . . . . . . . . . . . . 49 2.6.4 A Galton - Watson branching process . . . . 52 2.7 Szemer(cid:19)edi’s Regularity Lemma . . . . . . . . . . . . 54 2.7.1 Construction of regular partitions. . . . . . . 60 2.8 Edge - thickness and stickiness . . . . . . . . . . . . 72 2.9 Clique Separators . . . . . . . . . . . . . . . . . . . 74 2.9.1 Feasible Partitions . . . . . . . . . . . . . . . 76 2.9.2 Intermezzo . . . . . . . . . . . . . . . . . . . 79 2.9.3 Another Intermezzo: Trivially perfect graphs 80 2.10 Vertex ranking . . . . . . . . . . . . . . . . . . . . . 81 2.10.1 Permutation graphs . . . . . . . . . . . . . . 81 2.10.2 Separators in permutation graphs. . . . . . . 82 2.10.3 Vertex ranking of permutation graphs . . . . 83 2.11 Cographs . . . . . . . . . . . . . . . . . . . . . . . . 84 2.11.1 Switching cographs . . . . . . . . . . . . . . . 85 2.12 Parameterized Algorithms . . . . . . . . . . . . . . . 88 2.13 The bounded search technique . . . . . . . . . . . . 90 2.13.1 Vertex cover . . . . . . . . . . . . . . . . . . 90 2.13.2 Edge dominating set . . . . . . . . . . . . . . 91 2.13.3 Feedback vertex set . . . . . . . . . . . . . . 92 2.13.4 Further reading . . . . . . . . . . . . . . . . . 95 2.14 Matchings . . . . . . . . . . . . . . . . . . . . . . . . 96 2.15 Independent Set in Claw - Free Graphs. . . . . . . . 97 2.15.1 The Blossom Algorithm . . . . . . . . . . . . 97 2.15.2 Minty’s Algorithm . . . . . . . . . . . . . . 100 2.15.3 A Cute Lemma . . . . . . . . . . . . . . . . . 101 2.15.4 Edmonds’ Graph . . . . . . . . . . . . . . . 102 2.16 Dominoes . . . . . . . . . . . . . . . . . . . . . . . . 104 2.17 Triangle partition of planar graphs . . . . . . . . . . 106 2.17.1 Intermezzo: PQ - trees . . . . . . . . . . . . . 110 2.18 Games . . . . . . . . . . . . . . . . . . . . . . . . . . 111 2.18.1 Snake . . . . . . . . . . . . . . . . . . . . . . 112 Contents VII 2.18.2 Grundy values . . . . . . . . . . . . . . . . . 113 2.18.3 De Bruijn’s game . . . . . . . . . . . . . . . . 114 2.18.4 Poset games . . . . . . . . . . . . . . . . . . . 115 2.18.5 Coin - turning games . . . . . . . . . . . . . . 116 2.18.6 Nim - multiplication . . . . . . . . . . . . . . 118 2.18.7 P - Games . . . . . . . . . . . . . . . . . . . 120 3 2.18.8 Chomp . . . . . . . . . . . . . . . . . . . . . 122 Problem Formulations 125 3.1 Graph Algebras . . . . . . . . . . . . . . . . . . . . 125 3.2 Monadic Second{Order Logic . . . . . . . . . . . . 126 3.2.1 Sentences and Expressions . . . . . . . . . 126 3.2.2 Quanti(cid:12)cation over Subsets of Edges . . . 127 Recent Trends 129 4.1 Triangulations . . . . . . . . . . . . . . . . . . . . . 129 4.1.1 Chordal Graphs . . . . . . . . . . . . . . . . 129 4.1.2 Clique{Trees . . . . . . . . . . . . . . . . . . 132 4.2 Treewidth . . . . . . . . . . . . . . . . . . . . . . . . 134 4.2.1 Treewidth and brambles . . . . . . . . . . . . 135 4.2.2 Tree - decompositions . . . . . . . . . . . . . 137 4.2.3 Example: Steiner tree . . . . . . . . . . . . . 139 4.2.4 Treewidth of Circle Graphs . . . . . . . . . 145 4.3 On the treewidth of planar graphs . . . . . . . . . . 149 4.3.1 Antipodalities . . . . . . . . . . . . . . . . . . 151 4.3.2 Tilts and slopes . . . . . . . . . . . . . . . . . 157 4.3.3 Bond carvings . . . . . . . . . . . . . . . . . 163 4.3.4 Carvings and antipodalities . . . . . . . . . . 168 4.4 Tree - degrees of graphs . . . . . . . . . . . . . . . . 174 4.4.1 Intermezzo: Interval graphs . . . . . . . . . . 175 4.5 Modular decomposition . . . . . . . . . . . . . . . . 177 4.5.1 Modular decomposition tree . . . . . . . . . . 179 4.5.2 A linear - time modular decomposition . . . . 180 4.5.3 Exercise . . . . . . . . . . . . . . . . . . . . . 187 4.6 Rankwidth . . . . . . . . . . . . . . . . . . . . . . . 187 4.6.1 Distance hereditary - graphs . . . . . . . . . 188 4.6.2 Intermezzo: Perfect graphs . . . . . . . . . . 190 4.6.3 χ - Boundedness . . . . . . . . . . . . . . . . 191 VIII Contents 4.6.4 Governed decompositions . . . . . . . . . . . 196 4.6.5 Forward Ramsey splits . . . . . . . . . . . . . 198 4.6.6 Factorization of trees . . . . . . . . . . . . . . 199 4.6.7 Kruskalian decompositions . . . . . . . . . . 203 4.6.8 Exercise . . . . . . . . . . . . . . . . . . . . . 204 4.7 Clustered coloring . . . . . . . . . . . . . . . . . . . 205 4.7.1 Bandwidth and BFS - trees with few leaves . 205 4.7.2 Connected partitions . . . . . . . . . . . . . . 207 4.7.3 A decomposition of K minor free graphs . . 210 t 4.7.4 Further reading . . . . . . . . . . . . . . . . . 211 4.8 Well - Quasi Orders . . . . . . . . . . . . . . . . . . 213 4.8.1 Higman’s Lemma . . . . . . . . . . . . . . . . 213 4.8.2 Kruskal’s Theorem . . . . . . . . . . . . . . . 215 4.8.3 Gap embeddings . . . . . . . . . . . . . . . . 216 4.9 Threshold graphs and threshold - width . . . . . . . 217 4.9.1 Threshold - width . . . . . . . . . . . . . . . 218 4.9.2 On the complexity of threshold - width . . . 221 4.9.3 A (cid:12)xed - parameter algorithm for threshold - width . . . . . . . . . . . . . . . . . . . . . . 222 4.10 Black and white - coloring . . . . . . . . . . . . . . . 227 4.10.1 The complexity of black and white - coloring 228 4.11 k{Cographs. . . . . . . . . . . . . . . . . . . . . . . 229 4.11.1 Recognition of k{Cographs . . . . . . . . . 231 4.11.2 Recognition of k{Cographs | revisited . . 232 4.11.3 Treewidth of Cographs . . . . . . . . . . . . 233 4.12 Minors . . . . . . . . . . . . . . . . . . . . . . . . . . 234 4.12.1 The Graph Minor Theorem . . . . . . . . . 235 4.13 General Partition Graphs . . . . . . . . . . . . . . . 236 4.14 Tournaments . . . . . . . . . . . . . . . . . . . . . . 240 4.14.1 Tournament games . . . . . . . . . . . . . . . 240 4.14.2 Trees in tournaments. . . . . . . . . . . . . . 242 4.14.3 Immersions in tournaments . . . . . . . . . . 246 4.14.4 Domination in tournaments . . . . . . . . . . 255 4.15 Immersions . . . . . . . . . . . . . . . . . . . . . . . 259 4.15.1 Intermezzo: Topological minors . . . . . . . 259 4.15.2 Strong immersions in series - parallel digraphs 261 4.15.3 Intermezzo on 2 - trees . . . . . . . . . . . . . 262 4.15.4 Series parallel - triples . . . . . . . . . . . . . 263 Contents IX 4.15.5 A well quasi - order for one way series parallel - triples . . . . . . . . . . . . . . . . . . . . . 268 4.15.6 Series parallel separations . . . . . . . . . . . 270 4.15.7 Coda. . . . . . . . . . . . . . . . . . . . . . . 275 4.15.8 Exercise . . . . . . . . . . . . . . . . . . . . . 281 4.16 Asteroidal sets . . . . . . . . . . . . . . . . . . . . . 282 4.16.1 AT - free graphs . . . . . . . . . . . . . . . . 283 4.16.2 Independent set in AT-free graphs . . . . . . 283 4.16.3 Exercise . . . . . . . . . . . . . . . . . . . . . 285 4.16.4 Bandwidth of AT-free graphs . . . . . . . . . 286 4.16.5 Dominating pairs . . . . . . . . . . . . . . . . 290 4.16.6 Antimatroids . . . . . . . . . . . . . . . . . . 290 4.16.7 Totally balanced matrices . . . . . . . . . . . 292 4.16.8 Triangle graphs . . . . . . . . . . . . . . . . . 295 4.17 Sensitivity . . . . . . . . . . . . . . . . . . . . . . . . 296 4.17.1 What happened earlier ... . . . . . . . . . . . 297 4.17.2 Cauchy’s interlace lemma . . . . . . . . . . . 298 4.17.3 Hypercubes . . . . . . . . . . . . . . . . . . . 298 4.17.4 M(cid:127)obius inversion . . . . . . . . . . . . . . . . 300 4.17.5 The equivalence theorem . . . . . . . . . . . 301 4.17.6 Further reading . . . . . . . . . . . . . . . . . 304 4.18 Homomorphisms . . . . . . . . . . . . . . . . . . . . 304 4.18.1 Retracts . . . . . . . . . . . . . . . . . . . . . 305 4.18.2 Retracts in threshold graphs . . . . . . . . . 306 4.18.3 Retracts in cographs . . . . . . . . . . . . . . 307 4.19 Products. . . . . . . . . . . . . . . . . . . . . . . . . 312 4.19.1 Categorical products of cographs . . . . . . . 313 4.19.2 Tensor capacity . . . . . . . . . . . . . . . . . 314 4.19.3 Cartesian products . . . . . . . . . . . . . . . 317 4.19.4 Independence domination in cographs . . . . 318 4.19.5 θ (K (cid:2)K ) . . . . . . . . . . . . . . . . . . 319 e n n 4.20 Outerplanar Graphs . . . . . . . . . . . . . . . . . . 321 4.20.1 k{Outerplanar Graphs . . . . . . . . . . . . 322 4.20.2 Courcelle’s Theorem . . . . . . . . . . . . . 323 4.20.3 Approximations for Planar Graphs . . . . . . 323 4.20.4 Independent Set in Planar Graphs . . . . . . 323 4.21 Graph isomorphism. . . . . . . . . . . . . . . . . . . 325 X Contents Bibliography 327 Index 335