Bounded expansion

Last updated

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.

Contents

Definition and equivalent characterizations

A 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

A 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

Because 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

Instances 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]

Related Research Articles

In graph theory, an undirected graph H is called a minor of the graph G if H can be formed from G by deleting edges, vertices and by contracting edges.

In theoretical computer science, the subgraph isomorphism problem is a computational task in which two graphs G and H are given as input, and one must determine whether G contains a subgraph that is isomorphic to H. Subgraph isomorphism is a generalization of both the maximum clique problem and the problem of testing whether a graph contains a Hamiltonian cycle, and is therefore NP-complete. However certain other cases of subgraph isomorphism may be solved in polynomial time.

In mathematics, a universal graph is an infinite graph that contains every finite graph as an induced subgraph. A universal graph of this type was first constructed by Richard Rado and is now called the Rado graph or random graph. More recent work has focused on universal graphs for a graph family F: that is, an infinite graph belonging to F that contains all finite graphs in F. For instance, the Henson graphs are universal in this sense for the i-clique-free graphs.

<span class="mw-page-title-main">Graph property</span> Property of graphs that depends only on abstract structure

In graph theory, a graph property or graph invariant is a property of graphs that depends only on the abstract structure, not on graph representations such as particular labellings or drawings of the graph.

<span class="mw-page-title-main">Hadwiger number</span> Size of largest complete graph made by contracting edges of a given graph

In graph theory, the Hadwiger number of an undirected graph G is the size of the largest complete graph that can be obtained by contracting edges of G. Equivalently, the Hadwiger number h(G) is the largest number n for which the complete graph Kn is a minor of G, a smaller graph obtained from G by edge contractions and vertex and edge deletions. The Hadwiger number is also known as the contraction clique number of G or the homomorphism degree of G. It is named after Hugo Hadwiger, who introduced it in 1943 in conjunction with the Hadwiger conjecture, which states that the Hadwiger number is always at least as large as the chromatic number of G.

The graph isomorphism problem is the computational problem of determining whether two finite graphs are isomorphic.

In mathematics, a dense graph is a graph in which the number of edges is close to the maximal number of edges. The opposite, a graph with only a few edges, is a sparse graph. The distinction of what constitutes a dense or sparse graph is ill-defined, and is often represented by 'roughly equal to' statements. Due to this, the way that density is defined often depends on the context of the problem.

<span class="mw-page-title-main">Book embedding</span> Graph layout on multiple half-planes

In graph theory, a book embedding is a generalization of planar embedding of a graph to embeddings in a book, a collection of half-planes all having the same line as their boundary. Usually, the vertices of the graph are required to lie on this boundary line, called the spine, and the edges are required to stay within a single half-plane. The book thickness of a graph is the smallest possible number of half-planes for any book embedding of the graph. Book thickness is also called pagenumber, stacknumber or fixed outerthickness. Book embeddings have also been used to define several other graph invariants including the pagewidth and book crossing number.

<span class="mw-page-title-main">Grundy number</span> Maximum number of colors obtainable by a greedy graph coloring algorithm

In graph theory, the Grundy number or Grundy chromatic number of an undirected graph is the maximum number of colors that can be used by a greedy coloring strategy that considers the vertices of the graph in sequence and assigns each vertex its first available color, using a vertex ordering chosen to use as many colors as possible. Grundy numbers are named after P. M. Grundy, who studied an analogous concept for directed graphs in 1939. The undirected version was introduced by Christen & Selkow (1979).

<span class="mw-page-title-main">Induced path</span> Graph path which is an induced subgraph

In the mathematical area of graph theory, an induced path in an undirected graph G is a path that is an induced subgraph of G. That is, it is a sequence of vertices in G such that each two adjacent vertices in the sequence are connected by an edge in G, and each two nonadjacent vertices in the sequence are not connected by any edge in G. An induced path is sometimes called a snake, and the problem of finding long induced paths in hypercube graphs is known as the snake-in-the-box problem.

In the mathematical field of graph theory, a core is a notion that describes behavior of a graph with respect to graph homomorphisms.

In graph theory, a branch of mathematics, many important families of graphs can be described by a finite set of individual graphs that do not belong to the family and further exclude all graphs from the family which contain any of these forbidden graphs as (induced) subgraph or minor.

In graph theory, the planar separator theorem is a form of isoperimetric inequality for planar graphs, that states that any planar graph can be split into smaller pieces by removing a small number of vertices. Specifically, the removal of vertices from an n-vertex graph can partition the graph into disjoint subgraphs each of which has at most vertices.

