On 2-clubs in graph-based data clustering: theory and algorithm engineering
From MaRDI portal
Publication:5084692
DOI10.7155/JGAA.00570zbMATH Open1489.05145arXiv2006.14972OpenAlexW3205863632MaRDI QIDQ5084692FDOQ5084692
Authors: Aleksander Figiel, Anne-Sophie Himmel, André Nichterlein, Rolf Niedermeier 
Publication date: 28 June 2022
Published in: Journal of Graph Algorithms and Applications (Search for Journal in Brave)
Abstract: Editing a graph into a disjoint union of clusters is a standard optimization task in graph-based data clustering. Here, complementing classic work where the clusters shall be cliques, we focus on clusters that shall be 2-clubs, that is, subgraphs of diameter two. This naturally leads to the two NP-hard problems 2-Club Cluster Editing (the allowed editing operations are edge insertion and edge deletion) and 2-Club Cluster Vertex Deletion (the allowed editing operations are vertex deletions). Answering an open question from the literature, we show that 2-Club Cluster Editing is W[2]-hard with respect to the number of edge modifications, thus contrasting the fixed-parameter tractability result for the classic Cluster Editing problem (considering cliques instead of 2-clubs). Then focusing on 2-Club Cluster Vertex Deletion, which is easily seen to be fixed-parameter tractable, we show that under standard complexity-theoretic assumptions it does not have a polynomial-size problem kernel when parameterized by the number of vertex deletions. Nevertheless, we develop several effective data reduction and pruning rules, resulting in a competitive solver, clearly outperforming a standard CPLEX solver in most instances of an established biological test data set.
Full work available at URL: https://arxiv.org/abs/2006.14972
Recommendations
Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Fundamentals of parameterized complexity
- A fast branching algorithm for cluster vertex deletion
- Cluster editing
- Correlation clustering
- Cluster editing with locally bounded modifications
- Fixed-parameter algorithms for cluster vertex deletion
- Graph-based data clustering with overlaps
- Kernelization Lower Bounds by Cross-Composition
- The complexity of finding maximum disjoint paths with length constraints
- Cluster vertex deletion: a parameterization between vertex cover and clique-width
- Cluster graph modification problems
- Parameterized computational complexity of finding small-diameter subgraphs
- Going weighted: parameterized algorithms for cluster editing
- Exact algorithms for cluster editing: Evaluation and experiments
- Graph-modeled data clustering: Exact algorithms for clique generation
- Approximation and tidying -- a problem kernel for \(s\)-plex cluster vertex deletion
- The parametric complexity of graph diameter augmentation
- A more relaxed model for graph-based data clustering: \(s\)-plex cluster editing
- On biconnected and fragile subgraphs of low diameter
- Combining clickstream analyses and graph-modeled data clustering for identifying common response processes
- Parameterized algorithmics and computational experiments for finding 2-clubs
- Hardness of \(r\)-dominating set on graphs of diameter \((r + 1)\)
- Exact algorithms for finding well-connected 2-clubs in sparse real-world graphs: theory and experiments
- On the tractability of finding disjoint clubs in a network
- On 2-clubs in graph-based data clustering: theory and algorithm engineering
- On Editing Graphs into 2-Club Clusters
- On the tractability of covering a graph with 2-clubs
- Covering a graph with clubs
- Faster parameterized algorithm for cluster vertex deletion
- Parameterized Algorithmics for Graph Modification Problems: On Interactions with Heuristics
- Subexponential algorithm for \(d\)-cluster edge deletion: exception or rule?
Cited In (7)
- \(s\)-club cluster vertex deletion on interval and well-partitioned chordal graphs
- An improved fixed-parameter algorithm for 2-Club Cluster Edge Deletion
- \(s\)-club cluster vertex deletion on interval and well-partitioned chordal graphs
- Parameterized algorithmics and computational experiments for finding 2-clubs
- On Editing Graphs into 2-Club Clusters
- A 2-approximation algorithm for the graph 2-clustering problem
- Exact algorithms for finding well-connected 2-clubs in sparse real-world graphs: theory and experiments
Uses Software
This page was built for publication: On 2-clubs in graph-based data clustering: theory and algorithm engineering
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5084692)
