On Existence of Must-Include Paths and Cycles in Undirected Graphs

Yefim Dinitz, Solomon Eyal Shimony

Given an undirected graph $G=(V,E)$ and vertices $s,t,w_1,w_2\in V$, we study finding whether there exists a simple path $P$ from $s$ to $t$ such that $w_1,w_2\in P$. As a sub-pro…