On the parameterized complexity of s-club cluster deletion problems

DOI10.1007/978-3-031-23101-8_11MaRDI QIDQ6169520zbMATH OpenOpenAlexFDO

Authors Fabrizio Montecchiani, Giacomo Ortali, Tommaso Piselli, Alessandra Tappini

Publication date 14 August 2023

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2205.10834

Mathematics Subject Classification ID

Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10)

Abstract: We study the parameterized complexity of the $s$-Club Cluster Edge Deletion problem: Given a graph $G$ and two integers $sge2$ and $kge1$, is it possible to remove at most $k$ edges from $G$ such that each connected component of the resulting graph has diameter at most $s$? This problem is known to be NP-hard already when $s=2$. We prove that it admits a fixed-parameter tractable algorithm when parameterized by $s$ and the treewidth of the input graph.

Recommendations

• On Editing Graphs into 2-Club Clusters
• Subexponential algorithm for d-cluster edge deletion: exception or rule?
• An improved fixed-parameter algorithm for 2-Club Cluster Edge Deletion
• The parameterized complexity of \(s\)-club with triangle and seed constraints

Cites work

• A 2k kernel for the cluster editing problem
• A golden ratio parameterized algorithm for cluster editing
• A graph‐theoretic definition of a sociometric clique†
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Algorithms and complexity of \(s\)-club cluster vertex deletion
• An improved fixed-parameter algorithm for 2-Club Cluster Edge Deletion
• Cluster editing with locally bounded modifications
• Cluster graph modification problems
• Correlation clustering
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• Graph clustering
• Graph minors. II. Algorithmic aspects of tree-width
• Multivariate algorithmics for finding cohesive subnetworks
• Novel approaches for analyzing biological networks
• On Editing Graphs into 2-Club Clusters
• On the parameterized complexity of s-club cluster deletion problems
• On the tractability of covering a graph with 2-clubs
• Subexponential algorithm for d-cluster edge deletion: exception or rule?
• Tight bounds for parameterized complexity of cluster editing with a small number of clusters
• Treewidth. Computations and approximations

Cited in

(6)

• An improved fixed-parameter algorithm for 2-Club Cluster Edge Deletion
• The parameterized complexity of \(s\)-club with triangle and seed constraints
• On the Parameterized Complexity of Clique Elimination Distance
• \(s\)-club cluster vertex deletion on interval and well-partitioned chordal graphs
• On the parameterized complexity of s-club cluster deletion problems
• On the parameterized complexity of non-hereditary relaxations of clique

This page was built for publication: On the parameterized complexity of \(s\)-club cluster deletion problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6169520)