A Branch-and-Price Framework for Decomposing Graphs into Relaxed Cliques

Timo Gschwind (), Stefan Irnich (), Fabio Furini () and Roberto Wolfler Calvo ()
Additional contact information
Timo Gschwind: Department of Logistics Management, Gutenberg School of Management and Economics, Johannes Gutenberg University of Mainz, 55122 Mainz, Germany; Chair of Logistics, Department of Business Studies and Economics, Technische Universität Kaiserslautern, 67663 Kaiserslautern, Germany
Stefan Irnich: Department of Logistics Management, Gutenberg School of Management and Economics, Johannes Gutenberg University of Mainz, 55122 Mainz, Germany
Fabio Furini: Istituto di Analisi dei Sistemi ed Informatica “Antonio Ruberti” – Consiglio Nazionale delle Ricerche (IASI-CNR), 00185, Rome, Italy
Roberto Wolfler Calvo: Université Sorbonne Paris Nord, LIPN, CNRS, UMR 7030, 93430, Villetaneuse, France; Department of Mathematics and Computer Science, University of Cagliari, 09124 Cagliari, Italy

INFORMS Journal on Computing, 2021, vol. 33, issue 3, 1070-1090

Abstract: We study the family of problems of partitioning and covering a graph into/with a minimum number of relaxed cliques. Relaxed cliques are subsets of vertices of a graph for which a clique-defining property—for example, the degree of the vertices, the distance between the vertices, the density of the edges, or the connectivity between the vertices—is relaxed. These graph partitioning and covering problems have important applications in many areas such as social network analysis, biology, and disease-spread prevention. We propose a unified framework based on branch-and-price techniques to compute optimal decompositions. For this purpose, new, effective pricing algorithms are developed, and new branching schemes are invented. In extensive computational studies, we compare several algorithmic designs, such as structure-preserving versus dichotomous branching, and their interplay with different pricing algorithms. The final chosen branch-and-price setup produces results that demonstrate the effectiveness of all components of the newly developed framework and the validity of our approach when applied to social network instances.

Keywords: graph decomposition; clique relaxations; branch-and-price algorithm; social networks (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2020.0984 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:33:y:2021:i:3:p:1070-1090

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().