Title: Make a graph singly connected by edge orientations Show Chinese title

Title: 通过边的方向确定使图单连通

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. Show Chinese abstract

Abstract: 有向图$D$是单连通的，如果对于每一对顶点$(s,t)$，在$D$中从$s$到$t$的路径最多有一条。 图定向问题要求，给定一个无向图$G$，找到边的定向方式，使得结果有向图$D$具有某种性质。 在本工作中，我们研究图定向问题，其中期望的性质是$D$是单连通的。 我们的主要结果涉及固定围长$g$和着色数$c$的图。 对于每个$g,c\geq 3$，限制在围长为$g$且着色数为$c$的实例上，该问题要么是 NP 完全的，要么是在 P 中的。作为进一步的算法结果，我们表明该问题在平面图上是 NP 难的，并且在距离遗传图上是多项式时间可解的。