Efficient algorithms with performance estimates for some problems of finding several cliques in a complete undirected weighted graph

E. Kh. Gimadi   ; A. V. Kel'manov   ; A. V. Pyatkin   ; M. Yu. Khachai

Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 20 (2014) no. 2, pp. 99-112

Résumé

We consider the problem of finding a fixed number of vertex-disjoint cliques of fixed sizes in a complete undirected weighted graph with respect to the criterion of minimizing the total weight of vertices and edges in the cliques. We show that the problem is NP-hard in the strong sense both in the general case and in two particular statements, which have important applications. An approximation algorithm for this problem is presented. We show that the algorithm finds a solution with guaranteed performance estimate for the considered subclasses of the problem, and the estimate is attainable in both cases. In the case when the number of cliques to be found is fixed (i.e., is not involved in the statement), the time complexity of the algorithm is polynomial.

Détail

Mots-clés : search for vertex-disjoint cliques
Keywords: minimum total weight of vertices and edges, approximation algorithm, performance guarantee, attainable estimates, metric problem, quadratic Euclidean problem.

Bibliographie

[1] Burkard R., Dell'Amico M., Martello S., Assignments, SIAM, Philadelphia, 2009, 382 pp. | MR | Zbl

[2] De Kort J. B. J. M., “Lower bounds for symmetric $K$-peripatetic salesman problems”, Optimization, 22:1 (1991), 113–122 | DOI | MR | Zbl

[3] Dinits E. A., Kronrod M. A., “One algorithm for solving Assignment Problem”, Dokl. AN SSSR, 189:1 (1969), 23–25 | MR

[4] Garey M. R., Johnson D., Computers and intractability: A guide to the theory of $NP$-completeness, Freeman, San Francisco, 1979, 314 pp. | MR | Zbl

[5] Gimadi Edward Kh., “Approximation efficient algorithms with performance guarantees for some hard routing problems”, Proc. II Int. Conf. “Optimization and Applications” (OPTIMA 2011), Petrovac, 2011, 98–101

[6] Håstad J., “Clique is hard to approximate within $n^{1-\varepsilon}$”, Acta Math., 182:1 (1999), 105–142 | DOI | MR

[7] Kleinschmidt P., Schannath H., “A strongly polynomial algorithm for the transportation problem”, Math. Program. Ser. A, 68:1 (1995), 1–13 | MR | Zbl

[8] Krarup J., “The peripatetic salesman and some related unsolved problems”, Combinatorial programming: methods and applications, NATO Advanced Study Inst. Ser., Ser. C: Math. and Phys. Sci., 19, ed. C. R. Reeves, Reidel, Dordrecht, 1975, 173–178 | MR

[9] Park K., Lee K., Park S., “An extended formulation approach to the edge-weighted maximal clique problem”, European J. Oper. Res., 95 (1996), 671–682 | DOI | Zbl

[10] Prim R. C., “Shortest connection networks and some generalizations”, Bell System Technical J., 36:6 (1957), 1389–1401 | DOI

[11] Roskind J., Tarjan R. E., “A note on finding minimum-cost edge-disjoint spanning trees”, Math. Oper. Res., 10:4 (1985), 701–708 | DOI | MR | Zbl

[12] Spieksma F. C. R., “Multi-index assignment problems: complexity, approximation, applications”, Nonlinear assignment problems, algorithms and applications, Comb. Optim., 7, eds. L. Pitsoulis, P. Pardalos, Kluwer Acad. Publ., Dordrecht, 2000, 1–12 | MR | Zbl

[13] G. Gutin, A. Punnen, The traveling salesman problem and its variations, Comb. Optim., 12, Kluwer Acad. Publ., Dortrecht, 2002, 830 pp. | MR

[14] Baburin A. E., Gimadi E. Kh., “Ob asimptoticheskoi tochnosti effektivnogo algoritma resheniya zadachi $m$-PSP na maksimum v mnogomernom evklidovom prostranstve”, Tr. In-ta matematiki i mekhaniki UrO RAN, 16, no. 3, 2010, 12–24

[15] Galashov A. E., Kelmanov A. V., “2-priblizhennyi algoritm dlya odnoi zadachi poiska semeistva neperesekayuschikhsya podmnozhestv vektorov”, Avtomatika i telemekhanika, 2014, no. 4, 5–19

[16] Gimadi E. Kh., Glazkov Yu. V., Glebov A. N., “Priblizhennye algoritmy resheniya zadachi o dvukh kommivoyazherakh v polnom grafe s vesami reber 1 i 2”, Diskretnyi analiz i issledovanie operatsii. Ser. 2, 14:2 (2007), 41–61 | Zbl

[17] Eremin I. I., Gimadi E. Kh., Kelmanov A. V., Pyatkin A. V., Khachai M. Yu., “2-priblizhennyi algoritm poiska kliki s minimalnym chislom vershin i reber”, Tr. In-ta matematiki i mekhaniki UrO RAN, 19, no. 2, 2013, 134–143

[18] Kelmanov A. V., Pyatkin A. V., “NP-polnota nekotorykh zadach vybora podmnozhestva vektorov”, Diskretnyi analiz i issledovanie operatsii, 17:5 (2010), 37–45 | MR | Zbl

[19] Kelmanov A. V., Romanchenko S. M., “Priblizhennyi algoritm dlya resheniya odnoi zadachi poiska podmnozhestva vektorov”, Diskretnyi analiz i issledovanie operatsii, 18:1 (2011), 61–69 | MR | Zbl