EUVIMEDEUVIMED entdecken
Crossref

On the parameterized complexity of s-club cluster edge deletion

Ajinkya Gaikwad

Journal of Computer and System Sciences · 2026-11 · 161 · 103820

DOI: 10.1016/j.jcss.2026.103820 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Journal of Computer and System Sciences, 2026-11. Verfasst von Ajinkya Gaikwad. Die Arbeit nennt 20 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We study the parameterized and kernelization complexity of the \emph{\textsc{$s$-Club Cluster Edge Deletion}} problem, a distance-bounded generalization of \emph{\textsc{Cluster Edge Deletion}}. Given a graph $G=(V,E)$ and integers $k,s$, the goal is to delete at most $k$ edges so that every resulting connected component has diameter at most $s$. On the structural side, we settle an open question of Montecchiani, Ortali, Piselli, and Tappini (\emph{Theoretical Computer Science}, 2023) by proving W[1]-hardness parameterized by pathwidth plus the maximum number of allowed $s$-clubs, and consequently by treewidth plus this parameter. Thus, the diameter bound $s$ is inecessary for tractability under these parameters. In contrast, we show that dependence on \(s\) is unnecessary for several structural parameters: the problem is fixed-parameter tractable when parameterized by treedepth, neighborhood diversity, or cluster vertex deletion number, generalizing known results for $s=1.$ We further prove that no polynomial kernel exists when parameterized by vertex cover, even for $s=2$. On the positive side, we present an FPT bicriteria approximation scheme for graphs excluding long induced cycles, running in time $f(k,1/\epsilon)\cdot n^{\mathcal{O}(1)}$ and producing a solution of size at most $k$ whose components have diameter at most $(1+\epsilon)s$. Finally, we initiate the study of the directed variant, \textsc{$s$-Club Cluster Arc Deletion}, and prove that it is W[1]-hard parameterized by $k$, even on directed acyclic graphs.

Zitieren

APA

Gaikwad, A. (2026). On the parameterized complexity of s-club cluster edge deletion. Journal of Computer and System Sciences, 161, 103820. https://doi.org/10.1016/j.jcss.2026.103820

Vancouver

Gaikwad A. On the parameterized complexity of s-club cluster edge deletion. Journal of Computer and System Sciences. 2026;161:103820. doi:10.1016/j.jcss.2026.103820

BibTeX
@article{Gaikwad2026,
  author = {Gaikwad, Ajinkya},
  title = {On the parameterized complexity of s-club cluster edge deletion},
  journal = {Journal of Computer and System Sciences},
  year = {2026},
  volume = {161},
  pages = {103820},
  doi = {10.1016/j.jcss.2026.103820}
}
Kostenlos starten →