2023/08/27 by Liu, Yuxi, Xiao, Mingyu
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2308.14116
An induced subgraph is called an induced matching if each vertex is a degree-1 vertex in the subgraph. The Almost Induced Matching problem asks whether we can delete at most k vertices from the input graph such that the remaining graph is an induced matching. This paper studies parameterized algorithms for this problem by taking the size k of the deletion set as the parameter. First, we prove a 6k-vertex kernel for this problem, improving the previous result of 7k. Second, we give an O^*(1.6765k)-time and polynomial-space algorithm, improving the previous running-time bound of O^*(1.7485k).