Hyperbolicity#
Definition :
The hyperbolicity \(\delta\) of a graph \(G\) has been defined by Gromov [Gro1987] as follows (we give here the socalled 4points condition):
Let \(a, b, c, d\) be vertices of the graph, let \(S_1\), \(S_2\) and \(S_3\) be defined by
\[\begin{split}S_1 = dist(a, b) + dist(d, c)\\ S_2 = dist(a, c) + dist(b, d)\\ S_3 = dist(a, d) + dist(b, c)\\\end{split}\]and let \(M_1\) and \(M_2\) be the two largest values among \(S_1\), \(S_2\), and \(S_3\). We define \(hyp(a, b, c, d) = M_1  M_2\), and the hyperbolicity \(\delta(G)\) of the graph is the maximum of \(hyp\) over all possible 4tuples \((a, b, c, d)\) divided by 2. That is, the graph is said \(\delta\)hyperbolic when
\[\delta(G) = \frac{1}{2}\max_{a,b,c,d\in V(G)}hyp(a, b, c, d)\](note that \(hyp(a, b, c, d)=0\) whenever two elements among \(a,b,c,d\) are equal)
Some known results :
Trees and cliques are \(0\)hyperbolic
\(n\times n\) grids are \(n1\)hyperbolic
Cycles are approximately \(n/4\)hyperbolic
Chordal graphs are \(\leq 1\)hyperbolic
Besides, the hyperbolicity of a graph is the maximum over all its biconnected components.
Algorithms and complexity :
The time complexity of the naive implementation (i.e. testing all 4tuples) is \(O( n^4 )\), and an algorithm with time complexity \(O(n^{3.69})\) has been proposed in [FIV2012]. This remains very long for largescale graphs, and much harder to implement.
Several improvements over the naive algorithm have been proposed and are implemented in the current module.
Another upper bound on \(hyp(a, b, c, d)\) has been proved in [CCL2015]. It is used to design an algorithm with worse case time complexity in \(O(n^4)\) but that behaves much better in practice.
Assume that \(S_1 = dist(a, b) + dist(c, d)\) is the largest sum among \(S_1,S_2,S_3\). We have
\[\begin{split}S_2 + S_3 =& dist(a, c) + dist(b, d) + dist(a, d) + dist(b, c)\\ =& [ dist(a, c) + dist(b, c) ] + [ dist(a, d) + dist(b, d)]\\ \geq &dist(a,b) + dist(a,b)\\ \geq &2dist(a,b)\\\end{split}\]Now, since \(S_1\) is the largest sum, we have
\[\begin{split}hyp(a, b, c, d) =& S_1  \max\{S_2, S_3\}\\ \leq& S_1  \frac{S_2+ S_3}{2}\\ \leq& S_1  dist(a, b)\\ =& dist(c, d)\\\end{split}\]We obtain similarly that \(hyp(a, b, c, d) \leq dist(a, b)\). Consequently, in the implementation of the ‘CCL’ algorithm, we ensure that \(S_1\) is larger than \(S_2\) and \(S_3\) using an ordering of the pairs by decreasing lengths. Then, we use the best value \(h\) found so far to stop exploration as soon as \(dist(a, b) \leq h\).
The worst case time complexity of this algorithm is \(O(n^4)\), but it performs very well in practice since it cuts the search space. This algorithm can be turned into an approximation algorithm since at any step of its execution we maintain an upper and a lower bound. We can thus stop execution as soon as a multiplicative approximation factor or an additive one is proven.
The notion of ‘’farapart pairs’’ has been introduced in [Sot2011] to further reduce the number of 4tuples to consider. We say that the pair \((a,b)\) is farapart if for every \(w\) in \(V\setminus\{a,b\}\) we have
\[dist(w,a)+dist(a,b) > dist(w,b) \text{ and }dist(w,b)+dist(a,b) > dist(w,a)\]Determining the set of farapart pairs can be done in time \(O(nm)\) using BFS. Now, it is proved in [Sot2011] that there exists two farapart pairs \((a,b)\) and \((c,d)\) satisfying \(\delta(G) = hyp(a, b, c, d)/2\). For instance, the \(n\times m\)grid has only two farapart pairs, and so computing its hyperbolicity is immediate once the farapart pairs are found. The ‘CCL+FA’ or ‘CCL+’ algorithm improves the ‘CCL’ algorithm since it uses farapart pairs.
This algorithm was further improved in [BCCM2015]: instead of iterating twice over all pairs of vertices, in the “inner” loop, we cut several pairs by exploiting properties of the underlying graph.
Todo
Add exact methods for the hyperbolicity of chordal graphs
Add method for partitioning the graph with clique separators
This module contains the following functions
At Python level :
Return the hyperbolicity of the graph or an approximation of this value. 

