An SDP Relaxation for the Cutwidth Minimization Problem

The Cutwidth Minimization Problem is a linear ordering problem on graphs, whose applications include natural language processing, information retrieval, graph drawing, and network migration scheduling. It is an NP-hard problem, for which several heuristics and metaheuristics have been designed in order to compute upper bounds. Regarding lower bounds, integer linear programming models have been introduced, some with very good results on sparse graphs. However, even the best approaches see their performance decrease with the density and the size of the instances. We introduce a new semidefinite relaxation for the Cutwidth Minimization Problem and investigate ways to efficiently strengthen it, using valid inequalities. This results in a significant improvement of the lower bound for dense graphs. These methods can then be used to minimize other graph parameters such as the pathwidth or the bandwidth.