QClique: optimizing performance and accuracy in maximum weighted clique

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

The Maximum Weighted Clique (MWC) problem remains challenging due to its unfavourable time complexity. In this paper, we analyze the execution of exact search-based MWC algorithms and show that high-accuracy weighted cliques can be discovered in the early stages of the execution if searching the combinatorial space is performed systematically.

Based on this observation, we introduce QClique as an approximate MWC algorithm that processes the search space as long as better cliques are expected. QClique uses a tunable parameter to trade-off between accuracy vs. execution time and delivers 4.7-$82.3 time speedup in comparison to previous state-of-the-art MWC algorithms while providing 91.4% accuracy and achieves a parallel speedup of up to 56x on 128 threads.

Additionally, QClique accelerates the exact MWC computation by replacing the initial clique of the exact algorithm. For WLMC, an exact state-of-the-art MWC algorithm, this results in 3.3x on average.

Original languageEnglish
Title of host publicationEuro-Par 2024: parallel processing: 30th International European Conference on Parallel and Distributed Computing, proceedings
PublisherSpringer
Number of pages14
Publication statusAccepted - 01 Jun 2024
Event30th International European Conference on Parallel and Distributed Computing, Euro-Par 2024 - Madrid, Spain
Duration: 26 Aug 202430 Aug 2024

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference30th International European Conference on Parallel and Distributed Computing, Euro-Par 2024
Abbreviated titleEURO-PAR 2024
Country/TerritorySpain
CityMadrid
Period26/08/202430/08/2024

Cite this