Bandwidth of undirected graphs

Bandwidth of undirected graphs

Definition

The bandwidth bw(M) of a matrix M is the smallest integer k such that all non-zero entries of M are at distance k from the diagonal. The bandwidth bw(G) of an undirected graph G is the minimum bandwidth of the adjacency matrix of G, over all possible relabellings of its vertices.

Path spanner: alternatively, the bandwidth measures how tightly a path represents the distance of a graph G. Indeed, if the vertices of G can be ordered as v_1,...,v_n in such a way that k \times d_G(v_i,v_j) \geq |i-j| then bw(G)\leq k.

Proof: for all v_i \sim v_j (i.e. d_G(v_i,v_j)=1), the constraint ensures that k\geq |i-j|, meaning that adjacent vertices are at distance at most k in the path ordering. That alone is sufficient to ensure that bw(G)\leq k.

As a byproduct, we obtain that k \times d_G(v_i,v_j) \geq |i-j| in general: let v_{s_0},...,v_{s_i} be the vertices of a shortest (v_i,v_j)-path. We have:

k \times d_G(v_i,v_j) &=    k\times d_G(v_i,v_{s_0}) + k\times d_G(v_{s_0},v_{s_1}) + ... + k\times d_G(v_{s_{i-1}},v_{s_i}) + k\times d_G(v_{s_i},v_j)\\
                      &\geq |v_i-v_{s_0}| + |v_{s_0}-v_{s_1}| + ... + |v_{s_{i-1}}-v_{s_i}| + |v_{s_i}-v_j|\\
                      &\geq |v_i-v_j|\\

Satisfiability of a partial assignment

Let us suppose that the first i vertices v_1,...,v_i of G have already been assigned positions p_1,...,p_i in an ordering of V(G) of bandwidth \leq k. Where can v_{i+1} appear ?

Because of the previous definition, p_{i+1} must be at distance at most k\times d_G(v_1,v_{i+1}) from p_1, and in general at distance at most k\times d_G(v_j,v_{i+1}) from p_j. Each range is an interval of \{1,...,n\}\backslash \{p_1,...,p_i\}, and because the intersection of two intervals is again an interval we deduce that in order to satisfy all these constraints simultaneously p_j must belong to an interval defined from this partial assignment.

Applying this rule to all non-assigned vertices, we deduce that each of them must be assigned to a given interval of \{1,...,n\}. Note that this can also be extended to the already assigned vertices, by saying that v_j with j<i must be assigned within the interval [p_j,p_j].

This problem is not always satisfiable, e.g. 5 vertices cannot all be assigned to the elements of [10,13]. This is a matching problem which, because all admissible sets are intervals, can be solved quickly.

Solving the matching problem

Let n points v_1,...,v_n be given, along with two functions m,M:[n]\mapsto
[n]. Is there an ordering p_1,...,p_n of them such that m(v_i) \leq p_i \leq
M(v_i) ? This is equivalent to Hall’s bipartite matching theorem, and can in this specific case be solved by the following algorithm:

  • Consider all vertices v sorted increasingly according to M(v)
  • For each of them, assign to v the smallest position in [m(v),M(v)] which has not been assigned yet. If there is none, the assignment problem is not satisfiable.

Note that the latest operation can be performed with very few bitset operations (provided that n<64).

The algorithm

This section contains totally subjective choices, that may be changed in the hope to get better performances.

  • Try to find a satisfiable ordering by filling positions, one after the other (and not by trying to find each vertex’ position)
  • Fill the positions in this order: 0,n-1,1,n-2,3,n-3, ...

Note

There is some symmetry to break as the reverse of a satisfiable ordering is also a satisfiable ordering.

Functions

sage.graphs.graph_decompositions.bandwidth.bandwidth(G, k=None)

Compute the bandwidth of an undirected graph.

For a definition of the bandwidth of a graph, see the documentation of the bandwidth module.

INPUT:

  • G (a graph)
  • k – set to an integer value to test whether bw(G)\leq k, or to None (default) to compute bw(G).

OUTPUT:

When k is an integer value, the function returns either False or an ordering of cost \leq k.

When k is equal to None, the function returns a pair (bw, ordering).

See also

sage.graphs.generic_graph.GenericGraph.adjacency_matrix() – return the adjacency matrix from an ordering of the vertices.

EXAMPLES:

sage: from sage.graphs.graph_decompositions.bandwidth import bandwidth
sage: G = graphs.PetersenGraph()
sage: bandwidth(G,3)
False
sage: bandwidth(G)
(5, [0, 4, 5, 8, 1, 9, 3, 7, 6, 2])
sage: G.adjacency_matrix(vertices=[0, 4, 5, 8, 1, 9, 3, 7, 6, 2])
[0 1 1 0 1 0 0 0 0 0]
[1 0 0 0 0 1 1 0 0 0]
[1 0 0 1 0 0 0 1 0 0]
[0 0 1 0 0 0 1 0 1 0]
[1 0 0 0 0 0 0 0 1 1]
[0 1 0 0 0 0 0 1 1 0]
[0 1 0 1 0 0 0 0 0 1]
[0 0 1 0 0 1 0 0 0 1]
[0 0 0 1 1 1 0 0 0 0]
[0 0 0 0 1 0 1 1 0 0]
sage: G = graphs.ChvatalGraph()
sage: bandwidth(G)
(6, [0, 5, 9, 4, 10, 1, 6, 11, 3, 8, 7, 2])
sage: G.adjacency_matrix(vertices=[0, 5, 9, 4, 10, 1, 6, 11, 3, 8, 7, 2])
[0 0 1 1 0 1 1 0 0 0 0 0]
[0 0 0 1 1 1 0 1 0 0 0 0]
[1 0 0 0 1 0 0 1 1 0 0 0]
[1 1 0 0 0 0 0 0 1 1 0 0]
[0 1 1 0 0 0 1 0 0 1 0 0]
[1 1 0 0 0 0 0 0 0 0 1 1]
[1 0 0 0 1 0 0 1 0 0 0 1]
[0 1 1 0 0 0 1 0 0 0 1 0]
[0 0 1 1 0 0 0 0 0 0 1 1]
[0 0 0 1 1 0 0 0 0 0 1 1]
[0 0 0 0 0 1 0 1 1 1 0 0]
[0 0 0 0 0 1 1 0 1 1 0 0]

TESTS:

sage: bandwidth(2*graphs.PetersenGraph())
(5, [0, 4, 5, 8, 1, 9, 3, 7, 6, 2, 10, 14, 15, 18, 11, 19, 13, 17, 16, 12])
sage: bandwidth(Graph())
(0, [])
sage: bandwidth(Graph(1))
(0, [0])
sage: bandwidth(Graph(3))
(0, [0, 1, 2])

Directed/weighted graphs:

sage: bandwidth(digraphs.Circuit(5))
Traceback (most recent call last):
...
ValueError: This method only works on undirected graphs
sage: bandwidth(Graph(graphs.PetersenGraph(), weighted=True))
Traceback (most recent call last):
...
ValueError: This method only works on unweighted graphs

Table Of Contents

Previous topic

Rank Decompositions of graphs

Next topic

Products of graphs

This Page