.png){kind=icon}
.png){kind=icon}
Return
Improved Parameterized Algorithms for Cluster Vertex Deletion
.png){kind=icon}
PRE
AI
DOI：10.1007/s00224-025-10247-6.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
In the Cluster Vertex Deletion problem, we are given a graph G and an integer k, and the goal is to determine whether we can delete at most k vertices from G to make the remaining graph a cluster graph, i.e., a graph in which every connected component is a complete graph. In this paper, we show that Cluster Vertex Deletion can be solved in \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O<^>*(1.7549<^>k)$$\end{document} time, improving the previous result of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O<^>*(1.811<^>k)$$\end{document}. To obtain this result, one crucial step is to show that Cluster Vertex Deletion on graphs of maximum degree at most 4 can be solved in \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} time. For a general graph, after a series of reductions, if the maximum degree of the reduced graph is at most 4, we introduce a new technique, called core branching processing, to solve the problem; if the reduced graph has a vertex of degree at least 5, we adopt the previous method of automated generation of search trees to obtain the improved running time.
Keywords:
Cluster Vertex Deletion
parameterized algorithms
graph theory
branching
kernelization