Maximum cut with the smallest number of backward arcs

Abstract

In this paper, we focus on determining a maximum cut containing the smallest number of backward arcs from among all maximum cuts in a given network. We will solve this problem by reducing it to a standard maximum cut problem in a transformed network.