Vertex Ordering with Precedence Constraints

We study bipartite graph ordering problem, which arises in various domains such as production management, bioinformatics, and job scheduling with precedence constraints. In the bipartite vertex ordering problem, we are given a bipartite graph H = (B, S, E) where each vertex in B has a cost and each vertex in S has a profit. The goal is to find a minimum K together with an ordering < of the vertices of H, so that i < j whenever i is an element of B is adjacent to j is an element of S. Moreover, at each sub-order the difference between the costs and profits of the vertices in the suborder does not exceed K. The bipartite ordering problem is NP-complete when the weights are one, and the bipartite graph H is a bipartite circle graph. This restricted version was used in the study of the secondary structure of RNA in [11]. Thus, we seek exact algorithms for solving the bipartite ordering problem in classes with simpler structures than bipartite circle graphs. We give non-trivial polynomial time algorithms for finding the optimal solutions for bipartite permutation graphs, bipartite trivially perfect graphs, bipartite cographs, and trees. There are still several classes of bipartite graphs for which the ordering problem could be polynomial, such as bipartite interval graphs, bipartite convex graphs, bipartite chordal graphs, etc. In addition, we formulate the problem as a linear programming (LP) model and conduct experiments on random instances. We did not find any example with an integrality gap of two or more when limited to bipartite circle graphs with unit weights. No example with an integrality gap of more than 5/2 was found for arbitrary bipartite graphs with random weights. It would be interesting to investigate the possibility of designing a constant approximation algorithm for this problem.