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 P P for trees, weak NP NP -hard for planar bipartite graphs, and strong NP NP -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 P P for cactus graphs, (ii) weakly NP NP -hard for outerplanar graphs, and also (iii)strongly NP NP -hard for graphs which are both planar and bipartite. This implies the NP NP -hardness for P4 P 4 -bipartite, diamond-free or house-free graphs, each of which is a superclass of cactus. We also show (iv)the NP NP -hardness for seriesparallel graphs and multi-outerplanar graphs, and (v)present a pseudo-polynomial time algorithm for graphs with bounded treewidth.
graph orientation cactus seriesparallel minmax optimization np np -hardness np np np np np (outer)planar (p4 p 4 -)bipartite p4 p 4 p4 p 4 p 4