Finding shortest non-separating and non-disconnecting paths

Suppose first that $G$ has a clique $C$ with $C\cap V_{i}=\{v_{i}\}$ for $1\leq i\leq k$. Then, $P={\langle s,v_{1},v_{2},\ldots,v_{k},t\rangle}$ is an $s$-$t$ path of length $k+1$ in $H$. To see the connectivity of $H-V(P)$, it suffices to show that every vertex is reachable to $v^{*}$ in $H-V(P)$. By the construction of $H$, each vertex in $V(G)\setminus V(P)$ is adjacent to $v^{*}$ in $H-V(P)$. Each vertex $z$ in $V(H)\setminus(V(G)\cup\{v^{*},p\})$ is either the internal vertex $w$ of $P_{u,v}$ for some $u,v\in V(G)$ or the pendant vertex adjacent to $w$. In both cases, at least one of $u$ and $v$ is not contained in $P$ as $V(P)\setminus\{s,t\}$ is a clique in $G$, implying that $z$ is reachable to $v^{*}$.

Conversely, suppose that $H$ has a non-separating $s$-$t$ path $P$ of length at most $k+1$ in $H$. By the assumption that $G$ has more than $k$ vertices, there is a vertex of $G$ that does not belong to $P$. Observe that $P$ does not contain any internal vertex $w$ of some $P_{u,v}$ as otherwise the pendant vertex adjacent to $w$ becomes an isolated vertex by deleting $V(P)$, which implies $H-V(P)$ has at least two connected components. Similarly, $P$ does not contain $v^{*}$. These facts imply that the internal vertices of $P$ belong to $V(G)$, and we have $|V(P)\cap V_{i}|=1$ for $1\leq i\leq k$. Let $C=V(P)\setminus\{s,t\}$. We claim that $C$ is a clique in $G$. Suppose otherwise. There is a pair of vertices $u,v\in C$ that are not adjacent in $G$. This implies that $H$ contains the path $P_{u,v}$. However, as $P$ contains both $u$ and $v$, the internal vertex of $P_{u,v}$ together with its pendant vertex forms a component in $H-V(P)$, yielding a contradiction that $P$ is a non-separating path in $H$.

Suppose first that $P$ is non-separating in $G$. Let $u,v\in V(G)\setminus V(P)$ be arbitrary. As $P$ is non-separating, there is a $u$-$v$ path $P^{\prime}$ in $G-V(P)$. Let $u^{\prime}$ be the vertex of $G_{C}$ such that $u^{\prime}=u$ if $u\notin C$ and $u^{\prime}=v_{C}$ if $u\in C$. Let $v^{\prime}$ be the vertex defined analogously. We show that there is a $u^{\prime}$-$v^{\prime}$ path in $G_{C}-V(P)$ as well. If $P^{\prime}$ does not contain any vertex in $C$, it is also a $u^{\prime}$-$v^{\prime}$ path in $G_{C}$, and hence we are done. Suppose otherwise. Let $x$ and $y$ be the vertices in $V(P^{\prime})\cap C$ that are closest to $u$ and $v$, respectively. Note that $x$ and $y$ can be the end vertices of $P^{\prime}$, that is, $C$ may contain $u$ and $v$. Let $P_{u,x}$ and (resp. $P_{y,v}$) be the subpath of $P^{\prime}$ between $u$ and $x$ (resp. $y$ and $v$). Then, the sequence of vertices obtained by concatenating $P_{u,x}$ after $P_{y,v}-\{y\}$ and replacing exactly one occurrence of a vertex in $C$ with $v_{C}$ forms a path between $u^{\prime}$ and $v^{\prime}$. Since we choose $u,v$ arbitrarily, there is a path between any pair of vertices in $G_{C}-V(P)$ as well. Hence, $P$ is non-separating in $G_{C}$.

