Details

Autor(en) / Beteiligte

• Chen, Xujin
• Li, Bo

Titel

An Improved Kernel and Parameterized Algorithm for Almost Induced Matching

Ist Teil von

• Theory and Applications of Models of Computation, 2024, Vol.14637, p.86-98

Ort / Verlag

Singapore: Springer Singapore Pte. Limited

Erscheinungsjahr

2024

Link zum Volltext

Quelle

Alma/SFX Local Collection

Beschreibungen/Notizen

• 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)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O^*(1.6765^k)$$\end{document}-time and polynomial-space algorithm, improving the previous running-time bound of O∗(1.7485k)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O^*(1.7485^k)$$\end{document}.