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

Abstract

Given an undirected graph $G=(V,E)$ and vertices $s,t,w_1,w_2\in V$, we study the following path existence problem (PEP): does there exist a simple path from $s$ to $t$ containing $w_1$ and $w_2$, and the closely related cycle existence problem (CEP) of a simple cycle containing three given graph elements (vertices or edges).
We reduce the PEP to the CEP, and the general graph case of the CEP to that of a triconnected graph. We show that two simple necessary conditions for the existence of a cycle containing three given edges in a triconnected graph are sufficient.