On the Complexity of the Max Balance Problem

We study the computational complexity of the Maximum Balance problem. Namely, the aim of this paper is to trace out the borderline between instances for which the problem is easy and instances for which it is NP-hard. On one side, we extend the class of graphs for which the problem is polynomially solvable; on the other side we give a tighter NP-hardness result.