Abstract: In clustering problems, one has to partition a given set of objects into pairwise disjoint subsets (clusters) taking into account only similarity of objects. In the graph cluster editing problem similarity relation on the set of objects is given by an undirected graph whose vertices are in one-to-one correspondence with objects and edges correspond to pairs of similar objects. The goal is to find a nearest to a given graph G=(V,E)cluster graph, i.e., a graph on the vertex set V each connected component of which is a complete graph. The distance between graphs is understood as the Hamming distance between their incidence vectors. We consider a variant of the cluster editing problem in which the size of each cluster is bounded from above by a positive integer s. In 2011, Il’ev and Navrotskaya proved that this problem is NP-hard for any fixed s ⩾3. In 2015, Puleo and Milenkovic proposed a 6-approximation algorithm for this problem. In 2016, Il’ev, Il’eva and Navrotskaya presented an approximation algorithm that is 3-approximation in case of s =3 and 5-approximation in case of s =4. Now we propose simple greedy-type 2-approximation algorithms for these cases with tight performance guarantees.

Cite: Il’ev V.P. , Il’eva S.
Approximation Algorithms for Graph Cluster Editing Problems with Cluster Size at Most 3 and 4
In compilation Mathematical Optimization Theory and Operations Research: Recent Trends. – Springer., 2023. – Т.1881. – C.134-145. DOI: 10.1007/978-3-031-43257-6_11 Scopus OpenAlex

Dates:

Published print:	Sep 21, 2023
Published online:	Sep 21, 2023

Identifiers:

Scopus:	2-s2.0-85174564829
OpenAlex:	W4386891736

Citing:

DB	Citing
OpenAlex	1
Scopus	1

Altmetrics: