1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ What ideas have you explored? Have you tried to show the problem is NP complete? Have you found any relevant literature? $\endgroup$
    – Neal Young
    Jan 7, 2019 at 13:51
  • $\begingroup$ Isn't this just the closure problem (en.wikipedia.org/wiki/Closure_problem) on a directed graph formed by subdividing each edge of the input into two oppositely-oriented directed edges? $\endgroup$ Feb 9, 2019 at 8:11

1 Answer 1

3
$\begingroup$

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, Problem 1082G which does a similar reduction and solves the corresponding max flow problem.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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