Recent results on well-balanced orientations

Abstract

In this paper we consider problems related to Nash-Williams´ Strong Orientation Theorem and Odd-Vertex Pairing Theorem. These theorems date to 1960 and up to now not much is known about their relationship to other subjects in graph theory. We investigated many approaches to find a more transparent proof for these theorems and possibly generalizations of them. In many cases we found negative answers: counter-examples and NP-completeness results. For example we show that the weighted and the degree-constrained versions of the well-balanced orientation problem are NP-hard. We also show that it is NP-hard to find a minimum cost feasible odd-vertex pairing or to decide whether two graphs with some common edges have simultaneous well-balanced orientations or not. Nash-Williams´ original approach was to define best-balanced orientations with feasible odd-vertex pairings: we show here that not every best-balanced orientation can be obtained this way. However we prove that in the global case this is true: every smooth k-arc-connected orientation can be obtained through a k-feasible odd-vertex pairing. The aim of this paper is to help to find a transparent proof for the Strong Orientation Theorem. In order to achieve this we propose some other approaches and raise some open questions, too. (c) 2008 Elsevier B.V. All rights reserved.