Vertex removal improves graph pathwidth calculations for bipartite graphs
Pathwidth-One Vertex Explosion and Co-Path Problems
Data Structures and Algorithms
Summary
This paper looks at a problem where you have a special kind of graph made of two types of nodes, and you want to remove a few specific nodes to make the graph simpler in a particular way. The authors study how removing these nodes affects a measure called pathwidth, which relates to how complicated a graph's connections are. They show that two related problems can be transformed into each other in a way that keeps the key parameter the same. Using these transformations, they improve known algorithms and methods for solving these problems more efficiently.
What this means in practice
- •For graph algorithm engineers: Improve tools that simplify graph structures by efficiently reducing pathwidth through targeted node removals.
- •For network topology planners: Design networks with manageable complexity by applying vertex removal strategies to control network pathwidth.
A theory result. No direct application yet.
Authors
Dekel Tsur
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.