Finding shortest non-separating and non-disconnecting paths

Yasuaki Kobayashi, Shunsuke Nagano, Yota Otachi

For a connected graph $G=(V,E)$ and $s,t\in V$, a non-separating $s$-$t$ path is a path $P$ between $s$ and $t$ such that the set of vertices of $P$ does not separate $G$, tha…