• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail - Request a copy

The maximum clique interdiction problem

Furini, Fabio; Ljubić, Ivana; Martin, Sébastien; San Segundo, Pablo (2019), The maximum clique interdiction problem, European Journal of Operational Research, 277, 1, p. 112-127. 10.1016/j.ejor.2019.02.028

Type
Article accepté pour publication ou publié
Date
2019
Journal name
European Journal of Operational Research
Volume
277
Number
1
Publisher
Elsevier
Pages
112-127
Publication identifier
10.1016/j.ejor.2019.02.028
Metadata
Show full item record
Author(s)
Furini, Fabio
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Ljubić, Ivana
ESSEC Business School
Martin, Sébastien cc
Laboratoire de Conception, Optimisation et Modélisation des Systèmes [LCOMS]
San Segundo, Pablo
autre
Abstract (EN)
Given a graph G and an interdiction budget k, the Maximum Clique Interdiction Problem asks to find a subset of at most k vertices to remove from G so that the size of the maximum clique in the remaining graph is minimized. This problem has applications in many areas, such as crime detection, prevention of outbreaks of infectious diseases and surveillance of communication networks. We propose an integer linear programming formulation of the problem based on an exponential family of Clique-Interdiction Cuts and we give necessary and sufficient conditions under which these cuts are facet-defining. Our new approach provides a useful tool for analyzing the resilience of (social) networks with respect to clique-interdiction attacks, i.e., the decrease of the size of the maximum clique as a function of an incremental interdiction budget level. On a benchmark set of publicly available instances, including large-scale social networks with up to one hundred thousand vertices and three million edges, we show that most of them can be analyzed and solved to proven optimality within short computing time.
Subjects / Keywords
Combinatorial optimization; Interdiction problems; Maximum clique; (Social) Network analysis; Most vital vertices

Related items

Showing items related by title and author.

  • Thumbnail
    A new branch-and-bound algorithm for the maximum edge-weighted clique problem 
    San Segundo, Pablo; Coniglio, Stefano; Furini, Fabio; Ljubić, Ivana (2019) Article accepté pour publication ou publié
  • Thumbnail
    Tighter MIP models for Barge Container Ship Routing 
    Alfandari, Laurent; Davidović, Tatjana; Furini, Fabio; Ljubić, Ivana; Maraš, Vladislav; Martin, Sébastien (2019) Article accepté pour publication ou publié
  • Thumbnail
    On the Maximum Flow Blocker Problem 
    Bentoumi, Isma; Furini, Fabio; Mahjoub, Ali Ridha; Martin, Sébastien (2022) Communication / Conférence
  • Thumbnail
    An effective dynamic programming algorithm for the minimum-cost maximal knapsack packing problem 
    Furini, Fabio; Ljubić, Ivana; Sinnl, Markus (2017) Article accepté pour publication ou publié
  • Thumbnail
    ILP and CP Formulations for the Lazy Bureaucrat Problem 
    Furini, Fabio; Ljubić, Ivana; Sinnl, Markus (2015) Communication / Conférence
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo