Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree

Given an undirected graph with edge weights, we are asked to find an orientation, that is, an assignment of a direction to each edge, so as to minimize the weighted maximum outdegree in the resulted directed graph. The problem is called MMO, and is a restricted variant of the well-known minimum makespan problem. As in previous studies, it is shown that MMO is in PP for trees, weak NPNP-hard for planar bipartite graphs, and strong NPNP-hard for general graphs. There are still gaps between those graph classes. The objective of this paper is to show tighter thresholds of complexity: We show that MMO is (i) in PP for cactus graphs, (ii) weakly NPNP-hard for outerplanar graphs, and also (iii) strongly NPNP-hard for graphs which are both planar and bipartite. This implies the NPNP-hardness for P4P4-bipartite, diamond-free or house-free graphs, each of which is a superclass of cactus. We also show (iv) the NPNP-hardness for series–parallel graphs and multi-outerplanar graphs, and (v) present a pseudo-polynomial time algorithm for graphs with bounded treewidth.