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.

The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.

More in Data Structures & Algorithms

• arXiv preprint · 25 September 2026

  Optimal Prophet Inequalities for Gain from Trade

  Xujin Chen, Xiaodong Hu, Changjun Wang and 1 other
• arXiv preprint · 26 September 2026

  Efficient Support Recovery of Mixtures of Sparse Linear Classifiers with Less Measurements

  Xiaxin Li and Arya Mazumdar
• arXiv preprint · 25 September 2026

  An $n^{8/5+o(1)}$-Time $Ω(λ^3)$-Approximation for Longest Common Subsequence

  Zhao Song
• arXiv preprint · 26 September 2026

  Tree Search With Distributional Predictions

  Michael Dinitz and Bob Dong
• arXiv preprint · 25 September 2026

  Fast factorization in diagram monoids

  Matthias Fresacher, Willow Stewart and Daniel Tubbenhauer

All new papers in Data Structures & Algorithms