Solving Cluster Editing Using MaxSAT-based Techniques

Bachelor thesis (2021)

Authors

I.C.W.M. Marijnissen Electrical Engineering, Mathematics and Computer Science

Contributors

E. Demirović Algorithmics - EEMCS (supervisor 1)
J.A. Pouwelse Data-Intensive Systems - EEMCS (supervisor 2)
Faculty
Electrical Engineering, Mathematics and Computer Science
Copyright: © 2021 Imko Marijnissen
Cluster Editing Maximum Satisfiability Reduction
More Info
expand_more

Published Date

01-07-2021

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Faculty

Electrical Engineering, Mathematics and Computer Science

Abstract

Clustering is a well-studied problem and several algorithms have been developed to find these clusterings under certain constraints. This work will show the applicability of propositional logic (MaxSAT) based approaches to a specific version of correlation clustering called cluster editing. This is the problem of finding the minimum number of edits to turn a given graph into a disjoint union of cliques. This work proposes a combination of modelling, preprocessing and solving techniques to solve the cluster editing problem via propositional logic. This approach's performance is experimentally evaluated and compared to another search algorithm based on merging vertices and adding/deleting edges. The results show that for certain instances propositional logic based approaches have a satisfactory performance while for other instances the theoretical approach provides a more guided search of the solution space.