Given two graphs $G$ and $F$ on the same vertex set $V$. Compute a sub set $\tilde{V}\subset V$ which' sub graph of $G$ is of maximum density and does not have any pair that is connected in $F$.

Formally, find

$$ arg\max_{\tilde{V}\subset V}\Bigg\{\frac{\big\vert {E(G)}_{\vert\tilde{V}}\big\vert}{\vert \tilde{V}\vert} \,\,\Bigg\vert\,\, (v, v^{\prime})\notin E(F)\forall v, v^{\prime}\in\tilde{V} \Bigg\} $$.

So, we could compute maximum independent sets of $F$ and compute for each its densest sub graph. This may not yield a desired node set. Looks like we want 'high overlaps' between $G$-density and $F$-independency.

Is there a method to solve this or some ideas on how to combine densest-sub-graph-algorithm and maximum-independence-set-algorithm?


1 Answer 1


The problem is NP-hard. (It is at least as hard as maximum independent set, which can be seen by setting $G$ to be the fully connected graph.)

Therefore, a reasonable approach is to use an off-the-shelf ILP solver. Introduce zero-or-one variables $x_{v}$, with the intended meaning that $x_v=1$ means that $v \in \tilde{V}$. Define $y_{u,v} := x_u \land x_v$. Introduce a new (real-valued) unknown $d$ to represent the density. Then you can encode all of the requirements via the following linear inequalities:

  • The density is at least $d$: i.e., $\sum_{u,v} y_{u,v} \ge d \sum_v x_v$.

  • The $y$'s are consistent with the $x$'s: i.e., $y_{u,v} \ge x_u + x_v - 1$, $y_{u,v} \le x_u$, $y_{u,v} \le x_v$.

  • There is no pair that is connected in $F$: i.e., $y_{u,v}=0$ for all $(u,v) \in E(F)$.

Finally, ask the ILP solver to maximize $d$, subject to the above linear inequalities.

Alternatively, you could use a SAT solver together with a pseudo-boolean constraint to represent the constraint on the density, and use binary search over $d$.

  • $\begingroup$ Excellent and complete answer, thanks so much @D.W.! I really like it and will try MIP solver. Could try it through z3-solver for the smt variation, this will probably be much slower. $\endgroup$ May 13, 2023 at 10:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.