Bi-Weekly Talk: Komal Muluk: Make a graph singly connected by edge orientations

Wednesday, April 19, 2023, 10:30am

Location: RWTH Aachen University, Department of Computer Science - Ahornstr. 55, building E3, room 9u10

Speaker: Komal Muluk



A directed graph is said to be singly connected if for every ordered pair its vertices (s,t), there is at most one path from s to t in the digraph. 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. 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 and coloring number. For every g, c ≥ 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 the problem is NP-hard on planar graphs and polynomial time solvable on graph classes such as distance-hereditary graphs and series-parallel graphs.