RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Archive Impact factor Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Prikl. Diskr. Mat.: Year: Volume: Issue: Page: Find

 Prikl. Diskr. Mat., 2019, Number 46, Pages 72–77 (Mi pdm685)

Mathematical Backgrounds of Informatics and Programming

On generic complexity of the graph clustering problem

A. N. Rybalov

Sobolev Institute of Mathematics, Omsk, Russia

Abstract: 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 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.

Keywords: generic complexity, graph clustering.

 Funding Agency Grant Number Russian Science Foundation 18-71-10028

DOI: https://doi.org/10.17223/20710410/46/6

Full text: PDF file (594 kB)
References: PDF file   HTML file

Bibliographic databases:

UDC: 510.52

Citation: A. N. Rybalov, “On generic complexity of the graph clustering problem”, Prikl. Diskr. Mat., 2019, no. 46, 72–77

Citation in format AMSBIB
\Bibitem{Ryb19} \by A.~N.~Rybalov \paper On generic complexity of~the~graph clustering problem \jour Prikl. Diskr. Mat. \yr 2019 \issue 46 \pages 72--77 \mathnet{http://mi.mathnet.ru/pdm685} \crossref{https://doi.org/10.17223/20710410/46/6}