Geodesic
On 2-Clubs in Graph-Based Data Clustering: Theory and Algorithm Engineering
Journal of Graph Algorithms and Applications, Tome 25 (2021) no. 1, pp. 521-547.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

Editing a graph into a disjoint union of clusters is a standard optimization task in graph-based data clustering. Here, complementing classical work where the clusters shall be cliques, we focus on clusters that shall be 2-clubs, that is, subgraphs of diameter at most two. This naturally leads to the two NP-hard problems $\rm{2-C \small{LUB}}$ $\rm{C{\small LUSTER}}$ $\rm{E{\small DITING}}$ (the editing operations are edge insertions and edge deletions) and $\rm{2-C \small{LUB}}$ $\rm{C{\small LUSTER}}$ $\rm{V{\small ERTEX}}$ $\rm{D{\small ELETION}}$ (the editing operations are vertex deletions). Answering an open question from the literature, we show that $\rm{2-C \small{LUB}}$ $\rm{C{\small LUSTER}}$ $\rm{E{\small DITING}}$ is W[2]-hard with respect to the number of edge modifications, thus contrasting the fixed-parameter tractability result for the classical $\rm{C{\small LUSTER}}$ $\rm{E{\small DITING}}$ problem (considering cliques instead of 2-clubs). Then, focusing on $\rm{2-C \small{LUB}}$ $\rm{C{\small LUSTER}}$ $\rm{V{\small ERTEX}}$ $\rm{D{\small ELETION}}$, 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, outperforming a standard ILP formulation in most instances of an established biological test data set.
DOI : 10.7155/jgaa.00570
Keywords: graph modification problems, parameterized complexity, fixed-parameter tractability, problem kernel, data reduction, branch and bound, algorithm engineering 
@article{JGAA_2021_25_1_a23,
     author = {Aleksander Figiel and Anne-Sophie Himmel and Andr\'e Nichterlein and Rolf Niedermeier},
     title = {On {2-Clubs} in {Graph-Based} {Data} {Clustering:} {Theory} and {Algorithm} {Engineering}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {521--547},
     publisher = {mathdoc},
     volume = {25},
     number = {1},
     year = {2021},
     doi = {10.7155/jgaa.00570},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00570/}
}
TY  - JOUR
AU  - Aleksander Figiel
AU  - Anne-Sophie Himmel
AU  - André Nichterlein
AU  - Rolf Niedermeier
TI  - On 2-Clubs in Graph-Based Data Clustering: Theory and Algorithm Engineering
JO  - Journal of Graph Algorithms and Applications
PY  - 2021
SP  - 521
EP  - 547
VL  - 25
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00570/
DO  - 10.7155/jgaa.00570
LA  - en
ID  - JGAA_2021_25_1_a23
ER  - 
%0 Journal Article
%A Aleksander Figiel
%A Anne-Sophie Himmel
%A André Nichterlein
%A Rolf Niedermeier
%T On 2-Clubs in Graph-Based Data Clustering: Theory and Algorithm Engineering
%J Journal of Graph Algorithms and Applications
%D 2021
%P 521-547
%V 25
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00570/
%R 10.7155/jgaa.00570
%G en
%F JGAA_2021_25_1_a23
Aleksander Figiel; Anne-Sophie Himmel; André Nichterlein; Rolf Niedermeier. On 2-Clubs in Graph-Based Data Clustering: Theory and Algorithm Engineering. Journal of Graph Algorithms and Applications, Tome 25 (2021) no. 1, pp. 521-547. doi : 10.7155/jgaa.00570. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00570/

Cité par Sources :