Make a Graph Singly Connected by Edge Orientations

Summary

A directed graph D is singly connected if for every ordered pair of vertices (s, t), there is at most one path from s to t in D. Graph orientation problems ask, given an undirected graph G, to find an orientation of the edges such that the resultant directed graph D has a certain property. In this work, we study the graph orientation problem where the desired property is that D is singly connected. Our main result concerns graphs of a fixed girth g and coloring number c. For every \(g,c\ge 3\), the problem restricted to instances of girth g and coloring number c, is either NP-complete or in P. As further algorithmic results, we show that the problem is NP-hard on planar graphs and polynomial time solvable distance-hereditary graphs.