IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v323y2025i2p409-424.html
   My bibliography  Save this article

Solving the Multiobjective Quasi-clique Problem

Author

Listed:
  • dos Santos, Daniela Scherer
  • Klamroth, Kathrin
  • Martins, Pedro
  • Paquete, Luís

Abstract

Given a simple undirected graph G, a quasi-clique is a subgraph of G whose density is at least γ(0<γ≤1). Finding a maximum quasi-clique has been addressed from two different perspectives: (i) maximizing vertex cardinality for a given edge density; and (ii) maximizing edge density for a given vertex cardinality. However, when no a priori preference information about cardinality and density is available, a more natural approach is to consider the problem from a multiobjective perspective. We introduce the Multiobjective Quasi-clique (MOQC) problem, which aims to find a quasi-clique by simultaneously maximizing both vertex cardinality and edge density. To efficiently address this problem, we explore the relationship among MOQC, its single-objective counterpart problems, and a bi-objective optimization problem, along with several properties of the MOQC problem and quasi-cliques. We propose a baseline approach using ɛ-constraint scalarization and introduce a Two-phase strategy, which applies a dichotomic search based on weighted sum scalarization in the first phase and an ɛ-constraint methodology in the second phase. Additionally, we present a Three-phase strategy that combines the dichotomic search used in Two-phase with a vertex-degree-based local search employing novel sufficient conditions to assess quasi-clique efficiency, followed by an ɛ-constraint in a final stage. Experimental results on synthetic and real-world sparse graphs indicate that the integrated use of dichotomic search and local search, together with mechanisms to assess quasi-clique efficiency, makes the Three-phase strategy an effective approach for solving the MOQC problem in sparse graphs in terms of running time and ability to produce new efficient quasi-cliques.

Suggested Citation

  • dos Santos, Daniela Scherer & Klamroth, Kathrin & Martins, Pedro & Paquete, Luís, 2025. "Solving the Multiobjective Quasi-clique Problem," European Journal of Operational Research, Elsevier, vol. 323(2), pages 409-424.
  • Handle: RePEc:eee:ejores:v:323:y:2025:i:2:p:409-424
    DOI: 10.1016/j.ejor.2024.12.018
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221724009603
    Download Restriction: Full text for ScienceDirect subscribers only

    File URL: https://libkey.io/10.1016/j.ejor.2024.12.018?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:ejores:v:323:y:2025:i:2:p:409-424. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.