A New Lower Bound for the Minimum Linear Arrangement of a Graph

Given a graph G=(V,E) on n vertices, the Minimum Linear Arrangement Problem (MinLA) calls for a one-to-one function which minimizes ∑{i,j}∈E|ψ(i)−ψ(j)|. MinLA is strongly NP-hard and very difficult to solve to optimality in practice. One of the reasons for this difficulty is the lack of good lower bounds. In this paper, we take a polyhedral approach to MinLA. We associate an integer polyhedron with each graph G, and derive many classes of valid linear inequalities. It is shown that a cutting plane algorithm based on these inequalities can yield competitive lower bounds in a reasonable amount of time. A key to the success of our approach is that our linear programs contain only |E| variables. We conclude showing computational results on benchmark graphs from literature.