I would like to solve the following:
Let $G=(V,E)$ be a directed graph such as $\forall (x,y) \in E, x \neq y$.
Find any (all would be even better) graphs $S$ such that:
- $S \subset V$
- $\#\{(x,y) \mid (x,y) \in E, x \not \in S, y \in S\} \leq k \times \#S$
where $k$ is a strictly-positive rational.
In short, what I need to find is subsets $S$ of the graph’s variables which have less edges going from $V \setminus S $ to $S$ than some $k$ times their size. The idea is to find “relatively isolated” subsets of the graph’s variables.
Before starting to work on a solving algorithm, I wondered if the problem had already been solved, but I don’t really know what keywords to search for.
Alternatively, if the problem hasn’t arleady been solved, I don’t have any idea as to where to start. Perhaps starting with the naïve algorithm that tries all subsets and then try to look through the “good ones” first ?
Thank you for your help.