A branch-and-cut algorithm for the edge interdiction clique problem. (English) Zbl 07356517

Summary: Given a graph \(G\) and an interdiction budget \(k \in \mathbb{N} \), the Edge Interdiction Clique Problem (EICP) asks to find a subset of at most \(k\) edges to remove from \(G\) so that the size of the maximum clique, in the interdicted graph, is minimized. The EICP belongs to the family of interdiction problems with the aim of reducing the clique number of the graph. The EICP optimal solutions, called optimal interdiction policies, determine the subset of most vital edges of a graph which are crucial for preserving its clique number. We propose a new set-covering-based Integer Linear Programming (ILP) formulation for the EICP with an exponential number of constraints, called the clique-covering inequalities. We design a new branch-and-cut algorithm which is enhanced by a tailored separation procedure and by an effective heuristic initialization phase. Thanks to the new exact algorithm, we manage to solve the EICP in several sets of instances from the literature. Extensive tests show that the new exact algorithm greatly outperforms the state-of-the-art approaches for the EICP.


90C35 Programming involving graphs or networks
05C85 Graph algorithms (graph-theoretic aspects)
90C27 Combinatorial optimization
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut


Full Text: DOI Link


[1] to appear
[2] Bay, H.; Tuytelaars, T.; Gool, L. V., Surf: Speeded up robust features, Proceedings of the computer vision - ECCV 2006 (2006)
[3] July 25, 2004
[4] Chen, H.; Chung, W.; Xu, J. J.; Wang, G.; Qin, Y.; Chau, M., Crime data mining: A general framework and some examples, Computer, 37, 4, 50-56 (2004)
[5] Coniglio, S.; Furini, F.; San Segundo, P., A new combinatorial branch-and-bound algorithm for the knapsack problem with conflicts, European Journal of Operational Research, 289, 2, 435-455 (2021)
[6] Cornaz, D.; Furini, F.; Malaguti, E., Solving vertex coloring problems as maximum weight stable set problems, Discrete Applied Mathematics, 217, 151-162 (2017) · Zbl 1358.05098
[7] DIMACS2 (2017) 2nd DIMACS implementation challenge - NP Hard Problems: Maximum Clique, Graph Coloring, and Satisfiability. URL http://dimacs.rutgers.edu/Challenges/.
[8] DIMACS10 (2017). 10th DIMACS implementation challenge - Graph partitioning and graph clustering. URL https://www.cc.gatech.edu/dimacs10/.
[9] Fischetti, M.; Leitner, M.; Ljubić, I.; Luipersbeck, M.; Monaci, M.; Resch, M.; Sinnl, M., Thinning out Steiner trees: A node-based model for uniform edge costs, Mathematical Programming Computation, 9, 2, 203-229 (2017) · Zbl 1387.90132
[10] Fischetti, M.; Ljubić, I.; Monaci, M.; Sinnl, M., A new general-purpose algorithm for mixed-integer bilevel linear programs, Operations Research, 65, 60, 1615-1637 (2017) · Zbl 1386.90085
[11] Fischetti, M.; Ljubić, I.; Monaci, M.; Sinnl, M., Interdiction games under monotonicity, INFORMS Journal on Computing, 31, 2, 390-410 (2019) · Zbl 07281718
[12] Fischetti, M.; Lodi, A., Local branching, Mathematical Programming, 98, 1-3, 23-47 (2003) · Zbl 1060.90056
[13] Fischetti, M.; Monaci, M.; Sinnl, M., A dynamic reformulation heuristic for generalized interdiction problems, European Journal of Operational Research, 267, 1, 40-51 (2018) · Zbl 1403.90524
[14] Furini, F.; Iori, M.; Martello, S.; Yagiura, M., Heuristic and exact algorithms for the interval minmax regret knapsack problem, INFORMS Journal on Computing, 27, 2, 392-405 (2015) · Zbl 1329.90119
[15] Furini, F.; Ljubić, I.; Martin, S.; San Segundo, P., The maximum clique interdiction problem, European Journal of Operational Research, 277, 1, 112-127 (2019) · Zbl 1430.90543
[16] Hassan, M.-A.; Kacem, I.; Martin, S.; Osman, I. M., On the \(m\)-clique free interval subgraphs polytope: Polyhedral analysis and applications, Journal of Combinatorial Optimization, 36, 3, 1074-1101 (2018) · Zbl 1418.05103
[17] Håstad, J., Clique is hard to approximate within \(n^{1 - \epsilon}\), Acta Mathematica, 182, 105-142 (1999) · Zbl 0989.68060
[18] Kasperski, A., Discrete optimization with interval data - Minmax regret and fuzzy approach, Studies in Fuzziness and Soft Computing, 228 (2008), Springer · Zbl 1154.90017
[19] Li, C.; Fang, Z.; Jiang, H.; Xu, K., Incremental upper bound for the maximum clique problem, INFORMS Journal on Computing, 30, 1, 137-153 (2018) · Zbl 07271629
[20] Li, C.; Liu, Y.; Jiang, H.; Many, F.; Li, Y., A new upper bound for the maximum weight clique problem, European Journal of Operational Research, 270, 1, 66-77 (2018) · Zbl 1403.90640
[21] Lowe, D. G., Distinctive image features from scale-invariant keypoints, International Journal of Computer Vision, 60, 2, 91-110 (2004)
[22] Malaguti, E.; Monaci, M.; Toth, P., An exact approach for the vertex coloring problem, Discrete Optimization, 8, 2, 174-190 (2011) · Zbl 1244.05092
[23] Malaguti, E.; Toth, P., A survey on vertex coloring problems, International Transactions in Operational Research, 17, 1, 1-34 (2010) · Zbl 1223.05079
[24] Pajouh, F. M.; Boginski, V.; Pasiliao, E. L., Minimum vertex blocker clique problem, Networks, 64, 1, 48-64 (2014) · Zbl 1390.90183
[25] Sageman, M., Understanding terrorist networks (2004), University of Pennsylvania Press: University of Pennsylvania Press Philadelphia, PA, USA
[26] Sampson, R. J.; Groves, W. B., Community structure and crime: Testing social-disorganization theory, American Journal of Sociology, 94, 4, 774-802 (1989)
[27] San Segundo, P.; Artieda, J., A novel clique formulation for the visual feature matching problem, Applied Intelligence, 43, 2, 325-342 (2015)
[28] San Segundo, P.; Coniglio, S.; Furini, F.; Ljubi, I., A new branch-and-bound algorithm for the maximum edge-weighted clique problem, European Journal of Operational Research, 278, 1, 76-90 (2019) · Zbl 1430.90552
[29] San Segundo, P.; Furini, F.; Artieda, J., A new branch-and-bound algorithm for the maximum weighted clique problem, Computers & Operations Research, 110, 18-33 (2019) · Zbl 1458.90624
[30] San Segundo, P.; Lopez, A.; Batsyn, M.; Nikolaev, A.; Pardalos, P. M., Improved initial vertex ordering for exact maximum clique search, Applied Intelligence, 45, 3, 868-880 (2016)
[31] San Segundo, P.; Lopez, A.; Pardalos, P. M., A new exact maximum clique algorithm for large and massive sparse graphs, Computers & Operations Research, 66, 81-94 (2016) · Zbl 1349.90824
[32] San Segundo, P.; Matia, F.; Rodriguez-Losada, D.; Hernando, M., An improved bit parallel exact maximum clique algorithm, Optimization Letters, 7, 3, 467-479 (2013) · Zbl 1268.90118
[33] San Segundo, P.; Nikolaev, A.; Batsyn, M., Infra-chromatic bound for exact maximum clique search, Computers & Operations Research, 64, 293-303 (2015) · Zbl 1349.90825
[34] San Segundo, P.; Rodríguez-Losada, D.; Jiménez, A., An exact bit-parallel algorithm for the maximum clique problem, Computers & Operations Research, 38, 2, 571-581 (2011) · Zbl 1231.90369
[35] San Segundo, P.; Nikolaev, A.; Batsyn, M.; Pardalos, P. M., Improved infra-chromatic bound for exact maximum clique search, Informatica, 27, 2, 463-487 (2016) · Zbl 1387.05257
[36] San Segundo, P.; Tapia, C., Relaxed approximate coloring in exact maximum clique search, Computers & Operations Research, 44, 185-192 (2014) · Zbl 1307.90153
[37] Stentiford, F., Face recognition by detection of matching cliques of points, 9024, 148-158 (2014)
[38] Tang, Y.; Richard, J.-P. P.; Smith, J. C., A class of algorithms for mixed-integer bilevel min-max optimization, Journal of Global Optimization, 66, 2, 225-262 (2016) · Zbl 1380.90197
[39] Wu, Q.; Hao, J., An adaptive multistart tabu search approach to solve the maximum clique problem, Journal of Combinatorial Optimization, 26, 1, 86-108 (2013) · Zbl 1275.90084
[40] Zachary, W. W., An information flow model for conflict and fission in small groups, Journal of Anthropological Research, 33, 4, 452-473 (1977)
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.