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/

[1] Kapovich I., Miasnikov A., Schupp P., Shpilrain V., “Generic-case complexity, decision problems in group theory and random walks”, J. Algebra, 264:2 (2003), 665–694 | DOI | MR | Zbl

[2] Gimadi E.H., Glebov N.I., Perepelitsa V.A., “Algorithms with bounds for problems of discrete optimization”, Problemy Kibernetiki, 31 (1975), 35–42 (in Russian)

[3] Kr̀ivanek M., Morávek J., “NP-hard problems in hierarchical-tree clustering”, Acta Informatica, 23 (1986), 311–323 | DOI | MR | Zbl

[4] Bansal N., Blum A., Chawla S., “Correlation clustering”, Machine Learning, 56 (2004), 89–113 | DOI | MR | Zbl

[5] Shamir R., Sharan R., Tsur D., “Cluster graph modification problems”, Discrete Appl. Math., 144:1–2 (2004), 173–182 | DOI | MR | Zbl

[6] Ageev A. A., Il'ev V. P., Kononov A. V., Talevnin A. S., “Computational complexity of the graph approximation problem”, J. Appl. Ind. Math., 1:1 (2007), 1–8 | DOI | MR | MR

[7] Il'ev V. P., Il'eva S. D., “On problems of graph clustering”, Vestnik Omskogo Universiteta, 2016, no. 2, 16–18 (in Russian)

[8] Il'ev A. V., Il'ev V. P., “On a problem of graph clustering with partial learning”, Prikladnaya Diskretnaya Matematika, 2018, no. 42, 66–75 (in Russian) | MR

[9] Talevnin A. S., “On the complexity of the graph approximation problem”, Vestnik Omskogo Universiteta, 2004, no. 4, 22–24 (in Russian)

[10] Impagliazzo R., Wigderson A., “P $=$ BPP unless E has subexponential circuits: Derandomizing the XOR Lemma”, Proc. 29th STOC, ACM, El Paso, 1997, 220–229 | MR

[11] Rybalov A. N., “On generic complexity of the validity problem for Boolean formulas”, Prikladnaya Diskretnaya Matematika, 2016, no. 2(32), 119–126 (in Russian)