  Given an undirected graph $G$, a quasi-clique is a subgraph of $G$ whose
density is at least $\gamma$ $(0 < \gamma \leq 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.