<span class="mw-page-title-main">Star coloring</span> Graph coloring in which every 4-vertex path uses ≥3 colors

In the mathematical field of graph theory, a star coloring of a graph G is a (proper) vertex coloring in which every path on four vertices uses at least three distinct colors. Equivalently, in a star coloring, the induced subgraphs formed by the vertices of any two colors has connected components that are star graphs. Star coloring has been introduced by Grünbaum (1973). The star chromatic number of G is the fewest colors needed to star color G.

In graph theory, the tree-depth of a connected undirected graph is a numerical invariant of , the minimum height of a Trémaux tree for a supergraph of . This invariant and its close relatives have gone under many different names in the literature, including vertex ranking number, ordered chromatic number, and minimum elimination tree height; it is also closely related to the cycle rank of directed graphs and the star height of regular languages. Intuitively, where the treewidth of a graph measures how far it is from being a tree, this parameter measures how far a graph is from being a star.

<span class="mw-page-title-main">1-planar graph</span>

In topological graph theory, a 1-planar graph is a graph that can be drawn in the Euclidean plane in such a way that each edge has at most one crossing point, where it crosses a single additional edge. If a 1-planar graph, one of the most natural generalizations of planar graphs, is drawn that way, the drawing is called a 1-plane graph or 1-planar embedding of the graph.

In graph theory, a shallow minor or limited-depth minor is a restricted form of a graph minor in which the subgraphs that are contracted to form the minor have small diameter. Shallow minors were introduced by Plotkin, Rao & Smith (1994), who attributed their invention to Charles E. Leiserson and Sivan Toledo.

<span class="mw-page-title-main">Queue number</span> Invariant in graph theory

In the mathematical field of graph theory, the queue number of a graph is a graph invariant defined analogously to stack number using first-in first-out (queue) orderings in place of last-in first-out (stack) orderings.

In the mathematical fields of graph theory and finite model theory, the logic of graphs deals with formal specifications of graph properties using sentences of mathematical logic. There are several variations in the types of logical operation that can be used in these sentences. The first-order logic of graphs concerns sentences in which the variables and predicates concern individual vertices and edges of a graph, while monadic second-order graph logic allows quantification over sets of vertices or edges. Logics based on least fixed point operators allow more general predicates over tuples of vertices, but these predicates can only be constructed through fixed-point operators, restricting their power.

The twin-width of an undirected graph is a natural number associated with the graph, used to study the parameterized complexity of graph algorithms. Intuitively, it measures how similar the graph is to a cograph, a type of graph that can be reduced to a single vertex by repeatedly merging together twins, vertices that have the same neighbors. The twin-width is defined from a sequence of repeated mergers where the vertices are not required to be twins, but have nearly equal sets of neighbors.

References

  1. 1 2 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 .
  2. 1 2 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 .
  3. ↑ 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
  4. ↑ Nešetřil & Ossona de Mendez (2012), 14.2 Crossing Number, pp. 319–321.
  5. ↑ 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 .
  6. ↑ 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 .
  7. ↑ Fox, Jacob; Pach, János (2009), "A separator theorem for string graphs and its applications", Combinatorics, Probability and Computing , 19 (3): 371, doi:10.1017/s0963548309990459 .
  8. ↑ 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 .
  9. ↑ Dujmović, Vida; Sidiropoulos, Anastasios; Wood, David R. (2015), 3-Monotone Expanders, arXiv: 1501.05020 , Bibcode:2015arXiv150105020D
  10. ↑ Nešetřil & Ossona de Mendez (2012), 14.5 Stack Number, pp. 327–328.
  11. ↑ Nešetřil & Ossona de Mendez (2012), p. 307.
  12. ↑ Nešetřil & Ossona de Mendez (2012), 14.1 Random Graphs (Erdős–Rényi Model), pp. 314–319.
  13. ↑ Nešetřil & Ossona de Mendez (2012), pp. 321–327.
  14. ↑ Nešetřil & Ossona de Mendez (2012), 18.3 The Subgraph Isomorphism Problem and Boolean Queries, pp. 400–401.
  15. ↑ 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 .
  16. ↑ Har-Peled, Sariel; Quanrud, Kent (2015), "Approximation algorithms for polynomial-expansion and low-density graphs", Algorithms – ESA 2015: 23rd Annual European Symposium, Patras, Greece, September 14–16, 2015, Proceedings, Lecture Notes in Computer Science, vol. 9294, Springer-Verlag, pp. 717–728, arXiv: 1501.00721 , doi:10.1007/978-3-662-48350-3_60 .
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.