Computing the cutwidth of bipartite permutation graphs in linear time
Pinar Heggernes, Pim van 't Hof, Daniel Lokshtanov and Jesper Nederlof
SIAM Journal on Discrete Mathematics, vol. 26, no. 3, pp. 1008-1021, 2012.
[DOI][Preprint]
A preliminary version of this paper appeared in the proceedings of WG 2010, the 36th International Workshop on Graph-Theoretic Concepts in Computer Science (held on June 28-30, 2010, Zarós, Greece), Lecture Notes in Computer Science, vol. 6410, pp. 75-87, 2010.
[DOI]
Abstract:
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, non-trivial polynomial-time cutwidth algorithms were known only for subclasses of graphs of bounded treewidth. In WG 2008, Heggernes et al. 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.