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/}
}
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/