Conversely, suppose that $P$ is non-separating in $G_{C}$. For $u,v\in V(G_{C})\setminus V(P)$, there is a path $P^{\prime}$ in $G_{C}-V(P)$. Suppose that neither $u=v_{C}$ nor $v=v_{C}$. Then, we can construct a $u$-$v$ path in $G-V(P)$ as follows. If $v_{C}\notin V(P^{\prime})$, $P^{\prime}$ is also a path in $G-V(P)$ and hence we are done. Otherwise, $v_{C}\in V(P^{\prime})$. Let $P_{u}$ and $P_{v}$ be the subpaths in $P^{\prime}-\{v_{C}\}$ containing $u$ and $v$, respectively. From $P_{u}$ and $P_{v}$, we have a $u$-$v$ path in $G$ by connecting them with an arbitrary path in $G[C]$ between the end vertices other than $u$ and $v$. Note that such a bridging path in $G[C]$ always exists since $G[C]$ is connected. Moreover, as $V(P^{\prime})\cap C=\emptyset$ and $V(P)\cap C=\emptyset$, this is also a $u$-$v$ path in $G-V(P)$. Suppose otherwise that either $u=v_{C}$ or $v=v_{C}$, say $u=v_{C}$. In this case, we can construct a path between every vertex $w$ in $C$ and $v$ by concatenating $P^{\prime}$ and an arbitrary path in $G[C]$ between $w$ and the end vertex of the subpath $P^{\prime}-\{v_{C}\}$ other than $v$. Therefore, $P$ is non-separating in $G$.

Let $G\in\mathcal{C}$. We first compute $B=\{v\in V(G):{\rm dist}(s,v)\leq k\}$. This can be done in linear time. If $t\notin B$, then the instance $(G,s,t,k)$ is trivially infeasible. Suppose otherwise that $t\in B$. Let $C$ be a component in $G-B$. By definition, every non-separating $s$-$t$ path $P$ of length at most $k$ does not contain any vertex of $C$. Let $G^{\prime}$ be the graph obtained from $G$ by contracting all edges in $E(G-B)$. For each component $C$ in $G-B$, we denote by $v_{C}$ the vertex of $G^{\prime}$ corresponding to $C$ (i.e., $v_{C}$ is the vertex obtained by contracting all edges in $C$). Then, we have ${\rm diam}(G^{\prime})\leq 2k+2$ as ${\rm diam}(G[B])\leq k$ and every vertex in $V(G^{\prime})\setminus B$ is adjacent to a vertex in $B$. By Lemma 3.7, $G$ has a non-separating $s$-$t$ path of length at most $k$ if and only if so does $G^{\prime}$. Since $\mathcal{C}$ is minor-closed, we have $G^{\prime}\in\mathcal{C}$ and hence the treewidth of $G^{\prime}$ is upper bounded by $f(2k+2)$ for some function $f$. By Theorem 3.5, we can check whether $G^{\prime}$ has a non-separating $s$-$t$ path of length at most $k$ in $O(g(k)|V(G^{\prime})|)$ time for some function $g$.

Suppose to the contrary that an induced $u$-$v$ path $P$ contains a vertex $x\notin N[S]$. Since $P$ starts and ends in $S$, it contains a subpath $Q={\langle a,\dots,x,\dots,b\rangle}$ such that $a,b\in N(S)$ and all other vertices in $Q$ belong to $V-N[S]$. As $a,b\in N(S)$ and $G[S]$ is connected, $G$ has an induced $a$-$b$ path $R$ with all internal vertices belonging to $S$. Since the internal vertices of $Q$ have no neighbors in $S$, $Q\cup R$ induces a cycle. Both $a$-$b$ paths $Q$ and $R$ have length at least $2$ as $a$ and $b$ are not adjacent, and thus the cycle $G[Q\cup R]$ has length at least $4$. This contradicts that $G$ is chordal.

Let $d={\rm dist}(s,t)$. For $0\leq i\leq d$, let

and $V(P)\cap D_{i}=\{u_{i}\}$. Let $j$ ($0<j<d$) be the index such that $v=u_{j}$.

