Bandwidth Problem in Graphs

Abstract

Bandwidth is a graph layout problem that is known for its difficulty even on small graph classes. The bandwidth problem of an arbitrary graph is known to be NP-complete. It is NP-complete even for a tree of maximum degree 3. Bandwidth problem is amongst the most studied graph layout problems and intuitively, it seems to be harder to solve than various other graph layout problems like pathwidth and vertex separation. Bandwidth is a benchmark problem known for its difficulty among the often studied NP-hard graph problems. Surprisingly, to our knowledge, few polynomial time algorithms for exact computation of bandwidth are known only for caterpillars of hair length at most 2, chain graphs, cographs, interval graphs and bipartite permutation graphs. The following relationship between these classes of graphs is known : Bipartite Permutation Graphs ⊂ Biconvex Bipartite Graphs ⊂ Convex Bipartite Graphs ⊂ 2-directional Orthogonal Ray Graphs ⊂ Chordal Bipartite Graphs. In the above mentioned family, bandwidth problem is NP-complete for convex bipartite graphs and all its super classes. Polynomial time algorithm have been given for bipartite permutation graphs. But for Biconvex Bipartite graph, no standard result has been proposed. The NP-completeness of bandwidth problem in graphs has been traditionally proved using multiple processor scheduling problem. The multiple processor scheduling problem is known to be strongly NP-complete and is reduced to the bandwidth problem in certain graph classes and hence the latter is also proved to be NP-complete. In this thesis, we propose that bandwidth problem is not NP-complete for biconvex bipartite graphs. This result, though, cannot be accepted as a formal proof as we only prove that NP-Completeness cannot be proved by using the traditional method of multiple processor scheduling problem reduction to bandwidth problem in case of biconvex bipartite graphs. We see that polynomial time algorithms have been given ix x for Bipartite Permutation graph which is the nearest established subset of biconvex bipartite graphs. We try to extend a similar approach for biconvex bipartite graphs. We expect to obtain a polynomial time algorithm though it is still under development