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.
200 University Avenue West
Waterloo, ON N2L 3G1