Geodesic
On generic complexity of~the~graph clustering problem
Prikladnaâ diskretnaâ matematika, no. 4 (2019), pp. 72-77

Voir la notice de l'article provenant de la source Math-Net.Ru

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 objects 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) to minimize the number of connections between clusters and the number of missing links within clusters. It is proved that under the condition $\text {P} \neq \text{NP}$ and $\text{P} = \text{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.
Keywords: generic complexity, graph clustering. 
@article{PDM_2019_4_a5,
     author = {A. N. Rybalov},
     title = {On generic complexity of~the~graph clustering problem},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {72--77},
     publisher = {mathdoc},
     number = {4},
     year = {2019},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2019_4_a5/}
}
TY  - JOUR
AU  - A. N. Rybalov
TI  - On generic complexity of~the~graph clustering problem
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2019
SP  - 72
EP  - 77
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2019_4_a5/
LA  - ru
ID  - PDM_2019_4_a5
ER  - 
%0 Journal Article
%A A. N. Rybalov
%T On generic complexity of~the~graph clustering problem
%J Prikladnaâ diskretnaâ matematika
%D 2019
%P 72-77
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2019_4_a5/
%G ru
%F PDM_2019_4_a5
A. N. Rybalov. On generic complexity of~the~graph clustering problem. Prikladnaâ diskretnaâ matematika, no. 4 (2019), pp. 72-77. http://geodesic.mathdoc.fr/item/PDM_2019_4_a5/