2020/08/21 by Akash Kumar, Kumar, Akash, Mithilesh Kumar +1
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2008.09660
openalex publication_date 2020/08/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In the DELETION TO INDUCED MATCHING problem, we are given a graph G on n vertices, m edges and a non-negative integer k and asks whether there exists a set of vertices S ⊆ V(G) such that |S|≤ k and the size of any connected component in G-S is exactly 2. In this paper, we provide a fixed-parameter tractable (FPT) algorithm of running time O^*(1.748k) for the DELETION TO INDUCED MATCHING problem using branch-and-reduce strategy and path decomposition. We also extend our work to the exact-exponential version of the problem.