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, 2022, Number 58, Pages 105–111
DOI: https://doi.org/10.17223/20710410/58/10
(Mi pdm789)
 

Mathematical Backgrounds of Informatics and Programming

The generic complexity of the graph triangulation problem

A. N. Rybalov

Sobolev Institute of Mathematics, Omsk, Russia
References:
Abstract: Generic-case approach to algorithmic problems was suggested by A. Miasnikov, V. Kapovich, P. Schupp, and V. Shpilrain in 2003. This approach studies behavior of an algorithm on typical (almost all) inputs and ignores the rest of inputs. In this paper, we study the generic complexity of the graph triangulation problem. This problem is as follows. Given a finite simple graph with $3n$ vertices, determine whether the vertices of the graph can be divided into $n$ three-element sets, each of which contains vertices connected by edges of the original graph (that is, they are triangles). NP-completeness of this problem was proved by Shaffer in 1974 and is mentioned in the classic monograph by M. Garey and D. Johnson. We prove that under the conditions $\text {P} \neq \text{NP}$ and $\text{P} = \text{BPP}$ there is no polynomial strongly generic algorithm for this problem. A strongly generic algorithm solves a problem not on the whole set of inputs, but on a subset whose frequency sequence converges exponentially to $1$ with increasing size. To prove the theorem, we use the method of generic amplification, which allows one to construct generically hard problems from the problems that are 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 for them is solved in a similar way.
Keywords: generic complexity, graph triangulation problem.
Funding agency Grant number
Russian Science Foundation 22-11-20019
Document Type: Article
UDC: 510.52
Language: Russian
Citation: A. N. Rybalov, “The generic complexity of the graph triangulation problem”, Prikl. Diskr. Mat., 2022, no. 58, 105–111
Citation in format AMSBIB
\Bibitem{Ryb22}
\by A.~N.~Rybalov
\paper The generic complexity of~the~graph~triangulation~problem
\jour Prikl. Diskr. Mat.
\yr 2022
\issue 58
\pages 105--111
\mathnet{http://mi.mathnet.ru/pdm789}
\crossref{https://doi.org/10.17223/20710410/58/10}
Linking options:
  • https://www.mathnet.ru/eng/pdm789
  • https://www.mathnet.ru/eng/pdm/y2022/i4/p105
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Прикладная дискретная математика
    Statistics & downloads:
    Abstract page:68
    Full-text PDF :29
    References:17
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024