On finding orientations with the fewest number of vertices with small out-degree

Given an undirected graph, each of the two end-vertices of an edge can “own” the edge. Call a vertex “poor” if it owns at most one edge. We give a polynomial time algorithm for the problem of finding an assignment of owners to the edges which minimizes the number of poor vertices. In the terminology of graph orientation, this means finding an orientation for the edges of a graph which minimizes the number of vertices with out-degree at most 1, and answers a question of Asahiro et al. (2013).