Graph bandwidth

In graph theory, the graph bandwidth problem is to label the {{mvar|n}} vertices {{mvar|v{{sub|i}}}} of a graph {{mvar|G}} with distinct integers {{tmath|f(v_i)}} so that the quantity $\max\{\,| f(v_i) - f(v_j)| : v_iv_j \in E \,\}$ is minimized ({{mvar|E}} is the edge set of {{mvar|G}}).{{harv|Chinn|Chvátalová|Dewdney|Gibbs|1982}}

The problem may be visualized as placing the vertices of a graph at distinct integer points along the x-axis so that the length of the longest edge is minimized. Such placement is called linear graph arrangement, linear graph layout or linear graph placement.

The weighted graph bandwidth problem is a generalization wherein the edges are assigned weights {{mvar|w{{sub|ij}}}} and the cost function to be minimized is $\max\{\, w_{ij} |f(v_i) - f(v_j)| : v_iv_j \in E \,\}$ .

In terms of matrices, the (unweighted) graph bandwidth is the minimal bandwidth of a symmetric matrix which is an adjacency matrix of the graph.

The bandwidth may also be defined as one less than the maximum clique size in a proper interval supergraph of the given graph, chosen to minimize its clique size {{harv|Kaplan|Shamir|1996}}.

Cyclically interval graphs

For fixed $k$ define for every $i$ the set

$I_k(i) := [i, i+k+1)$ . $G_k(n)$ is the corresponding interval graph formed from

the intervals $I_k(1), I_k(2), ... I_k(n)$ . These are exactly the proper interval

graphs of graphs having bandwidth $k$ . These graphs called be

cyclically interval graphs because the intervals can be assigned to layers

$L_1, L_2, ... L_{k+1}$ in cyclically order, where the intervals of a layer doesn't

intersect.

Therefore, one see the relation to the pathwidth. Pathwidth restricted graphs are minor closed but

the set of subgraphs of cyclically interval graphs are not. This follows from the fact, that thrinking

degree 2 vertices may increase the bandwidth.

Alternate adding vertices on edges can decrease the bandwidth. Hint: The last problem is known as

topologic bandwidth. An other graph measure related through the bandwidth is the

bisection bandwidth.

Bandwidth formulas for some graphs

For several families of graphs, the bandwidth $\varphi(G)$ is given by an explicit formula.

The bandwidth of a path graph P_n on n vertices is 1, and for a complete graph K_m we have $\varphi(K_n)=n-1$ . For the complete bipartite graph K_m,n,

: $\varphi(K_{m,n}) = \lfloor (m-1)/2\rfloor+n$ , assuming $m \ge n\ge 1,$

