PhD Seminar • Algorithms and Complexity — Cutwidth, Imbalance, and the Structure of Optimal Orderings

Jan Gorzny, PhD candidate
David R. Cheriton School of Computer Science

We show that both Cutwidth and Imbalance are fixed-parameter tractable when parameterized by the twin-cover number of the input graph. We further show that Imbalance is NP-complete for split graphs and linear-time solvable for proper interval (bipartite) graphs, which equals the complexity of Cutwidth on these classes. Both results follow from a new structural theorem, that every instance of Cutwidth or Imbalance has an optimal ordering of a restricted form. This is joint work with Jonathan Buss.