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

Yefim Dinitz; Solomon Eyal Shimony

paper

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

arXiv:2302.09614

Abstract

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-problem, we study the question: given an undirected graph and three of its edges, does there exist a simple cycle containing all those edges? We provide necessary and sufficient conditions for the existence of such paths and cycles, and develop efficient algorithms to solve this and related problems.