I am trying to find an efficient polynomial algorithm to solve the following problem :
For a directed graph $G = (V, E)$ such that every arc $e$ has some capacity $c_e$ and every vertex $v$ has some demand $d_v$. We know that for every vertex $v$, $$\sum_{e\in E : e=(v,w)} c_e \ge d_v.$$ We say that the graph $G$ is self-sufficient
For a fixed vertex $u$. We want to find the maximum set $S$ that does not contain $u$ and such that $G(S) = (S, E\cap \left(S\times S\right))$ is self-sufficient.
My first thought is to try to modelize the problem which I do as follow :
$$ \max_{y\in \{0,1\}^V} \sum_{v\in V} y_v : \sum_{e \in E: e = (v,w)} c_ey_w \ge d_vy_v,\; \forall v\in V;\; y_u = 0. $$
Where $y$ will be the indicator of the set $S$. The problem that I do not have any idea how to solve this problem efficiently. Does anyone have an idea.
If the self-sufficiency condition is violated at a vertex $v$ of $G$, it's also violated at $v$ in every subgraph of $G$ that contains $v$.
So if we begin by taking the set $S = V(G) - \{u\}$ and checking $G[S]$ for self-sufficiency, any vertex at which the condition is violated is a vertex we can never use. Remove those from $S$ and repeat.
Eventually we'll reach a self-sufficient $G[S]$ (in the worst case, when $S = \emptyset$). Because we only removed vertices we knew could never be part of a self-sufficient graph, we get the maximum self-sufficient graph.