<p>This problem can be reduced to the Project Selection problem: suppose you have a set <span class="math-container">$P$</span> of projects each has an associated revenue <span class="math-container">$p_i \in \mathbb Z$</span> and you have dependencies between projects represented by a directed graph <span class="math-container">$G$</span> where the vertices are the projects and an edge <span class="math-container">$(i, j)$</span> means that project <span class="math-container">$i$</span> can only be selected if project <span class="math-container">$j$</span> is selected as well. We need to choose a <em>feasible</em> set of projects <span class="math-container">$A \subseteq P$</span>, where a set is feasible if for every <span class="math-container">$u \in A$</span> we have all the out-neighbors of <span class="math-container">$u$</span> also in <span class="math-container">$A$</span> (note that this induces a subgraph <span class="math-container">$G'$</span> of the set of all projects in <span class="math-container">$A$</span> as vertices and the edges joining any two vertices in <span class="math-container">$A$</span>), and the goal is to choose a feasible set of projects to maximize <span class="math-container">$\sum_{i \in A} p_i$</span>.</p>

<p>Our reduction is as follows: given a directed graph <span class="math-container">$G=(V, E)$</span> with weights on the edges <span class="math-container">$w$</span> and weights on the nodes <span class="math-container">$h$</span>, we define a new graph <span class="math-container">$G'=(V', E')$</span> as follows: we create a vertex <span class="math-container">$v_i$</span> in <span class="math-container">$V'$</span> for every node <span class="math-container">$i \in V$</span> and assign it cost <span class="math-container">$p_{v_i} = - h(i)$</span>, then for every edge <span class="math-container">$e = (i, j)$</span> in <span class="math-container">$E$</span> we create a node <span class="math-container">$u_e$</span> in <span class="math-container">$V'$</span> with cost <span class="math-container">$p_{u_e} = w(e)$</span> and we create two edges <span class="math-container">$(u_e, v_i)$</span> and <span class="math-container">$(u_e, v_j)$</span> in <span class="math-container">$E'$</span> (these indicate that this edge can only be chosen if both vertices are). To prove that this is correct, note that for a given feasible set of projects in this new problem we can immediately find the corresponding subgraph of <span class="math-container">$G$</span>, <span class="math-container">$G_A = (V_A, E_A)$</span> and we see that it maximizes
<span class="math-container">$$ \sum_{i \in A} p_i = \sum_{e \in E_A} p_{u_e} + \sum_{i \in V_A} p_{v_i} = \sum_{e \in E_A} w(e) - \sum_{i \in V_A} h(i)$$</span>
which is our original goal. The Project Selection problem can be solved by maxflow algorithms, see Kleinberg and Tardos Section 7.11 for the solution (and a more thorough description of the problem). There is <a href="https://codeforces.com/blog/entry/63544" rel="nofollow noreferrer">code for this here</a>, Problem 1082G which does a similar reduction and solves the corresponding max flow problem.</p>

CC BY-SA 4.0
2019-01-07T16:23:08.463Z
2019-01-07T16:50:06.110Z
2019-01-07T16:50:06.110Z
rka
<p>for a given weighted vertices and edges graph, we want to find the maximum subgraph. the maximum subgraph is made of some vertices and some edges of the given graph which sum of the edges minus sum of the vertices is maximum. what is the algorithm for this problem? or any help with the code please.</p>

CC BY-SA 4.0
2019-01-07T13:51:53.300Z
What ideas have you explored?  Have you tried to show the problem is NP complete? Have you found any relevant literature?
Neal Young
CC BY-SA 4.0
2019-02-09T08:11:35.770Z
Isn't this just the closure problem (https://en.wikipedia.org/wiki/Closure_problem) on a directed graph formed by subdividing each edge of the input into two oppositely-oriented directed edges?
David Eppstein
<graph-theory>
maximize edges minus vertices in a weighted graph
joo
# maximize edges minus vertices in a weighted graph

(Asked by: username_0 on 2019-01-06)

for a given weighted vertices and edges graph, we want to find the maximum subgraph. the maximum subgraph is made of some vertices and some edges of the given graph which sum of the edges minus sum of the vertices is maximum. what is the algorithm for this problem? or any help with the code please.

**Tags:** graph-theory

> **Comments:**
> **username_1**: What ideas have you explored?  Have you tried to show the problem is NP complete? Have you found any relevant literature?  
> **username_2**: Isn't this just the closure problem (https://en.wikipedia.org/wiki/Closure_problem) on a directed graph formed by subdividing each edge of the input into two oppositely-oriented directed edges?  

---

## 1 answers

### Answer by username_3 on 2019-01-07. Score: 4

This problem can be reduced to the Project Selection problem: suppose you have a set $P$ of projects each has an associated revenue $p\_i \in \mathbb Z$ and you have dependencies between projects represented by a directed graph $G$ where the vertices are the projects and an edge $(i, j)$ means that project $i$ can only be selected if project $j$ is selected as well. We need to choose a *feasible* set of projects $A \subseteq P$, where a set is feasible if for every $u \in A$ we have all the out-neighbors of $u$ also in $A$ (note that this induces a subgraph $G'$ of the set of all projects in $A$ as vertices and the edges joining any two vertices in $A$), and the goal is to choose a feasible set of projects to maximize $\sum\_{i \in A} p\_i$.

Our reduction is as follows: given a directed graph $G=(V, E)$ with weights on the edges $w$ and weights on the nodes $h$, we define a new graph $G'=(V', E')$ as follows: we create a vertex $v\_i$ in $V'$ for every node $i \in V$ and assign it cost $p\_{v\_i} = - h(i)$, then for every edge $e = (i, j)$ in $E$ we create a node $u\_e$ in $V'$ with cost $p\_{u\_e} = w(e)$ and we create two edges $(u\_e, v\_i)$ and $(u\_e, v\_j)$ in $E'$ (these indicate that this edge can only be chosen if both vertices are). To prove that this is correct, note that for a given feasible set of projects in this new problem we can immediately find the corresponding subgraph of $G$, $G\_A = (V\_A, E\_A)$ and we see that it maximizes
$$ \sum\_{i \in A} p\_i = \sum\_{e \in E\_A} p\_{u\_e} + \sum\_{i \in V\_A} p\_{v\_i} = \sum\_{e \in E\_A} w(e) - \sum\_{i \in V\_A} h(i)$$
which is our original goal. The Project Selection problem can be solved by maxflow algorithms, see Kleinberg and Tardos Section 7.11 for the solution (and a more thorough description of the problem). There is [code for this here](https://codeforces.com/blog/entry/63544), Problem 1082G which does a similar reduction and solves the corresponding max flow problem.


---

