# Densest Sub Graph and forbidden Pairs

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?

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$$.

• 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. May 13, 2023 at 10:11