Prikladnaya Diskretnaya Matematika
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






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Prikladnaya Diskretnaya Matematika, 2023, Number 60, Pages 114–119
DOI: https://doi.org/10.17223/20710410/60/10
(Mi pdm807)
 

Mathematical Backgrounds of Informatics and Programming

On generic complexity of the graph clustering problem with bounded clusters

A. N. Rybalov

Sobolev Institute of Mathematics, Omsk, Russia
References:
Abstract: In this paper, we study the generic complexity of the graph clustering problem with bounded sizes of clusters. In this problem, the structure of object relations 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) of bounded sizes 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 this problem there is no polynomial strongly generic algorithm. A strongly generic algorithm solves a problem not on the entire set of inputs, but on a subset whose frequency sequence converges exponentially to 1 as the size increases. To prove this result, we use the method of generic amplification, which allows to construct generically hard problems from the problems hard in the classical sense. The main component of this method is the cloning technique, which combines the inputs of a problem together into sufficiently large sets of equivalent inputs. Equivalence is understood in the sense that the problem is solved similarly for them.
Keywords: generic complexity, graph clustering.
Funding agency Grant number
Russian Science Foundation 22-11-20019
Document Type: Article
UDC: 510.52
Language: Russian
Citation: A. N. Rybalov, “On generic complexity of the graph clustering problem with bounded clusters”, Prikl. Diskr. Mat., 2023, no. 60, 114–119
Citation in format AMSBIB
\Bibitem{Ryb23}
\by A.~N.~Rybalov
\paper On generic complexity of~the~graph clustering problem with bounded clusters
\jour Prikl. Diskr. Mat.
\yr 2023
\issue 60
\pages 114--119
\mathnet{http://mi.mathnet.ru/pdm807}
\crossref{https://doi.org/10.17223/20710410/60/10}
Linking options:
  • https://www.mathnet.ru/eng/pdm807
  • https://www.mathnet.ru/eng/pdm/y2023/i2/p114
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Прикладная дискретная математика
    Statistics & downloads:
    Abstract page:69
    Full-text PDF :21
    References:19
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024