Return the hyperbolicity distribution of the graph or a sampling of it. 
AUTHORS:
David Coudert (2012): initial version, exact and approximate algorithm, distribution, sampling
David Coudert (2014): improved exact algorithm using farapart pairs
Michele Borassi (2015): cleaned the code and implemented the new algorithm
Karan Desai (2016): fixed minor typo in documentation
Methods#
 sage.graphs.hyperbolicity.hyperbolicity(G, algorithm='BCCM', approximation_factor=None, additive_gap=None, verbose=False)#
Return the hyperbolicity of the graph or an approximation of this value.
The hyperbolicity of a graph has been defined by Gromov [Gro1987] as follows: Let \(a, b, c, d\) be vertices of the graph, let \(S_1 = dist(a, b) + dist(b, c)\), \(S_2 = dist(a, c) + dist(b, d)\), and \(S_3 = dist(a, d) + dist(b, c)\), and let \(M_1\) and \(M_2\) be the two largest values among \(S_1\), \(S_2\), and \(S_3\). We have \(hyp(a, b, c, d) = M_1  M_2\), and the hyperbolicity of the graph is the maximum over all possible 4tuples \((a,b, c,d)\) divided by 2. The worst case time complexity is in \(O( n^4 )\).
See the documentation of
sage.graphs.hyperbolicity
for more information.INPUT:
G
– a connected Graphalgorithm
– (default:'BCCM'
); specifies the algorithm to use among:'basic'
is an exhaustive algorithm considering all possible 4tuples and so have time complexity in \(O(n^4)\).'CCL'
is an exact algorithm proposed in [CCL2015]. It considers the 4tuples in an ordering allowing to cut the search space as soon as a new lower bound is found (see the module’s documentation). This algorithm can be turned into a approximation algorithm.'CCL+FA'
or'CCL+'
uses the notion of farapart pairs as proposed in [Sot2011] to significantly reduce the overall computation time of the'CCL'
algorithm.'BCCM'
is an exact algorithm proposed in [BCCM2015]. It improves'CCL+FA'
by cutting several 4tuples (for more information, see the module’s documentation).'dom'
is an approximation with additive constant four. It computes the hyperbolicity of the vertices of a dominating set of the graph. This is sometimes slower than'CCL'
and sometimes faster. Try it to know if it is interesting for you. Theadditive_gap
andapproximation_factor
parameters cannot be used in combination with this method and so are ignored.
approximation_factor
– (default: None) When the approximation factor is set to some value (larger than 1.0), the function stop computations as soon as the ratio between the upper bound and the best found solution is less than the approximation factor. When the approximation factor is 1.0, the problem is solved optimally. This parameter is used only when the chosen algorithm is'CCL'
,'CCL+FA'
, or'BCCM'
.additive_gap
– (default: None) When sets to a positive number, the function stop computations as soon as the difference between the upper bound and the best found solution is less than additive gap. When the gap is 0.0, the problem is solved optimally. This parameter is used only when the chosen algorithm is'CCL'
or'CCL+FA'
, or'BCCM'
.verbose
– (default:False
) is a boolean set to True to display some information during execution: new upper and lower bounds, etc.
OUTPUT:
This function returns the tuple ( delta, certificate, delta_UB ), where:
delta
– the hyperbolicity of the graph (halfinteger value).certificate
– is the list of the 4 vertices for which the maximum value has been computed, and so the hyperbolicity of the graph.delta_UB
– is an upper bound fordelta
. Whendelta == delta_UB
, the returned solution is optimal. Otherwise, the approximation factor ifdelta_UB/delta
.
EXAMPLES:
Hyperbolicity of a \(3\times 3\) grid:
sage: from sage.graphs.hyperbolicity import hyperbolicity sage: G = graphs.Grid2dGraph(3, 3) sage: L,C,U = hyperbolicity(G, algorithm='BCCM'); L,sorted(C),U (2, [(0, 0), (0, 2), (2, 0), (2, 2)], 2) sage: L,C,U = hyperbolicity(G, algorithm='CCL'); L,sorted(C),U (2, [(0, 0), (0, 2), (2, 0), (2, 2)], 2) sage: L,C,U = hyperbolicity(G, algorithm='basic'); L,sorted(C),U (2, [(0, 0), (0, 2), (2, 0), (2, 2)], 2)
Hyperbolicity of a PetersenGraph:
sage: from sage.graphs.hyperbolicity import hyperbolicity sage: G = graphs.PetersenGraph() sage: L,C,U = hyperbolicity(G, algorithm='BCCM'); L,sorted(C),U (1/2, [6, 7, 8, 9], 1/2) sage: L,C,U = hyperbolicity(G, algorithm='CCL'); L,sorted(C),U (1/2, [0, 1, 2, 3], 1/2) sage: L,C,U = hyperbolicity(G, algorithm='CCL+'); L,sorted(C),U (1/2, [0, 1, 2, 3], 1/2) sage: L,C,U = hyperbolicity(G, algorithm='CCL+FA'); L,sorted(C),U (1/2, [0, 1, 2, 3], 1/2) sage: L,C,U = hyperbolicity(G, algorithm='basic'); L,sorted(C),U (1/2, [0, 1, 2, 3], 1/2) sage: L,C,U = hyperbolicity(G, algorithm='dom'); L,U (0, 1) sage: sorted(C) # random [0, 1, 2, 6]
Asking for an approximation in a grid graph:
sage: from sage.graphs.hyperbolicity import hyperbolicity sage: G = graphs.Grid2dGraph(2, 10) sage: L,C,U = hyperbolicity(G, algorithm='CCL', approximation_factor=1.5); L,U (1, 3/2) sage: L,C,U = hyperbolicity(G, algorithm='CCL+', approximation_factor=1.5); L,U (1, 1) sage: L,C,U = hyperbolicity(G, algorithm='CCL', approximation_factor=4); L,U (1, 4) sage: L,C,U = hyperbolicity(G, algorithm='CCL', additive_gap=2); L,U (1, 3) sage: L,C,U = hyperbolicity(G, algorithm='dom'); L,U (1, 5)
Asking for an approximation in a cycle graph:
sage: from sage.graphs.hyperbolicity import hyperbolicity sage: G = graphs.CycleGraph(10) sage: L,C,U = hyperbolicity(G, algorithm='CCL', approximation_factor=1.5); L,U (2, 5/2) sage: L,C,U = hyperbolicity(G, algorithm='CCL+FA', approximation_factor=1.5); L,U (2, 5/2) sage: L,C,U = hyperbolicity(G, algorithm='CCL+FA', additive_gap=1); L,U (2, 5/2)
Comparison of results:
sage: from sage.graphs.hyperbolicity import hyperbolicity sage: for i in range(10): # long time ....: G = graphs.RandomBarabasiAlbert(100,2) ....: d1,_,_ = hyperbolicity(G, algorithm='basic') ....: d2,_,_ = hyperbolicity(G, algorithm='CCL') ....: d3,_,_ = hyperbolicity(G, algorithm='CCL+') ....: d4,_,_ = hyperbolicity(G, algorithm='CCL+FA') ....: d5,_,_ = hyperbolicity(G, algorithm='BCCM') ....: l3,_,u3 = hyperbolicity(G, approximation_factor=2) ....: if (not d1==d2==d3==d4==d5) or l3>d1 or u3<d1: ....: print("That's not good!") sage: from sage.graphs.hyperbolicity import hyperbolicity sage: import random sage: random.seed() sage: for i in range(10): # long time ....: n = random.randint(2, 20) ....: m = random.randint(0, n*(n1) / 2) ....: G = graphs.RandomGNM(n, m) ....: for cc in G.connected_components_subgraphs(): ....: d1,_,_ = hyperbolicity(cc, algorithm='basic') ....: d2,_,_ = hyperbolicity(cc, algorithm='CCL') ....: d3,_,_ = hyperbolicity(cc, algorithm='CCL+') ....: d4,_,_ = hyperbolicity(cc, algorithm='CCL+FA') ....: d5,_,_ = hyperbolicity(cc, algorithm='BCCM') ....: l3,_,u3 = hyperbolicity(cc, approximation_factor=2) ....: if (not d1==d2==d3==d4==d5) or l3>d1 or u3<d1: ....: print("Error in graph ", cc.edges(sort=True))
The hyperbolicity of a graph is the maximum value over all its biconnected components:
sage: from sage.graphs.hyperbolicity import hyperbolicity sage: G = graphs.PetersenGraph() * 2 sage: G.add_edge(0, 11) sage: L,C,U = hyperbolicity(G); L,sorted(C),U (1/2, [6, 7, 8, 9], 1/2)
 sage.graphs.hyperbolicity.hyperbolicity_distribution(G, algorithm='sampling', sampling_size=1000000)#
