1
$\begingroup$

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.

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

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.

$\endgroup$
3
  • $\begingroup$ 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 ? $\endgroup$ – Youem yesterday
  • $\begingroup$ 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.) $\endgroup$ – Misha Lavrov yesterday
  • $\begingroup$ Thank you! This should absolutely work for me. $\endgroup$ – Youem yesterday

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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