Suppose to the contrary that there is an induced $s$-$t$ path $Q$ such that $V(Q)\cap(N[u_{j}]\setminus\{s,t\})=\emptyset$. By Lemma 3.11, $V(Q)\subseteq N[V(P)]=\bigcup_{0\leq i\leq d}N[u_{i}]$ holds. Since $Q$ starts in $N[u_{0}]$ and ends in $N[u_{d}]$, there are indices $i$ and $k$ with $0\leq i<j<k\leq d$ such that $Q$ consecutively visits a vertex $v_{i}\in N[u_{i}]$ and then a vertex $v_{k}\in N[u_{k}]$ in this order. Since ${\rm dist}(u_{i},u_{k})=k-i\geq 2$ and $\{v_{i},v_{k}\}\in E$, at least one of $v_{i}\neq u_{i}$ and $v_{k}\neq u_{k}$ holds. By symmetry, we assume that $v_{i}\neq u_{i}$.

If $v_{k}=u_{k}$, then $v_{i}\in N(u_{i})\cap N(u_{k})$. In this case, we have $i=j-1$ and $k=j+1$ since otherwise $P$ admits a shortcut using the subpath ${\langle u_{i},v_{i},u_{k}\rangle}$. This implies that ${\rm dist}(s,v_{i})\leq{\rm dist}(s,u_{i})+1=i+1=j$ and ${\rm dist}(v_{i},t)\leq 1+{\rm dist}(v_{k},t)=1+{\rm dist}(u_{k},t)=1+(d-k)=d-j$. Since ${\rm dist}(s,v_{i})+{\rm dist}(v_{i},t)\geq d$, we have ${\rm dist}(s,v_{i})=j$ and ${\rm dist}(v_{i},t)=d-j$. This implies that $v_{i}\in D_{j}\subseteq N[u_{j}]\setminus\{s,t\}$, a contradiction

Next we consider the case $v_{k}\neq u_{k}$. Recall that we also have $v_{i}\neq u_{i}$ as an assumption. In this case, we have $k-i\leq 3$ as ${\langle u_{i},v_{i},v_{k},u_{k}\rangle}$ is not a shortcut for $P$. Assume first that $k-i=3$. By symmetry, we may assume that $i=j-1$ and $k=j+2$. Since ${\rm dist}(s,v_{i})\leq{\rm dist}(s,u_{i})+1=j$ and ${\rm dist}(v_{i},t)\leq 2+{\rm dist}(u_{k},t)\leq 2+(d-k)=d-j$, we have $v_{i}\in D_{j}\subseteq N[u_{j}]\setminus\{s,t\}$, a contradiction. Next assume that $k-i=2$. That is, $i=j-1$ and $k=i+1$. Since $v_{i},v_{k}\notin N[u_{j}]\setminus\{s,t\}$ and $P$ is shortest, the vertices $v_{i}$, $u_{i}$, $u_{j}$, $u_{k}$, $v_{k}$ are distinct and form a cycle of length $5$. Observe that $v_{i}\notin\{s,t\}$ since otherwise ${\langle v_{i}=s,v_{k},u_{k}\rangle}$ or ${\langle u_{i},v_{i}=t\rangle}$ is a shortcut. Similarly, $v_{k}\notin\{s,t\}$. Hence, $v_{i},v_{k}\notin N[u_{j}]$. Therefore, the possible chords for the cycle ${\langle v_{i},u_{i},u_{j},u_{k},v_{k}\rangle}$ are $\{u_{i},v_{k}\}$ and $\{u_{k},v_{i}\}$. In any combination of them, the graph has an induced cycle of length at least $4$.

The first case is trivial. In the following, we prove the correctness of the second case.

First we show that the condition 2a is necessary. Let $a\in D_{\ell}$ and $b\in V\setminus D$. Since $|D_{\ell}|>1$ and $|V(P)\cap D_{\ell}|=1$, there is a vertex $a^{\prime}\in D_{\ell}\setminus V(P)$, where $a^{\prime}$ may be $a$ itself. Since $V(P)\subseteq D$, it holds that $b\notin V(P)$. Hence, $a^{\prime}$ and $b$ belong to the same connected component of $G-V(P)$. Since $D_{\ell}$ is a clique, $a\in N[a^{\prime}]$. Thus, $a$ and $b$ belong to the same connected component of $G-(V(P)\setminus\{a,b\})$. Therefore, $V(P)$ does not contain any $a$-$b$ separator.

