In graph theory, a family of graphs is said to have bounded expansion if all of its shallow minors are sparse graphs. Many natural families of sparse graphs have bounded expansion. A closely related but stronger property, polynomial expansion, is equivalent to the existence of separator theorems for these families. Families with these properties have efficient algorithms for problems including the subgraph isomorphism problem and model checking for the first order theory of graphs.
Definition and equivalent characterizations
editA t-shallow minor of a graph G is defined to be a graph formed from G by contracting a collection of vertex-disjoint subgraphs of radius t, and deleting the remaining vertices of G. A family of graphs has bounded expansion if there exists a function f such that, in every t-shallow minor of a graph in the family, the ratio of edges to vertices is at most f(t).[1]
Equivalent definitions of classes of bounded expansions are that all shallow minors have chromatic number bounded by a function of t,[1] or that the given family has a bounded value of a topological parameter. Such a parameter is a graph invariant that is monotone under taking subgraphs, such that the parameter value can change only in a controlled way when a graph is subdivided, and such that a bounded parameter value implies that a graph has bounded degeneracy.[2]
Polynomial expansion and separator theorems
editA stronger notion is polynomial expansion, meaning that the function f used to bound the edge density of shallow minors is a polynomial. If a hereditary graph family obeys a separator theorem, stating that any n-vertex graph in the family can be split into pieces with at most n/2 vertices by the removal of O(nc) vertices for some constant c < 1, then that family necessarily has polynomial expansion. Conversely, graphs with polynomial expansion have sublinear separator theorems.[3]
Classes of graphs with bounded expansion
editBecause of the connection between separators and expansion, every minor-closed graph family, including the family of planar graphs, has polynomial expansion. The same is true for 1-planar graphs, and more generally the graphs that can be embedded onto surfaces of bounded genus with a bounded number of crossings per edge, as well as the biclique-free string graphs, since these all obey similar separator theorems to the planar graphs.[4][5][6][7] In higher dimensional Euclidean spaces, intersection graphs of systems of balls with the property that any point of space is covered by a bounded number of balls also obey separator theorems[8] that imply polynomial expansion.
Although graphs of bounded book thickness do not have sublinear separators,[9] they also have bounded expansion.[10] Other graphs of bounded expansion include graphs of bounded degree,[11] random graphs of bounded average degree in the Erdős–Rényi model,[12] and graphs of bounded queue number.[2][13]
Algorithmic applications
editInstances of the subgraph isomorphism problem in which the goal is to find a target graph of bounded size, as a subgraph of a larger graph whose size is not bounded, may be solved in linear time when the larger graph belongs to a family of graphs of bounded expansion. The same is true for finding cliques of a fixed size, finding dominating sets of a fixed size, or more generally testing properties that can be expressed by a formula of bounded size in the first-order logic of graphs.[14][15]
For graphs of polynomial expansion, there exist polynomial-time approximation schemes for the set cover problem, maximum independent set problem, dominating set problem, and several other related graph optimization problems.[16]
References
edit- ^ a b Nešetřil, Jaroslav; Ossona de Mendez, Patrice (2012), "5.5 Classes with Bounded Expansion", Sparsity: Graphs, Structures, and Algorithms, Algorithms and Combinatorics, vol. 28, Springer, pp. 104–107, doi:10.1007/978-3-642-27875-4, ISBN 978-3-642-27874-7, MR 2920058.
- ^ a b Nešetřil, Jaroslav; Ossona de Mendez, Patrice; Wood, David R. (2012), "Characterisations and examples of graph classes with bounded expansion", European Journal of Combinatorics, 33 (3): 350–373, arXiv:0902.3265, doi:10.1016/j.ejc.2011.09.008, MR 2864421, S2CID 2633083.
- ^ Dvořák, Zdeněk; Norin, Sergey (2016), "Strongly sublinear separators and polynomial expansion", SIAM Journal on Discrete Mathematics, 30 (2): 1095–1101, arXiv:1504.04821, doi:10.1137/15M1017569, MR 3504982, S2CID 27395359
- ^ Nešetřil & Ossona de Mendez (2012), 14.2 Crossing Number, pp. 319–321.
- ^ Grigoriev, Alexander; Bodlaender, Hans L. (2007), "Algorithms for graphs embeddable with few crossings per edge", Algorithmica, 49 (1): 1–11, doi:10.1007/s00453-007-0010-x, MR 2344391, S2CID 8174422.
- ^ Dujmović, Vida; Eppstein, David; Wood, David R. (2015), "Genus, treewidth, and local crossing number", Proc. 23rd Int. Symp. Graph Drawing (GD 2015), arXiv:1506.04380, Bibcode:2015arXiv150604380D.
- ^ Fox, Jacob; Pach, János (2009), "A separator theorem for string graphs and its applications" (PDF), Combinatorics, Probability and Computing, 19 (3): 371, doi:10.1017/s0963548309990459, S2CID 5705145.
- ^ Miller, Gary L.; Teng, Shang-Hua; Thurston, William; Vavasis, Stephen A. (1997), "Separators for sphere-packings and nearest neighbor graphs", Journal of the ACM, 44 (1): 1–29, doi:10.1145/256292.256294, MR 1438463.
- ^ Dujmović, Vida; Sidiropoulos, Anastasios; Wood, David R. (2015), 3-Monotone Expanders, arXiv:1501.05020, Bibcode:2015arXiv150105020D
- ^ Nešetřil & Ossona de Mendez (2012), 14.5 Stack Number, pp. 327–328.
- ^ Nešetřil & Ossona de Mendez (2012), p. 307.
- ^ Nešetřil & Ossona de Mendez (2012), 14.1 Random Graphs (Erdős–Rényi Model), pp. 314–319.
- ^ Nešetřil & Ossona de Mendez (2012), pp. 321–327.
- ^ Nešetřil & Ossona de Mendez (2012), 18.3 The Subgraph Isomorphism Problem and Boolean Queries, pp. 400–401.
- ^ Dvořák, Zdeněk; Kráľ, Daniel; Thomas, Robin (2010), "Deciding first-order properties for sparse graphs", Proc. 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS 2010), IEEE Computer Soc., Los Alamitos, CA, pp. 133–142, MR 3024787.
- ^ Har-Peled, Sariel; Quanrud, Kent (2015), "Approximation algorithms for polynomial-expansion and low-density graphs", Algorithms - ESA 2015, Lecture Notes in Computer Science, vol. 9294, Springer-Verlag, pp. 717–728, arXiv:1501.00721, doi:10.1007/978-3-662-48350-3_60, ISBN 978-3-662-48349-7.