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:

\[\begin{split}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|\\\end{split}\]

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