Graph Classes and the Complexity of the Graph Orientation Minimizing the Maximum Weighted Outdegree

Asahiro, Y., Miyano, E. and Ono, H.

    Given an undirected graph with edge weights, we are asked to find an orientation, i.e., 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 previous studies, it is shown that MMO is in P for trees, weak NP-hard for planar bipartite graphs and strong NP-hard for general graphs. There are still gaps between those graph classes. The objective of this paper is to show tight thresholds of complexity: We show that MMO is (i) in P for cactuses, (ii) weakly NP-hard for outerplanar graphs, and also (iii) strongly NP-hard for P4-bipartite graphs. The latter two are minimal superclasses of the former. Also, we show the NP-hardness for the other related graph classes, diamond-free, house-free, series-parallel, bipartite and planar.
Cite as: Asahiro, Y., Miyano, E. and Ono, H. (2008). Graph Classes and the Complexity of the Graph Orientation Minimizing the Maximum Weighted Outdegree. In Proc. Fourteenth Computing: The Australasian Theory Symposium (CATS 2008), Wollongong, NSW, Australia. CRPIT, 77. Harland, J. and Manyem, P., Eds. ACS. 97-106.
pdf (from crpit.com) pdf (local if available) BibTeX EndNote GS