Diameter (graph theory)

Last updated January 09, 2025

In graph theory, the diameter of a connected undirected graph is the farthest distance between any two of its vertices. That is, it is the diameter of a set for the set of vertices of the graph, and for the shortest-path distance in the graph. Diameter may be considered either for weighted or for unweighted graphs. Researchers have studied the problem of computing the diameter, both in arbitrary graphs and in special classes of graphs.

Graphs of low diameter

The degree diameter problem seeks tight relations between the diameter, number of vertices, and degree of a graph. One way of formulating it is to ask for the largest graph with given bounds on its degree and diameter. For any fixed degree, this maximum size is exponential in the diameter, with the base of the exponent depending on the degree.^[1]

The girth of a graph, the length of its shortest cycle, can be at most $2k+1$ for a graph of diameter $k$ . The regular graphs for which the girth is exactly $2k+1$ are the Moore graphs. Only finitely many Moore graphs exist, but their exact number is unknown. They provide the solutions to the degree diameter problem for their degree and diameter.^[2]

Small-world networks are a class of graphs with low diameter, modeling the real-world phenomenon of six degrees of separation in social networks.^[3]

Algorithms

In arbitrary graphs

The diameter of a graph can be computed by using a shortest path algorithm to compute shortest paths between all pairs of vertices, and then taking the maximum of the distances that it computes. For instance, in a graph with positive edge weights, this can be done by repeatedly using Dijkstra's algorithm, once for each possible starting vertex. In a graph with $n$ vertices and $m$ edges, this takes time $O(mn+n^{2}\log n)$ . Computing all-pairs shortest paths is the fastest known method for computing the diameter of a weighted graph exactly.^[4]

In an unweighted-graph, Dijkstra's algorithm may be replaced by breadth-first search, giving time $O(mn)$ . Alternatively, the diameter may be computed using an algorithm based on fast matrix multiplication, in time proportional to the time for multiplying $n\times n$ matrices, approximately $O(n^{2.37})$ using known matrix multiplication algorithms.^[5] For sparse graphs, with few edges, repeated breadth-first search is faster than matrix multiplication. Assuming the exponential time hypothesis, repeated breadth-first search is near-optimal: this hypothesis implies that no algorithm can achieve time $O(n^{2-\varepsilon })$ for any $\varepsilon >0$ .^[4]

