The generic complexity of the bounded problem of graphs clustering. (Russian. English summary) Zbl 07643910
Summary: 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.
References:
| [1] | Kr̀ivanek M. and Morávek J., “NP-hard problems in hierarchical-tree clustering”, Acta Informatica, 23 (1986), 311-323 · Zbl 0644.68055 · doi:10.1007/BF00289116 |
| [2] | Bansal N., Blum A., and Chawla S., “Correlation clustering”, Machine Learning, 56 (2004), 89-113 · Zbl 1089.68085 · doi:10.1023/B:MACH.0000033116.57574.95 |
| [3] | Shamir R., Sharan R., and Tsur D., “Cluster graph modification problems”, Discrete Appl. Math., 144:1-2 (2004), 173-182 · Zbl 1068.68107 · doi:10.1016/j.dam.2004.01.007 |
| [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 · Zbl 1249.68085 · doi:10.1134/S1990478907010012 |
| [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) · Zbl 1515.05172 |
| [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 · Zbl 0962.68058 |
| [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 · Zbl 1041.20021 · doi:10.1016/S0021-8693(03)00167-4 |
| [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) · Zbl 0426.90066 |
| [11] | Myasnikov A. G. and Rybalov A.N., “Generic complexity of undecidable problems”, J. Symbolic Logic, 73:2 (2008), 656-673 · Zbl 1140.03025 · doi:10.2178/jsl/1208359065 |
| [12] | Rybalov A. N., “On the strongly generic undecidability of the Halting Problem”, Theor. Comput. Sci., 377 (2007), 268-270 · Zbl 1118.03033 · doi:10.1016/j.tcs.2007.02.010 |
| [13] | Rybalov A. N., “Generic complexity of Presburger arithmetic”, Theory Comput. Systems, 46:1 (2010), 2-8 · Zbl 1186.03063 · doi:10.1007/s00224-008-9120-3 |
| [14] | Rybalov A. N., “Generic complexity of the Diophantine problem”, Groups Complexity Cryptology, 5:1 (2013), 25-30 · Zbl 1348.03036 · doi:10.1515/gcc-2013-0004 |
| [15] | Rybalov A. N., “Generic hardness of the Boolean satisfiability problem”, Groups Complexity Cryptology, 9:2 (2017), 151-154 · Zbl 1422.68095 |
| [16] | Rybalov A. N., “On generic complexity of the graph clustering problem”, Prikladnaya Diskretnaya Matematika,, 2019, no. 46, 72-77 (in Russian) · Zbl 1458.68073 |
| [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 1528.68320 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
