The generic complexity of~the~bounded problem of graphs clustering

A. N. Rybalov

Prikladnaâ diskretnaâ matematika, no. 3 (2022), pp. 91-97.

Résumé

Generic-case approach to algorithmic problems 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 bounded problem of graphs clustering. In this problem the structure of objects relations is presented as a graph: vertices correspond to objects, and edges connect similar objects. It is required to divide the set of objects into bounded disjoint groups (clusters) to minimize the number of connections between clusters and the number of missing links within clusters. We have constructed a subproblem of this problem, for which there is no polynomial generic algorithm provided $\text {P} \neq \text{NP}$ and $\text{P} = \text{BPP}$. To prove the theorem, 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 merges 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 clustering.

Bibliographie

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

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

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

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

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

[6] Il'ev A. V. and Il'ev V. P., “On a semi-superwized graph clustering problem”, Prikladnaya Diskretnaya Matematika, 2018, no. 42, 66–75 (in Russian) | MR | Zbl

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

[8] 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

[9] 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 | Zbl

[10] 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)

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

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

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

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

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

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

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