Dekel Tsur

In this paper we consider two vertex deletion problems. In the BLOCK VERTEX DELETION problem, the input is a graph G and an integer k, and the goal is to decide whether there is a set of at most k vertices whose removal from G result in a block graph (a graph in which every biconnected component is a clique). In the PATHWIDTH ONE VERTEX DELETION problem, the input is a graph G and an integer k, and the goal is to decide whether there is a set of at most k vertices whose removal from G result in a graph with pathwidth at most one. We give a kernel for BLOCK VERTEX DELETION with O(k³) vertices and a kernel for PATHWIDTH ONE VERTEX DELETION with O(k²) vertices. Our results improve the previous O(k⁴)-vertex kernel for BLOCK VERTEX DELETION (Agrawal et al., 2016 [1]) and the O(k³)-vertex kernel for PATHWIDTH ONE VERTEX DELETION (Cygan et al., 2012 [3]).