# Maximum self sufficient induced subgraph

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.

• Can capacities be negative? – Misha Lavrov 2 days ago
• Let's assume that they are nonnegative – Youem yesterday

## 1 Answer

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.

• This is a good idea. However the time comlexity of it is $O(V \cdot E)$ which a little bit slow for me. Do you think we can do better ? – Youem yesterday
• You should be able to implement this algorithm in $O(E)$ time. For each edge $vw$, you will need to ask "is $w$ still self-sufficient now that we have deleted $v$?" (or the reverse) at most once. Just begin by computing all the values of $\sum c_e$, and don't recompute them from scratch every time. (And, I guess, only check the condition at a vertex after you've deleted an adjacent vertex.) – Misha Lavrov yesterday
• Thank you! This should absolutely work for me. – Youem yesterday