On generic complexity of the graph clustering problem with bounded clusters | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2023. № 60. DOI: 10.17223/20710410/60/10

In this paper, we study the generic complexity of the graph clustering problem with bounded sizes of clusters. In this problem, the structure of object relations is presented as a graph: vertices correspond to objects, and edges connect similar objects. It is required to divide a set of objects into disjoint groups (clusters) of bounded sizes to minimize the number of connections between clusters and the number of missing links within clusters. It is proved that, under the condition P ≠ NP and P = BPP, for this problem there is no polynomial strongly generic algorithm. A strongly generic algorithm solves a problem not on the entire set of inputs, but on a subset whose frequency sequence converges exponentially to 1 as the size increases. To prove this result, we use the method of generic amplification, which allows to construct generically hard problems from the problems hard in the classical sense. The main component of this method is the cloning technique, which combines the inputs of a problem together into sufficiently large sets of equivalent inputs. Equivalence is understood in the sense that the problem is solved similarly for them.