2024/03/13 by Daniela Scherer dos Santos, Santos, Daniela Scherer dos, Kathrin Klamroth +5 · 1 citation
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.2403.08534
openalex publication_date 2024/03/13 · openalex created_date 2024/03/15 · openalex updated_date 2026/07/28
Given an undirected graph G, a quasi-clique is a subgraph of G whose density is at least γ (0 < γ≤ 1). Two optimization problems can be defined for quasi-cliques: the Maximum Quasi-Clique (MQC) Problem, which finds a quasi-clique with maximum vertex cardinality, and the Densest k-Subgraph (DKS) Problem, which finds the densest subgraph given a fixed cardinality constraint. Most existing approaches to solve both problems often disregard the requirement of connectedness, which may lead to solutions containing isolated components that are meaningless for many real-life applications. To address this issue, we propose two flow-based connectedness constraints to be integrated into known Mixed-Integer Linear Programming (MILP) formulations for either MQC or DKS problems. We compare the performance of MILP formulations enhanced with our connectedness constraints in terms of both running time and number of solved instances against existing approaches that ensure quasi-clique connectedness. Experimental results demonstrate that our constraints are quite competitive, making them valuable for practical applications requiring connectedness.