{{Short description|Node labeling problem in graph theory}} {{CS1 config|mode=cs1}} In graph theory, the '''graph bandwidth problem''' may be visualized as placing the vertices of a given graph at distinct integer positions along the number line so that the length of the longest edge is minimized. Such placement is called '''linear graph arrangement''', '''linear graph layout''' or '''linear graph placement'''.<ref name=feige/> It may be formalized as labeling the <math>n</math> vertices <math>v_i</math> of a graph <math>G</math> with distinct integers <math>f(v_i)</math> so that the quantity <math>\max\{\,| f(v_i) - f(v_j)| : v_iv_j \in E \,\}</math> is minimized, where <math>E</math> is the edge set of <math>G</math>.<ref name=ccdg>{{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 }}</ref>
The '''weighted graph bandwidth problem''' is a generalization wherein the edges are assigned weights <math>w_{ij}</math> and the cost function to be minimized is the product of weight with length, <math>\max\{\, w_{ij} |f(v_i) - f(v_j)| : v_iv_j \in E \,\}</math>.
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.<ref name=ks>{{cite journal | 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}}</ref>
==Bandwidth formulas for some graphs== For several families of graphs, the bandwidth <math>\varphi(G)</math> is given by an explicit formula.
The bandwidth of a path graph <math>P_n</math> on <math>n</math> vertices is 1, and the bandwidth of a complete graph <math>K_m</math> is <math>\varphi(K_n)=n-1</math>. For the complete bipartite graph <math>K_{m,n}</math>, <math display=block>\varphi(K_{m,n}) = \lfloor (m-1)/2\rfloor+n,</math> assuming <math>m \ge n\ge 1</math>. As a special case of this formula, the star graph <math>S_k = K_{k,1}</math> on <math>k+1</math> vertices has bandwidth <math>\varphi(S_{k}) = \lfloor (k-1)/2\rfloor+1</math>.<ref>{{cite journal | last = Chvátal | first = Václav | author-link = Václav Chvátal | doi = 10.21136/CMJ.1970.100949 | hdl = 10338.dmlcz/100949 | issue = 1 | journal = Czechoslovak Mathematical Journal | mr = 266791 | pages = 109–111 | title = A remark on a problem of Harary | volume = 20 | year = 1970| hdl-access = free }}</ref>
For the hypercube graph <math>Q_n</math> on <math>2^n</math> vertices the bandwidth is<ref>{{cite journal | last = Harper | first = L. H. | doi = 10.1016/S0021-9800(66)80059-5 | journal = Journal of Combinatorial Theory | mr = 200192 | pages = 385–393 | title = Optimal numberings and isoperimetric problems on graphs | volume = 1 | year = 1966}}</ref> <math display=block>\varphi(Q_n)=\sum_{m=0}^{n-1} \binom{m}{\lfloor m/2\rfloor}.</math>
The bandwidth of the <math>m\times n</math> square grid graph <math>P_m \times P_n</math>, that is, the Cartesian product of two path graphs on <math>m</math> and <math>n</math> vertices, is equal to <math>\min\{m,n\}</math>.<ref>{{cite journal | last = Chvátalová | first = Jarmila | doi = 10.1016/0012-365X(75)90039-4 | journal = Discrete Mathematics | mr = 427150 | pages = 249–253 | title = Optimal labelling of a product of two paths | volume = 11 | year = 1975}}</ref>
==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'',
: <math> \varphi(G) \ge \chi(G) - 1; </math>
letting diam(''G'') denote the diameter of ''G'', the following inequalities hold:<ref name=ccdg/>
:<math>\lceil (n-1)/\operatorname{diam}(G) \rceil \le \varphi(G) \le n - \operatorname{diam}(G),</math>
where <math>n</math> is the number of vertices in <math>G</math>.
If a graph ''G'' has bandwidth ''k'', then its pathwidth is at most ''k'',<ref name=ks/> and its tree-depth is at most ''k'' log(''n''/''k'').<ref>{{cite journal | 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 }}</ref> In contrast, as noted in the previous section, the star graph ''S''<sub>''k''</sub>, a structurally very simple example of a tree, has comparatively large bandwidth. Observe that the pathwidth of ''S''<sub>''k''</sub> is 1, and its tree-depth is 2.
Some graph families of bounded degree have sublinear bandwidth: if ''T'' is a tree of maximum degree at most ∆, then <ref>{{cite book | last = Chung | first = Fan R. K. | author-link =Fan Chung | year = 1988 | contribution = Labelings of Graphs | editor-last = Beineke | editor-first = Lowell W. |editor-link=L. W. Beineke | editor2-last = Wilson | editor2-first = Robin J. |editor2-link=Robin Wilson (mathematician) | 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 }}</ref>
:<math>\varphi(T) \le \frac{5n}{\log_\Delta n}. </math>
More generally, for planar graphs of bounded maximum degree at most ''∆'', a similar bound holds:<ref>{{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 }}</ref>
:<math>\varphi(G) \le \frac{20n}{\log_\Delta n}.</math>
==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.<ref>{{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 | contribution = Problem GT40 }}</ref> 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.<ref>{{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 }}</ref> For arbitrary graphs with <math>n</math> vertices, the best approximation ratio known is <math>O(\log^3 n\sqrt{\log\log n})</math>, using semidefinite programming.<ref>{{cite book | last1 = Dunagan | first1 = John | last2 = Vempala | first2 = Santosh S. | editor1-last = Goemans | editor1-first = Michel X. | editor2-last = Jansen | editor2-first = Klaus | editor3-last = Rolim | editor3-first = José D. P. | editor4-last = Trevisan | editor4-first = Luca | contribution = On Euclidean embeddings and bandwidth minimization | doi = 10.1007/3-540-44666-4_26 | pages = 229–240 | publisher = Springer | series = Lecture Notes in Computer Science | title = Approximation, Randomization and Combinatorial Optimization: Algorithms and Techniques, 4th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2001 and 5th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2001 Berkeley, CA, USA, August 18–20, 2001, Proceedings | volume = 2129 | year = 2001}}</ref> For the case of dense graphs, a 3-approximation algorithm is known.<ref>{{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/ }}</ref> On the other hand, a number of polynomially-solvable special cases are known.<ref name=feige>{{cite book | last = Feige | first = Uriel | author-link = Uriel Feige | editor-last = Halldórsson | editor-first = Magnús M. | contribution = Coping with the NP-hardness of the graph bandwidth problem | doi = 10.1007/3-540-44985-X_2 | pages = 10–19 | publisher = Springer | series = Lecture Notes in Computer Science | title = Algorithm Theory – SWAT 2000, 7th Scandinavian Workshop on Algorithm Theory, Bergen, Norway, July 5–7, 2000, Proceedings | volume = 1851 | year = 2000}}</ref> 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.<ref name="multilevellinord"> {{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 }}</ref>
==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).
==See also== *Cutwidth and pathwidth, different NP-complete optimization problems involving linear layouts of graphs.
==References== {{reflist}}
==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