Title : Degree-Constrained Graph Orientation: Maximum Satisfaction and Minimum Violation
Speaker : Hirotaka Ono (Kyushu University)


Abstract : 
A degree-constrained graph orientation of an undirected graph G is an 
assignment of a direction to each edge in G such that the outdegree 
of every vertex in the resulting directed graph satisfies a specified 
lower and/or upper bound. Such graph orientations have been studied 
for a long time and various characterizations of their existence are 
known. In this paper, we consider four related optimization problems 
introduced in [4]: For any fixed non-negative integer W, the problems 
Max W -Light, Min W -Light, Max W -Heavy, and Min W -Heavy take as 
input an undirected graph G and ask for an orientation of G that 
maximizes or minimizes the number of vertices with outdegree at most 
W or at least W. The problems’ computational complexities vary with 
W. Here, we resolve several open questions related to their polynomial-
time approximability and present a number of positive and negative results.
This is a joint work with Yuichi Asahiro, Jesper Jansson, Eiji Miyano.