The generic complexity of~the~graph~triangulation~problem

A. N. Rybalov

Prikladnaâ diskretnaâ matematika, no. 4 (2022), pp. 105-111.

Résumé

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.

Détail

Keywords: generic complexity, graph triangulation problem.

Bibliographie

[1] Garey M. and Johnson D., Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman and Company, 1979, 340 pp. | MR

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

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

[4] Blum M., “How to prove a theorem so no one else can claim it”, Proc. Intern. Congress Math. (Berkeley, CA, 1986), 1444–1451 | MR

[5] Myasnikov A. G. and Rybalov A. N., “Generic complexity of undecidable problems”, J. Symbolic Logic, 73:2 (2008), 656–673 | DOI | MR

[6] Rybalov A. N., “On the strongly generic undecidability of the Halting Problem”, Theor. Comput. Sci., 377 (2007), 268–270 | DOI | MR

[7] Rybalov A. N., “Generic complexity of Presburger arithmetic”, Theory Comput. Systems, 46:1 (2010), 2–8 | DOI | MR

[8] Rybalov A. N., “Generic complexity of the Diophantine problem”, Groups Complexity Cryptology, 5:1 (2013), 25–30 | DOI | MR

[9] Rybalov A. N., “Generic hardness of the Boolean satisfiability problem”, Groups Complexity Cryptology, 9:2 (2017), 151–154 | MR

[10] Rybalov A. N., “On generic complexity of the graph clustering problem”, Prikladnaya Diskretnaya Matematika, 2019, no. 46, 72–77 (in Russian)

[11] Rybalov A. N., “The general complexity of the problem to recognize Hamiltonian paths”, Prikladnaya Diskretnaya Matematika, 2021, no. 53, 120–126 (in Russian)

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

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