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
