Pathwidth-One Vertex Explosion and Co-Path Problems

Abstract

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 set $S\subseteq B$ of size at most $k$ such that exploding every vertex in $S$ results in a graph with pathwidth at most one. The restricted Pathwidth One Vertex Explosion problem (restricted POVE) is a generalization of BOVE. The input to this problem is a graph $G$, a nonnegative integer $k$, and a set of vertices $X\subseteq V($ The goal is to decide whether there is a set $S\subseteq X$ of size at most $k$ such that exploding every vertex in $S$ results in a graph with pathwidth at most one. In this paper, we show parameter-preserving reductions in both directions between BOVE and Co-Path Set, and between restricted POVE and restricted Co-Path Packing. These reductions yield improved parameterized algorithms for BOVE and restricted POVE and an improved kernel for BOVE.