Imbalance is fixed parameter tractable

• The Imbalance Minimization problem on graphs asks for an ordering of the vertices such that the total imbalance is minimized.
• The problem finds several applications in graph drawing, and is known to be NP-hard.
• In this article, we show that the problem is fixed parameter tractable, when parameterized by the solution size, resolving an open question from the literature.

In the Imbalance Minimization problem we are given a graph G=(V,E)G=(V,E) and an integer b   and asked whether there is an ordering v1…vnv1…vn of V such that the sum of the imbalance of all the vertices is at most b  . The imbalance of a vertex vivi is the absolute value of the difference between the number of neighbors to the left and right of vivi. The problem is also known as the Balanced Vertex Ordering problem and it finds many applications in graph drawing. We show that this problem is fixed parameter tractable and provide an algorithm that runs in time 2O(blogb)⋅nO(1)2O(blogb)⋅nO(1). This resolves an open problem of Kára et al. [On the complexity of the balanced vertex ordering problem, in: COCOON, in: Lecture Notes in Comput. Sci., vol. 3595, 2005, pp. 849–858].