Make a graph singly connected by edge orientations

arXiv (Cornell University)

Abstract

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\geq 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.

Authors 2

1. Tim A. Hartmann

   Helmholtz Center for Information Security

   Affiliation as printed

   CISPA Helmholtz Center for Information Security , Saarbrücken , Germany

2. Komal Muluk Aachen

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University , Germany