Ensuring connectedness for the maximum quasi‐clique and densest <i>k</i> ‐subgraph problems

Abstract Given an undirected graph , a quasi‐clique is a subgraph of with density at least . Two optimisation 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 ‐subgraph (DKS) problem, which finds the densest subgraph of a given fixed cardinality. Most existing approaches to solving both problems often disregard the requirement of connectedness, leading to unconnected solutions that may be meaningless for many real‐life applications. To address this issue, we propose two flow‐based and an Miller–Tucher–Zemlin‐based connectedness constraint for integration into existing mixed‐integer linear programming (MILP) formulations for MQC and DKS. We compare 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 competitive, making them valuable for practical applications requiring connectedness.