Pathwidth-One Vertex Explosion and Co-Path Problems

Dekel Tsur

In the Bipartite One-sided Vertex Explosion problem (BOVE), the input is a bipartite graph $G=(T,B,E)$ and a nonnegative integer $k$. The goal is to decide whether there is a s…