Return the hyperbolicity distribution of the graph or a sampling of it.
The hyperbolicity of a graph has been defined by Gromov [Gro1987] as follows: Let \(a, b, c, d\) be vertices of the graph, let \(S_1 = dist(a, b) + dist(b, c)\), \(S_2 = dist(a, c) + dist(b, d)\), and \(S_3 = dist(a, d) + dist(b, c)\), and let \(M_1\) and \(M_2\) be the two largest values among \(S_1\), \(S_2\), and \(S_3\). We have \(hyp(a, b, c, d) = M_1  M_2\), and the hyperbolicity of the graph is the maximum over all possible 4tuples \((a, b, c, d)\) divided by 2.
The computation of the hyperbolicity of each 4tuple, and so the hyperbolicity distribution, takes time in \(O( n^4 )\).
INPUT:
G
– a Graph.algorithm
– (default: ‘sampling’) When algorithm is ‘sampling’, it returns the distribution of the hyperbolicity over a sample ofsampling_size
4tuples. When algorithm is ‘exact’, it computes the distribution of the hyperbolicity over all 4tuples. Be aware that the computation time can be HUGE.sampling_size
– (default: \(10^6\)) number of 4tuples considered in the sampling. Used only whenalgorithm == 'sampling'
.
OUTPUT:
hdict
– A dictionary such that hdict[i] is the number of 4tuples of hyperbolicity i.
EXAMPLES:
Exact hyperbolicity distribution of the Petersen Graph:
sage: from sage.graphs.hyperbolicity import hyperbolicity_distribution sage: G = graphs.PetersenGraph() sage: hyperbolicity_distribution(G,algorithm='exact') {0: 3/7, 1/2: 4/7}
Exact hyperbolicity distribution of a \(3\times 3\) grid:
sage: from sage.graphs.hyperbolicity import hyperbolicity_distribution sage: G = graphs.GridGraph([3,3]) sage: hyperbolicity_distribution(G,algorithm='exact') {0: 11/18, 1: 8/21, 2: 1/126}