Scholarlink

<p>In the <span>Cluster Vertex Deletion</span> problem, we are given a graph <i>G</i> and an integer <i>k</i>, and the goal is to determine whether we can delete at most <i>k</i> vertices from <i>G</i> 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 <span>Cluster Vertex Deletion</span> can be solved in <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(O^*(1.7549^k)\)</EquationSource> </InlineEquation> time, improving the previous result of <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(O^*(1.811^k)\)</EquationSource> </InlineEquation>. To obtain this result, one crucial step is to show that <span>Cluster Vertex Deletion</span> on graphs of maximum degree at most 4 can be solved in <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(O^*(1.7485^k)\)</EquationSource> </InlineEquation> 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.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Improved Parameterized Algorithms for Cluster Vertex Deletion

  • 期刊论文

  • 发表日期：

    2025年11月11日

查看全文
  • Kangyi Tian,
  • Mingyu Xiao,
  • Boting Yang

摘要

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 \(O^*(1.7549^k)\) time, improving the previous result of \(O^*(1.811^k)\) . 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 \(O^*(1.7485^k)\) 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.