Graph modification problems, which involve transforming graphs through vertex or edge operations, are pivotal in theoretical computer science and parameterized complexity. Given a graph \(G=(V,E)\) and an integer \(k\in \mathbb {N}\) , we study Uniform Cluster Vertex Deletion (resp. Uniform Cluster Edge Deletion), where the goal is to remove at most k vertices (resp. edges) such that the connected components of the resulting graph are equal-sized cliques. Graphs satisfying this property are referred to as uniform cluster graphs. We present a kernelization result with a vertex kernel of size \( \mathcal {O}(k^3) \) for Uniform Cluster Vertex Deletion (UCVD) and an FPT algorithm running in \( \mathcal {O}^{*}(2^{k}) \) time, improving upon the best-known results in the literature. We also provide a linear vertex kernel for Uniform Cluster Edge Deletion (UCED) of size \( 6k \) . Through this work, we resolve several open questions posed by Misra, Mittal, Saurabh & Thakkar [ISAAC 2023] regarding the parameterized complexity of these problems, thus offering a comprehensive view of the landscape surrounding uniform cluster graphs.

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

Parameterized Algorithms for Editing to Uniform Cluster Graph

  • Ajinkya Gaikwad,
  • Hitendra Kumar,
  • Soumen Maity

摘要

Graph modification problems, which involve transforming graphs through vertex or edge operations, are pivotal in theoretical computer science and parameterized complexity. Given a graph \(G=(V,E)\) and an integer \(k\in \mathbb {N}\) , we study Uniform Cluster Vertex Deletion (resp. Uniform Cluster Edge Deletion), where the goal is to remove at most k vertices (resp. edges) such that the connected components of the resulting graph are equal-sized cliques. Graphs satisfying this property are referred to as uniform cluster graphs. We present a kernelization result with a vertex kernel of size \( \mathcal {O}(k^3) \) for Uniform Cluster Vertex Deletion (UCVD) and an FPT algorithm running in \( \mathcal {O}^{*}(2^{k}) \) time, improving upon the best-known results in the literature. We also provide a linear vertex kernel for Uniform Cluster Edge Deletion (UCED) of size \( 6k \) . Through this work, we resolve several open questions posed by Misra, Mittal, Saurabh & Thakkar [ISAAC 2023] regarding the parameterized complexity of these problems, thus offering a comprehensive view of the landscape surrounding uniform cluster graphs.