Next we show that the condition 2b is necessary. Let $a\in D_{\ell}$ and $b\in D_{r}$. As before, it suffices to show that $a$ and $b$ belong to the same connected component of $G-(V(P)\setminus\{a,b\})$. By the same reasoning in the previous case, there are vertices $a^{\prime}\in D_{\ell}\setminus V(P)$ and $b^{\prime}\in D_{r}\setminus V(P)$ and they belong to the same connected component of $G-V(P)$. Now, since $a\in N[a^{\prime}]$ and $b\in N[b^{\prime}]$, $a$ and $b$ belong to the same connected component of $G-(V(P)\setminus\{a,b\})$.

Finally we show that the conditions 2a and 2b together form a sufficient condition for $P$ to be non-separating. Assume that a shortest $s$-$t$ path $P$ satisfies the conditions 2a and 2b. Since $|D_{\ell}|>1$ and $|V(P)\cap D_{\ell}|=1$, there is a connected component $C$ of $G-V(P)$ that contains at least one vertex of $D_{\ell}$. Now the condition 2a implies that $V\setminus D\subseteq V(C)$ (recall that $V(P)\subseteq D$), and the condition 2b implies that $(D_{\ell}\cup D_{r})\setminus V(P)\subseteq V(C)$ holds. To complete the proof, it suffices to show that $D_{i}\setminus V(P)\subseteq V(C)$ for all $i$. If $i<\ell$ or $i>r$, then $D_{i}\setminus V(P)=\emptyset$. Let $v\in D_{i}\setminus V(P)$ for some $i$ with $\ell\leq i\leq r$. Observe that $v$ is an internal vertex of a shortest path from the unique vertex $u\in D_{\ell-1}$ to the unique vertex $w\in D_{r+1}$. By Lemma 3.13, $N[v]\setminus\{u,w\}$ is a $u$-$w$ separator. Since $C$ is connected and $u,w$ have neighbors in $C$, $G[V(C)\cup\{u,w\}]$ contains a $u$-$w$ path $Q$. Since $N[v]\setminus\{u,w\}$ is a $u$-$w$ separator, $Q$ contains a vertex $q$ such that

Therefore, $v$ has a neighbor (i.e., $q$) in $V(C)$, and thus $v$ itself belongs to $C$.

Since $G$ is chordal, each minimal separator of $G$ is a clique. Since $P$ is a shortest path, the size of a clique in $G[V(P)]$ is at most $2$. Therefore, every minimal separator of $G$ contained in $V(P)$ has size at most $2$. Furthermore, every size-$2$ minimal separator $\{u,v\}$ is an edge of $G$. This observation gives us the following implementation of the algorithm that clearly runs in polynomial time.

For $i\in\{1,2\}$, let $\mathcal{F}_{i}$ be the set of size-$i$ minimal $a$-$b$ separators of $G$ such that $a\in D_{\ell}$ and $b\in(V\setminus D)\cup D_{r}$. It suffices to find a shortest $s$-$t$ path $P$ such that no element of $\mathcal{F}_{1}\cup\mathcal{F}_{2}$ is a subset of $V(P)$. To forbid the elements of $\mathcal{F}_{1}$, we just remove the vertices that form the size-$1$ separators in $\mathcal{F}_{1}$. Similarly, to forbid the elements of $\mathcal{F}_{2}$, we remove the edges corresponding to the size-$2$ separators in $\mathcal{F}_{2}$. Now we find a shortest $s$-$t$ path $P$ in the resultant graph. If $P$ has length $d={\rm dist}_{G}(s,t)$, then $P$ is a non-separating shortest $s$-$t$ path in $G$. Otherwise, $G$ does not have such a path.