It is possible to approximate the diameter of a weighted graph to within an approximation ratio of 3/2, in time ${\tilde {O}}(\min(m^{3/2},mn^{2/3})$ , where the ${\tilde {O}}$ notation hides logarithmic factors in the time bound.^[6] Under the exponential time hypothesis, no substantially more accurate approximation, substantially faster than all pairs shortest paths, is possible.^[4]

In special classes of graphs

The diameter can be computed in linear time for interval graphs,^[7] and in near-linear time for graphs of bounded treewidth.^[8] In median graphs, the diameter can be found in the subquadratic time bound ${\tilde {O}}(n^{1.6456})$ .^[9] In any class of graphs closed under graph minors, such as the planar graphs, it is possible to compute the diameter in subquadratic time, with an exponent depending on the graph family.^[10]

Related Research Articles

In graph theory, the shortest path problem is the problem of finding a path between two vertices in a graph such that the sum of the weights of its constituent edges is minimized.

<span class="mw-page-title-main">Breadth-first search</span> Algorithm to search the nodes of a graph

Breadth-first search (BFS) is an algorithm for searching a tree data structure for a node that satisfies a given property. It starts at the tree root and explores all nodes at the present depth prior to moving on to the nodes at the next depth level. Extra memory, usually a queue, is needed to keep track of the child nodes that were encountered but not yet explored.

In computer science, the Floyd–Warshall algorithm is an algorithm for finding shortest paths in a directed weighted graph with positive or negative edge weights. A single execution of the algorithm will find the lengths of shortest paths between all pairs of vertices. Although it does not return details of the paths themselves, it is possible to reconstruct the paths with simple modifications to the algorithm. Versions of the algorithm can also be used for finding the transitive closure of a relation $, or widest paths between all pairs of vertices in a weighted graph.$

In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, supposing that each elementary operation takes a fixed amount of time to perform. Thus, the amount of time taken and the number of elementary operations performed by the algorithm are taken to be related by a constant factor.

In combinatorial mathematics, the Steiner tree problem, or minimum Steiner tree problem, named after Jakob Steiner, is an umbrella term for a class of problems in combinatorial optimization. While Steiner tree problems may be formulated in a number of settings, they all require an optimal interconnect for a given set of objects and a predefined objective function. One well-known variant, which is often used synonymously with the term Steiner tree problem, is the Steiner tree problem in graphs. Given an undirected graph with non-negative edge weights and a subset of vertices, usually referred to as terminals, the Steiner tree problem in graphs requires a tree of minimum weight that contains all terminals and minimizes the total weight of its edges. Further well-known variants are the Euclidean Steiner tree problem and the rectilinear minimum Steiner tree problem.

A Euclidean minimum spanning tree of a finite set of points in the Euclidean plane or higher-dimensional Euclidean space connects the points by a system of line segments with the points as endpoints, minimizing the total length of the segments. In it, any two points can reach each other along a path through the line segments. It can be found as the minimum spanning tree of a complete graph with the points as vertices and the Euclidean distances between points as edge weights.

In graph theory, the metric dimension of a graph G is the minimum cardinality of a subset S of vertices such that all other vertices are uniquely determined by their distances to the vertices in S. Finding the metric dimension of a graph is an NP-hard problem; the decision version, determining whether the metric dimension is less than a given value, is NP-complete.

The Christofides algorithm or Christofides–Serdyukov algorithm is an algorithm for finding approximate solutions to the travelling salesman problem, on instances where the distances form a metric space . It is an approximation algorithm that guarantees that its solutions will be within a factor of 3/2 of the optimal solution length, and is named after Nicos Christofides and Anatoliy Serdyukov. Christofides published the algorithm in 1976; Serdyukov discovered it independently in 1976 but published it in 1978.

Maximum cardinality matching is a fundamental problem in graph theory. We are given a graph $G$ , and the goal is to find a matching containing as many edges as possible; that is, a maximum cardinality subset of the edges such that each vertex is adjacent to at most one edge of the subset. As each edge will cover exactly two vertices, this problem is equivalent to the task of finding a matching that covers as many vertices as possible.

In the mathematical area of graph theory, a triangle-free graph is an undirected graph in which no three vertices form a triangle of edges. Triangle-free graphs may be equivalently defined as graphs with clique number ≤ 2, graphs with girth ≥ 4, graphs with no induced 3-cycle, or locally independent graphs.

A geometric spanner or a $t$ -spanner graph or a $t$ -spanner was initially introduced as a weighted graph over a set of points as its vertices for which there is a $t$ -path between any pair of vertices for a fixed parameter $t$ . A $t$ -path is defined as a path through the graph with weight at most $t$ times the spatial distance between its endpoints. The parameter $t$ is called the stretch factor or dilation factor of the spanner.

In graph theory and theoretical computer science, the longest path problem is the problem of finding a simple path of maximum length in a given graph. A path is called simple if it does not have any repeated vertices; the length of a path may either be measured by its number of edges, or by the sum of the weights of its edges. In contrast to the shortest path problem, which can be solved in polynomial time in graphs without negative-weight cycles, the longest path problem is NP-hard and the decision version of the problem, which asks whether a path exists of at least some given length, is NP-complete. This means that the decision problem cannot be solved in polynomial time for arbitrary graphs unless P = NP. Stronger hardness results are also known showing that it is difficult to approximate. However, it has a linear time solution for directed acyclic graphs, which has important applications in finding the critical path in scheduling problems.

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">Widest path problem</span> Path-finding using high-weight graph edges

In graph algorithms, the widest path problem is the problem of finding a path between two designated vertices in a weighted graph, maximizing the weight of the minimum-weight edge in the path. The widest path problem is also known as the maximum capacity path problem. It is possible to adapt most shortest path algorithms to compute widest paths, by modifying them to use the bottleneck distance instead of path length. However, in many cases even faster algorithms are possible.

In network theory, the Wiener connector is a means of maximizing efficiency in connecting specified "query vertices" in a network. Given a connected, undirected graph and a set of query vertices in a graph, the minimum Wiener connector is an induced subgraph that connects the query vertices and minimizes the sum of shortest path distances among all pairs of vertices in the subgraph. In combinatorial optimization, the minimum Wiener connector problem is the problem of finding the minimum Wiener connector. It can be thought of as a version of the classic Steiner tree problem, where instead of minimizing the size of the tree, the objective is to minimize the distances in the subgraph.

Seidel's algorithm is an algorithm designed by Raimund Seidel in 1992 for the all-pairs-shortest-path problem for undirected, unweighted, connected graphs. It solves the problem in $expected time for a graph with vertices, where is the exponent in the complexity of matrix multiplication. If only the distances between each pair of vertices are sought, the same time bound can be achieved in the worst case. Even though the algorithm is designed for connected graphs, it can be applied individually to each connected component of a graph with the same running time overall. There is an exception to the expected running time given above for computing the paths: if the expected running time becomes .$

In combinatorial optimization, the matroid parity problem is a problem of finding the largest independent set of paired elements in a matroid. The problem was formulated by Lawler (1976) as a common generalization of graph matching and matroid intersection. It is also known as polymatroid matching, or the matchoid problem.

In computational geometry, a greedy geometric spanner is an undirected graph whose distances approximate the Euclidean distances among a finite set of points in a Euclidean space. The vertices of the graph represent these points. The edges of the spanner are selected by a greedy algorithm that includes an edge whenever its two endpoints are not connected by a short path of shorter edges. The greedy spanner was first described in the PhD thesis of Gautam Das and conference paper and subsequent journal paper by Ingo Althöfer et al. These sources also credited Marshall Bern (unpublished) with the independent discovery of the same construction.

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.

In metric geometry and computational geometry, a minimum-diameter spanning tree of a finite set of points in a metric space is a spanning tree in which the diameter is as small as possible.

References

↑ Miller, Mirka; Širáň, Jozef (2005), "Moore graphs and beyond: A survey of the degree/diameter problem", Electronic Journal of Combinatorics , Dynamic survey: DS14
↑ Dalfó, C. (2019), "A survey on the missing Moore graph" (PDF), Linear Algebra and Its Applications, 569: 1–14, doi:10.1016/j.laa.2018.12.035, hdl: 2117/127212 , MR 3901732, S2CID 126689579
↑ Amaral, L. A. N.; Scala, A.; Barthélémy, M.; Stanley, H. E. (September 2000), "Classes of small-world networks", Proceedings of the National Academy of Sciences, 97 (21): 11149–11152, arXiv: cond-mat/0001458 , doi: 10.1073/pnas.200327197 , PMID 11005838
1 2 3 Roditty, Liam; Vassilevska Williams, Virginia (2013), "Fast approximation algorithms for the diameter and radius of sparse graphs", in Boneh, Dan; Roughgarden, Tim; Feigenbaum, Joan (eds.), Symposium on Theory of Computing Conference, STOC'13, Palo Alto, CA, USA, June 1-4, 2013, Association for Computing Machinery, pp. 515–524, doi:10.1145/2488608.2488673, ISBN 978-1-4503-2029-0
↑ Cygan, Marek; Gabow, Harold N.; Sankowski, Piotr (2012), "Algorithmic applications of Baur-Strassen's theorem: shortest cycles, diameter and matchings", 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, IEEE Computer Society, pp. 531–540, arXiv: 1204.1616 , doi:10.1109/FOCS.2012.72, ISBN 978-0-7695-4874-6
↑ Chechik, Shiri; Larkin, Daniel H.; Roditty, Liam; Schoenebeck, Grant; Tarjan, Robert Endre; Vassilevska Williams, Virginia (2014), "Better approximation algorithms for the graph diameter", in Chekuri, Chandra (ed.), Proceedings of the Twenty-Fifth Annual ACM–SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, SIAM, pp. 1041–1052, doi:10.1137/1.9781611973402.78, ISBN 978-1-61197-338-9
↑ Olariu, Stephan (1990), "A simple linear-time algorithm for computing the center of an interval graph", Int. J. Comput. Math., 34 (3–4): 121–128, doi:10.1080/00207169008803870
↑ Bringmann, Karl; Husfeldt, Thore; Magnusson, Måns (2020), "Multivariate analysis of orthogonal range searching and graph distances", Algorithmica, 82 (8): 2292–2315, doi:10.1007/s00453-020-00680-z, MR 4132892
↑ Bergé, Pierre; Ducoffe, Guillaume; Habib, Michel (2024), "Subquadratic-time algorithm for the diameter and all eccentricities on median graphs", Theory of Computing Systems, 68 (1): 144–193, arXiv: 2110.02709 , doi:10.1007/s00224-023-10153-9, MR 4699679
↑ Ducoffe, Guillaume; Habib, Michel; Viennot, Laurent (2022), "Diameter, eccentricities and distance oracle computations on $H$ -minor free graphs and graphs of bounded (distance) Vapnik-Chervonenkis dimension", SIAM Journal on Computing , 51 (5): 1506–1534, arXiv: 1907.04385 , doi:10.1137/20M136551X, MR 4502132

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.

[milsir-1] Miller, Mirka; Širáň, Jozef (2005), "Moore graphs and beyond: A survey of the degree/diameter problem", Electronic Journal of Combinatorics , Dynamic survey: DS14

[dalfo-2] Dalfó, C. (2019), "A survey on the missing Moore graph" (PDF), Linear Algebra and Its Applications, 569: 1–14, doi:10.1016/j.laa.2018.12.035, hdl: 2117/127212 , MR 3901732, S2CID 126689579

[amscabs-3] Amaral, L. A. N.; Scala, A.; Barthélémy, M.; Stanley, H. E. (September 2000), "Classes of small-world networks", Proceedings of the National Academy of Sciences, 97 (21): 11149–11152, arXiv: cond-mat/0001458 , doi: 10.1073/pnas.200327197 , PMID 11005838

[rodvw-4] 1 2 3 Roditty, Liam; Vassilevska Williams, Virginia (2013), "Fast approximation algorithms for the diameter and radius of sparse graphs", in Boneh, Dan; Roughgarden, Tim; Feigenbaum, Joan (eds.), Symposium on Theory of Computing Conference, STOC'13, Palo Alto, CA, USA, June 1-4, 2013, Association for Computing Machinery, pp. 515–524, doi:10.1145/2488608.2488673, ISBN 978-1-4503-2029-0

[cygasa-5] Cygan, Marek; Gabow, Harold N.; Sankowski, Piotr (2012), "Algorithmic applications of Baur-Strassen's theorem: shortest cycles, diameter and matchings", 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, IEEE Computer Society, pp. 531–540, arXiv: 1204.1616 , doi:10.1109/FOCS.2012.72, ISBN 978-0-7695-4874-6

[clrstv-6] Chechik, Shiri; Larkin, Daniel H.; Roditty, Liam; Schoenebeck, Grant; Tarjan, Robert Endre; Vassilevska Williams, Virginia (2014), "Better approximation algorithms for the graph diameter", in Chekuri, Chandra (ed.), Proceedings of the Twenty-Fifth Annual ACM–SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, SIAM, pp. 1041–1052, doi:10.1137/1.9781611973402.78, ISBN 978-1-61197-338-9

[olariu-7] Olariu, Stephan (1990), "A simple linear-time algorithm for computing the center of an interval graph", Int. J. Comput. Math., 34 (3–4): 121–128, doi:10.1080/00207169008803870

[brhuma-8] Bringmann, Karl; Husfeldt, Thore; Magnusson, Måns (2020), "Multivariate analysis of orthogonal range searching and graph distances", Algorithmica, 82 (8): 2292–2315, doi:10.1007/s00453-020-00680-z, MR 4132892

[beduha-9] Bergé, Pierre; Ducoffe, Guillaume; Habib, Michel (2024), "Subquadratic-time algorithm for the diameter and all eccentricities on median graphs", Theory of Computing Systems, 68 (1): 144–193, arXiv: 2110.02709 , doi:10.1007/s00224-023-10153-9, MR 4699679

[duhavi-10] Ducoffe, Guillaume; Habib, Michel; Viennot, Laurent (2022), "Diameter, eccentricities and distance oracle computations on $H$ -minor free graphs and graphs of bounded (distance) Vapnik-Chervonenkis dimension", SIAM Journal on Computing , 51 (5): 1506–1534, arXiv: 1907.04385 , doi:10.1137/20M136551X, MR 4502132

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]