×

zbMATH — the first resource for mathematics

Polyhedral properties of the induced cluster subgraphs. (English) Zbl 1466.90088
Summary: A cluster graph is a graph whose every connected component is a complete graph. Given a simple undirected graph \(G\), a subset of vertices inducing a cluster graph is called an independent union of cliques (IUC), and the IUC polytope associated with \(G\) is defined as the convex hull of the incidence vectors of all IUCs in the graph. The Maximum IUC problem, which is to find a maximum-cardinality IUC in a graph, finds applications in network-based data analysis. In this paper, we derive several families of facet-defining valid inequalities for the IUC polytope. We also give a complete description of this polytope for some special classes of graphs. We establish computational complexity of the separation problem for most of the considered families of valid inequalities and explore the effectiveness of employing the corresponding cutting planes in an integer (linear) programming framework for the Maximum IUC problem through computational experiments.
MSC:
90C27 Combinatorial optimization
90C10 Integer programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ames, B. P.W.; Vavasis, S. A., Convex optimization for the planted k-disjoint-clique problem, Math. Program., 143, 1, 299-337 (2014) · Zbl 1291.90194
[2] Aprile, M.; Drescher, M.; Fiorini, S.; Huynh, T., A tight approximation algorithm for the cluster vertex deletion problem (2020), arXiv preprint arXiv:2007.08057
[3] Balasundaram, B.; Butenko, S., On a polynomial fractional formulation for independence number of a graph, J. Global Optim., 35, 3, 405-421 (2006) · Zbl 1124.05069
[4] Bastos, L.; Ochi, L. S.; Protti, F.; Subramanian, A.; Martins, I. C.; Pinheiro, R. G.S., Efficient algorithms for cluster editing, J. Comb. Optim., 31, 1, 347-371 (2016) · Zbl 1341.90106
[5] Berge, C., Färbung von Graphen, deren sämtliche bzw. deren ungerade Kreise starr sind (Zusammenfassung), Wiss. Z. Martin Luther Univ. Halle-Wittenberg Math.-Nat.wiss., 10, 114-115 (1961)
[6] Bienstock, D., On the complexity of testing for odd holes and induced odd paths, Discrete Math., 90, 1, 85-92 (1991) · Zbl 0753.05046
[7] Bienstock, D., Corrigendum to: On the complexity of testing for odd holes and induced odd paths, Discrete Math., 102, 1, 109 (1992) · Zbl 0760.05080
[8] Böcker, S., A golden ratio parameterized algorithm for cluster editing, J. Discrete Algorithms, 16, 79-89 (2012) · Zbl 1257.05164
[9] Böcker, S.; Baumbach, J., Cluster editing, (Bonizzoni, P.; Brattka, V.; Löwe, B., The Nature of Computation. Logic, Algorithms, Applications. CiE 2013. The Nature of Computation. Logic, Algorithms, Applications. CiE 2013, Lecture Notes in Computer Science, vol. 7921 (2013), Springer: Springer Berlin, Heidelberg), 33-44 · Zbl 1387.68177
[10] Bomze, I. M.; Budinich, M.; Pardalos, P. M.; Pelillo, M., The maximum clique problem, (Du, D.-Z.; Pardalos, P. M., Handbook of Combinatorial Optimization (1999), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht, The Netherlands), 1-74 · Zbl 1253.90188
[11] Boral, A.; Cygan, M.; Kociumaka, T.; Pilipczuk, M., A fast branching algorithm for cluster vertex deletion, Theory Comput. Syst., 58, 2, 357-376 (2016) · Zbl 1336.68192
[12] Chang, H.; Lu, H., A faster algorithm to recognize even-hole-free graphs, J. Combin. Theory Ser. B, 113, 141-161 (2015) · Zbl 1315.05107
[13] Chen, Y.; Flum, J., On parameterized path and chordless path problems, (Twenty-Second Annual IEEE Conference on Computational Complexity, CCC’07 (2007), IEEE), 250-263
[14] Chudnovsky, M.; Cornuéjols, G.; Liu, X.; Seymour, P.; Vušković, K., Recognizing berge graphs, Combinatorica, 25, 2, 143-186 (2005) · Zbl 1089.05027
[15] Chudnovsky, M.; Robertson, N.; Seymour, P.; Thomas, R., The strong perfect graph theorem, Ann. of Math., 164, 51-229 (2006) · Zbl 1112.05042
[16] Chudnovsky, M.; Scott, A.; Seymour, P.; Spirkl, S., Detecting an odd hole, J. ACM, 67, 1 (2020), Article 5 · Zbl 07273076
[17] Colombi, M.; Mansini, R.; Savelsbergh, M., The generalized independent set problem: Polyhedral analysis and solution approaches, European J. Oper. Res., 260, 1, 41-55 (2017) · Zbl 1402.90141
[18] Conforti, M.; Cornuéjols, G.; Kapoor, A.; Vušković, K., Even-hole-free graphs part II: Recognition algorithm, J. Graph Theory, 40, 4, 238-266 (2002) · Zbl 1003.05095
[19] Dehne, F.; Langston, M. A.; Luo, X.; Pitre, S.; Shaw, P.; Zhang, Y., The cluster editing problem: Implementations and experiments, (Bodlaender, H. L.; Langston, M. A., Parameterized and Exact Computation. IWPEC 2006. Parameterized and Exact Computation. IWPEC 2006, Lecture Notes in Computer Science, vol. 4169 (2006), Springer: Springer Berlin, Heidelberg), 13-24 · Zbl 1154.68451
[20] Dessmark, A.; Jansen, K.; Lingas, A., The maximum \(k\)-dependent and \(f\)-dependent set problem, (International Symposium on Algorithms and Computation (1993), Springer), 88-97 · Zbl 0925.05062
[21] Ertem, Z.; Lykhovyd, E.; Wang, Y.; Butenko, S., The maximum independent union of cliques problem: complexity and exact approaches, J. Global Optim., 76, 545-562 (2020) · Zbl 1448.90093
[22] Ertem, Z.; Veremyev, A.; Butenko, S., Detecting large cohesive subgroups with high clustering coefficients in social networks, Social Networks, 46, 1-10 (2016)
[23] Fiorini, S.; Joret, G.; Schaudt, O., Improved approximation algorithms for hitting 3-vertex paths, (International Conference on Integer Programming and Combinatorial Optimization (2016), Springer), 238-249 · Zbl 1419.90111
[24] Fiorini, S.; Joret, G.; Schaudt, O., Improved approximation algorithms for hitting 3-vertex paths, Math. Program., 182, 1-2, 355?367 (2020) · Zbl 1442.05222
[25] Fomin, F. V.; Gaspers, S.; Kratsch, D.; Liedloff, M.; Saurabh, S., Iterative compression and exact algorithms, Theoret. Comput. Sci., 411, 7-9, 1045-1053 (2010) · Zbl 1186.68187
[26] Fomin, F. V.; Gaspers, S.; Lokshtanov, D.; Saurabh, S., Exact algorithms via monotone local search, J. ACM, 66, 2 (2019), Article 8 · Zbl 1427.68119
[27] Fomin, F. V.; Kratsch, S.; Pilipczuk, M.; Pilipczuk, M.; Villanger, Y., Tight bounds for parameterized complexity of cluster editing with a small number of clusters, J. Comput. System Sci., 80, 7, 1430-1447 (2014) · Zbl 1311.68076
[28] Garey, M.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-completeness (1979), W.H. Freeman and Company: W.H. Freeman and Company New York · Zbl 0411.68039
[29] Gramm, J.; Guo, J.; Hüffner, F.; Niedermeier, R., Automated generation of search tree algorithms for hard graph modification problems, Algorithmica, 39, 4, 321-347 (2004) · Zbl 1090.68027
[30] Grötschel, M.; Lovász, L.; Schrijver, A., Geometric Algorithms and Combinatorial Optimization (1993), Springer-Verlag: Springer-Verlag Berlin · Zbl 0837.05001
[31] Guo, J.; Komusiewicz, C.; Niedermeier, R.; Uhlmann, J., A more relaxed model for graph-based data clustering: \(s\)-plex cluster editing, SIAM J. Discrete Math., 24, 4, 1662-1683 (2010) · Zbl 1221.05293
[32] Hosseinian, S.; Butenko, S., Algorithms for the generalized independent set problem based on a quadratic optimization approach, Optim. Lett., 13, 1211-1222 (2019) · Zbl 1434.90210
[33] Hüffner, F.; Komusiewicz, C.; Moser, H.; Niedermeier, R., Fixed-parameter algorithms for cluster vertex deletion, Theory Comput. Syst., 47, 1, 196-217 (2010) · Zbl 1205.68263
[34] Jansen, K.; Scheffler, P.; Woeginger, G., The disjoint cliques problem, RAIRO-Oper. Res., 31, 1, 45-66 (1997) · Zbl 0881.90123
[35] Karp, R., Reducibility among combinatorial problems, (Miller, R. E.; Thatcher, J. W.; D., B. J., Complexity of Computer Computations. Complexity of Computer Computations, IBM Research Symposia Series (1972), Plenum Press: Plenum Press New York), 85-103
[36] Komusiewicz, C.; Uhlmann, J., Cluster editing with locally bounded modifications, Discrete Appl. Math., 160, 15, 2259-2270 (2012) · Zbl 1252.05178
[37] Krishnamoorthy, M. S.; Deo, N., Node-deletion NP-complete problems, SIAM J. Comput., 8, 4, 619-625 (1979) · Zbl 0423.05039
[38] Le, T.-N.; Lokshtanov, D.; Saurabh, S.; Thomassé, S.; Zehavi, M., Subquadratic kernels for implicit 3-hitting set and 3-set packing problems, (Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (2018), SIAM), 331-342 · Zbl 1403.68167
[39] Lewis, J. M.; Yannakakis, M., The node-deletion problem for hereditary properties is NP-complete, J. Comput. System Sci., 20, 2, 219-230 (1980) · Zbl 0436.68029
[40] Meyer, C. A.; Floudas, C. A., Trilinear monomials with positive or negative domains: Facets of the convex and concave envelopes, (Floudas, C. A.; Pardalos, P., Frontiers in Global Optimization. Frontiers in Global Optimization, Nonconvex Optimization and Its Applications, vol. 74 (2004), Kluwer Academic Publishers: Kluwer Academic Publishers Boston, MA), 327-352 · Zbl 1176.90469
[41] Nascimento, M. C.V.; De Carvalho, A. C., Spectral methods for graph clustering-a survey, European J. Oper. Res., 211, 2, 221-231 (2011) · Zbl 1250.68228
[42] Nemhauser, G. L.; Trotter, L. E., Properties of vertex packings and independence system, Math. Program., 6, 48-61 (1974) · Zbl 0281.90072
[43] Nemhauser, G. L.; Trotter, L. E., Vertex packing: structural properties and algorithms, Math. Program., 8, 232-248 (1975) · Zbl 0314.90059
[44] Nemhauser, G. L.; Wolsey, L. A., Integer and Combinatorial Optimization (1999), Wiley: Wiley New York · Zbl 0944.90001
[45] Padberg, M. W., On the facial structure of set packing polyhedra, Math. Program., 5, 199-215 (1973) · Zbl 0272.90041
[46] Padberg, M. W., A note on zero-one programming, Oper. Res., 23, 4, 833-837 (1975) · Zbl 0311.90053
[47] Pattillo, J.; Youssef, N.; Butenko, S., On clique relaxation models in network analysis, European J. Oper. Res., 226, 1, 9-18 (2013) · Zbl 1292.05208
[48] Pilipczuk, M., Exact algorithms for induced subgraph problems, (Kao, M. Y., Encyclopedia of Algorithms (2015), Springer: Springer Boston, MA)
[49] Pyatkin, A.; Lykhovyd, E.; Butenko, S., The maximum number of induced open triangles in graphs of a given order, Optim. Lett., 13, 1927-1935 (2019) · Zbl 1432.90134
[50] Schaeffer, S. E., Graph clustering, Comput. Sci. Rev., 1, 1, 27-64 (2007) · Zbl 1302.68237
[51] Shamir, R.; Sharan, R.; Tsur, D., Cluster graph modification problems, Discrete Appl. Math., 144, 1-2, 173-182 (2004) · Zbl 1068.68107
[52] Sherali, H. D.; Adams, W. P., A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems, SIAM J. Discrete Math., 3, 411-430 (1990) · Zbl 0712.90050
[53] Sherali, H. D.; Smith, J. C., A polyhedral study of the generalized vertex packing problem, Math. Program., 107, 3, 367-390 (2006) · Zbl 1134.90038
[54] Trotter, L. E., A class of facet producing graphs for vertex packing polyhedra, Discrete Math., 12, 373-388 (1975) · Zbl 0314.05111
[55] Van Bevern, R.; Moser, H.; Niedermeier, R., Approximation and tidying – a problem kernel for \(s\)-plex cluster vertex deletion, Algorithmica, 62, 3-4, 930-950 (2012) · Zbl 1236.68100
[56] Wolsey, L. A., Facets and strong valid inequalities for integer programs, Oper. Res., 24, 2, 367-372 (1976) · Zbl 0339.90036
[57] Wu, Q.; Hao, J., A review on algorithms for maximum clique problems, European J. Oper. Res., 242, 3, 693-709 (2015) · Zbl 1341.05241
[58] You, J.; Wang, J.; Cao, Y., Approximate association via dissociation, Discrete Appl. Math., 219, 202-209 (2017) · Zbl 1354.05110
[59] Zemel, E., Lifting the facets of zero-one polytopes, Math. Program., 15, 1, 268-277 (1978) · Zbl 0428.90042
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.