which was proved by Chvátal.A remark on a problem of Harary. V. Chvátal, Czechoslovak Mathematical Journal 20(1):109–111, 1970. [http://dml.cz/dmlcz/100949 http://dml.cz/dmlcz/100949] As a special case of this formula, the star graph $S_k = K_{k,1}$ on k + 1 vertices has bandwidth $\varphi(S_{k}) = \lfloor (k-1)/2\rfloor+1$ .

For the hypercube graph $Q_n$ on $2^n$ vertices the bandwidth was determined by {{harvtxt|Harper|1966}} to be

: $\varphi(Q_n)=\sum_{m=0}^{n-1} \binom{m}{\lfloor m/2\rfloor}.$

Chvatálová showedOptimal Labelling of a product of two paths. J. Chvatálová, Discrete Mathematics 11, 249–253, 1975. that the bandwidth of the m × n square grid graph $P_m \times P_n$ , that is, the Cartesian product of two path graphs on $m$ and $n$ vertices, is equal to min{m,n}.

Bounds

The bandwidth of a graph can be bounded in terms of various other graph parameters. For instance, letting χ(G) denote the chromatic number of G,

: $\varphi(G) \ge \chi(G) - 1;$

letting diam(G) denote the diameter of G, the following inequalities hold:{{harvnb|Chinn|Chvátalová|Dewdney|Gibbs|1982}}

: $\lceil (n-1)/\operatorname{diam}(G) \rceil \le \varphi(G) \le n - \operatorname{diam}(G),$

where $n$ is the number of vertices in $G$ .

If a graph G has bandwidth k, then its pathwidth is at most k {{harv|Kaplan|Shamir|1996}}, and its tree-depth is at most k log(n/k) {{harv|Gruber|2012}}. In contrast, as noted in the previous section, the star graph S_k, a structurally very simple example of a tree, has comparatively large bandwidth. Observe that the pathwidth of S_k is 1, and its tree-depth is 2.

Some graph families of bounded degree have sublinear bandwidth: {{harvtxt|Chung|1988}} proved that if T is a tree of maximum degree at most ∆, then

: $\varphi(T) \le \frac{5n}{\log_\Delta n}.$

More generally, for planar graphs of bounded maximum degree at most ∆, a similar bound holds (cf. {{harvnb|Böttcher|Pruessmann|Taraz|Würfl|2010}}):

: $\varphi(G) \le \frac{20n}{\log_\Delta n}.$

Computing the bandwidth

Both the unweighted and weighted versions are special cases of the quadratic bottleneck assignment problem.

The bandwidth problem is NP-hard, even for some special cases.Garey–Johnson: GT40 Regarding the existence of efficient

approximation algorithms, it is known that the bandwidth is NP-hard to approximate within any constant, and this even holds when the input graphs are restricted to caterpillar trees with maximum hair length 2 {{harv|Dubey|Feige|Unger|2010}}.

For the case of dense graphs, a 3-approximation algorithm was designed by {{harvtxt|Karpinski|Wirtgen|Zelikovsky|1997}}.

On the other hand, a number of polynomially-solvable special cases are known."Coping with the NP-Hardness of the Graph Bandwidth Problem", Uriel Feige, Lecture Notes in Computer Science, Volume 1851, 2000, pp. 129-145, {{doi|10.1007/3-540-44985-X_2}} A heuristic algorithm for obtaining linear graph layouts of low bandwidth is the Cuthill–McKee algorithm. Fast multilevel algorithm for graph bandwidth computation was proposed in.

{{cite journal

| author = Ilya Safro and Dorit Ron and Achi Brandt

| title = Multilevel Algorithms for Linear Ordering Problems

| journal = ACM Journal of Experimental Algorithmics

| year = 2008

| pages = 1.4–1.20

| volume = 13

| doi=10.1145/1412228.1412232

}}

Applications

The interest in this problem comes from some application areas.

One area is sparse matrix/band matrix handling, and general algorithms from this area, such as Cuthill–McKee algorithm, may be applied to find approximate solutions for the graph bandwidth problem.

Another application domain is in electronic design automation. In standard cell design methodology, typically standard cells have the same height, and their placement is arranged in a number of rows. In this context, graph bandwidth problem models the problem of placement of a set of standard cells in a single row with the goal of minimizing the maximal propagation delay (which is assumed to be proportional to wire length).

References

{{Cite journal | last1 = Böttcher | first1 = J. | last2 = Pruessmann | first2 = K. P. | last3 = Taraz | first3 = A. | last4 = Würfl | first4 = A. | title = Bandwidth, expansion, treewidth, separators and universality for bounded-degree graphs | doi = 10.1016/j.ejc.2009.10.010 | journal = European Journal of Combinatorics | volume = 31 | pages = 1217–1227 | year = 2010 | issue = 5 | arxiv = 0910.3014 }}
{{Cite journal | last1 = Chinn | first1 = P. Z. |author1-link=Phyllis Chinn| last2 = Chvátalová | first2 = J. | last3 = Dewdney | first3 = A. K. |author3-link=Alexander Dewdney| last4 = Gibbs | first4 = N. E. | title = The bandwidth problem for graphs and matrices—a survey | journal = Journal of Graph Theory | volume = 6 | pages = 223–254| year = 1982 | issue = 3 | doi = 10.1002/jgt.3190060302 }}
{{citation

| last = Chung

| first = Fan R. K.

| author-link =Fan Chung

| year = 1988

| contribution = Labelings of Graphs

| editor-last = Beineke

| editor-first = Lowell W.

| editor2-last = Wilson

| editor2-first = Robin J.

| title = Selected Topics in Graph Theory

| publisher = Academic Press

| pages = 151–168

| isbn = 978-0-12-086203-0

| url = http://www.math.ucsd.edu/~fan/mypaps/fanpap/86log.PDF

}}

{{Cite journal | last1 = Dubey | first1 = C. | last2 = Feige | first2 = U. | last3 = Unger | first3 = W. | title = Hardness results for approximating the bandwidth | journal = Journal of Computer and System Sciences | volume = 77 | pages = 62–90| year = 2010 | doi = 10.1016/j.jcss.2010.06.006 | doi-access = free }}
{{cite book

| last = Garey

| first = M.R.

| author-link = Michael Garey

|author2=Johnson, D.S. |author-link2=David S. Johnson

| title = Computers and Intractability: A Guide to the Theory of NP-Completeness

| year = 1979

| publisher = W.H. Freeman

| location = New York

| isbn = 0-7167-1045-5

}}

{{Citation

| title = On Balanced Separators, Treewidth, and Cycle Rank

| year = 2012

| last = Gruber | first = Hermann

| journal = Journal of Combinatorics

| pages = 669–682

| volume = 3

| issue = 4

| doi=10.4310/joc.2012.v3.n4.a5

| arxiv = 1012.1344

}}

{{Cite journal | last1 = Harper | first1 = L. | title = Optimal numberings and isoperimetric problems on graphs | journal = Journal of Combinatorial Theory | volume = 1 | pages = 385–393 | year = 1966 | issue = 3 | doi = 10.1016/S0021-9800(66)80059-5 | doi-access = free }}
{{Citation

| title = Pathwidth, bandwidth, and completion problems to proper interval graphs with small cliques

| year = 1996

| journal = SIAM Journal on Computing

| pages = 540–561

| volume = 25

| issue = 3

| last1 = Kaplan | first1 = Haim

| last2 = Shamir | first2 = Ron

| doi=10.1137/s0097539793258143}}

{{Cite journal

| last1 = Karpinski | first1 = Marek

| last2 = Wirtgen | first2 = Jürgen

| last3 = Zelikovsky | first3 = Aleksandr

| title = An Approximation Algorithm for the Bandwidth Problem on Dense Graphs

| journal = Electronic Colloquium on Computational Complexity

| volume = 4 | number = 17

| year = 1997

| url = http://eccc.hpi-web.de/report/1997/017/

}}

External links

[http://www.csc.kth.se/~viggo/wwwcompendium/node53.html Minimum bandwidth problem], in: Pierluigi Crescenzi and Viggo Kann (eds.), A compendium of NP optimization problems. Accessed May 26, 2010.

Category:Graph algorithms

Category:Combinatorial optimization

Category:NP-hard problems

Category:Graph invariants