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

Mittwoch, 19.04.2023, 10.30 Uhr

Ort: RWTH Aachen University, Informatikzentrum - Ahornstr. 55, Erweiterungsgebäude E3, Raum 9u10

Vortragende: Komal Muluk

 

Abstract:

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.