On generic complexity of~the~graph clustering problem with bounded clusters

A. N. Rybalov

Prikladnaâ diskretnaâ matematika, no. 2 (2023), pp. 114-119.

Résumé

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.

Détail

Keywords: generic complexity, graph clustering.

Bibliographie

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

[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

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

[8] Il'ev V. P. and Navrotskaya A. A., “Computational complexity of the problem of approximation by graphs with connected components of bounded size”, Prikladnaya Diskretnaya Matematika, 2011, no. 3(13), 80–84 (in Russian) | Zbl

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

[10] Rybalov A. N., “The generic complexity of the bounded problem of graphs clustering”, Prikladnaya Diskretnaya Matematika, 2022, no. 57, 91–97 (in Russian)

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

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

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

[14] Vyalyy M., Kitaev A., and Shen' A., Klassicheskie i kvantovye vychisleniya, MCCME CheRo Publ., M., 1999, 192 pp. (in Russian)