Computing the Cutwidth of Bipartite Permutation Graphs in Linear Time
Pinar Heggernes, Pim van ’t Hof, Daniel Lokshtanov, Jesper Nederlof · SIAM Journal on Discrete Mathematics · 2012
The problem of determining the cutwidth of a graph is a notoriously hard problem which remains NP-complete under severe restrictions on input graphs. Until recently, nontrivial polynomial-time cutwidth algorithms were known only for subclasses of graphs of bounded treewidth. Very recently, Heggernes et al. (SIAM J. Discrete Math., 25 (2011), pp. 1418--1437) initiated the study of cutwidth on graph classes containing graphs of unbounded treewidth and showed that a greedy algorithm computes the cutwidth of threshold graphs. We continue this line of research and present the first polynomial-time algorithm for computing the cutwidth of bipartite permutation graphs. Our algorithm runs in linear time. We stress that the cutwidth problem is NP-complete on bipartite graphs and its computational complexity is open even on small subclasses of permutation graphs, such as trivially perfect graphs.