Imbalance Parameterized by Twin Cover

Abstract

Joint work with Harshil Mittal ⸱ Published in Theoretical Computer Science (Dec 2021) ⸱ A shorter version was accepted at COCOON 2020 ⸱ Preprint available from ArXiV

Imbalance is a layout optimization problem, where we would like to order the vertices of a graph so that, roughly speaking, vertices have their neighbors split up as equally as possible on their left and right. We examine the parameterized complexity of the problem with respect to a structural parameter called twin cover.