On generic complexity of the graph clustering problem | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2019. № 46. DOI: 10.17223/20710410/46/6

Generic-case approach to algorithmic problems was suggested by Miasnikov, Kapovich, Schupp and Shpilrain in 2003. This approach studies behavior of algorithms on typical (almost all) inputs and ignores the rest of inputs. In this paper, we study the generic complexity of the problem of clustering graphs. In this problem the structure of relations of ob jects is presented as a graph: vertices correspond to ob jects, and edges connect similar ob jects. It is required to divide a set of ob jects into disjoint groups (clusters) 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 the graph clustering problem there is no polynomial strongly generic algorithm. A strongly generic algorithm solves a problem not on the whole set of inputs, but on its subset, in which the sequence of frequencies of inputs converges exponentially fast to 1 with increasing its size.