0
$\begingroup$

Let's say that you want to invite a person $u$ in party $P$. The person $u$ will join the party if and only if all the friends of $u$ will join the party as well. Otherwise, $u$ will reject your invitation. Hence, we have two sets: $P$ with all the persons, and $F$ with the friend relations. Suppose $(u, v)$ belongs to $F$. This means that $u$ treats $v$ as a friend of $u$, and thus $u$ will reject your invitation if $v$ does not join the party. Note that $(u, v) \in F$ doesn’t mean that $v$ treats $u$ as a friend of $v$. Also, every person $u$ in $P$ has a quality measure, $p_u$ (this can be positive or negative and is given). Now I need to find a subset of $P$, such that all those in the subset won't reject my invitation and the qualities among the people is maximized.

Here is an example of a feasible and non-feasible subset: $P = \{a, b, c, d\}, F = \{(a, b),(a, c),(b, d),(b, c)\}, p_a = 10, p_b = 1, p_c = 1, p_d = −20$.
A subset $\{a, b, c\}$ is not feasible because $d$ is not invited and thus $b$ rejects your invitation.
A subset $\{b, c, d\}$ is feasible with total quality is $p_b + p_c + p_d = −18$ which is not maximized. The optimal subset $A$ of this example is $\{c\}$ with total quality is $p_c = 1$.

Now I need to design an algorithm that finds this optimal subset in $O(|P|(|P| + |F|)^2)$ time. My thoughts: The elements in $F$ are directed edges, and the elements in $P$ are the nodes. As we are kind of dealing with a maximum flow problem, and as the required running time resembles the running time of the Ford Fulkerson algorithm $O(VE^2)$, I thought, that $(|P| + |F|)$ should be the amount of edges in the graph. Hence, my thought was to split each node $u$ into two nodes, say $u(\mathrm{in})$ and $u(\mathrm{out})$ with the directed arc $u(\mathrm{in})\rightarrow u(\mathrm{out})$ and edge weight the $p_u$. This way we have $(|P| + |F|)$ edges. However, the max flow algorithm doesn't necessarily saturate the edges it travels. However, in my case, whenever a node is reached (person is invited)/edge is travelled it adds the full flow $p_u$.

How would you approach this problem? And what are your thoughts on how the algorithm should work?

$\endgroup$
  • $\begingroup$ Hello coursemate from comp3711 :) A similar but more well-known problem is called "project selection" in max flow. $\endgroup$ – Maa Lee Nov 29 '19 at 7:28
  • $\begingroup$ @MaaLee Thank you! $\endgroup$ – Ronny Leleu Dec 5 '19 at 8:57
2
$\begingroup$

This is known as the closure problem. I quote the Wikipedia paragraph describing the reduction to the max flow problem here.

As Picard (1976) [1] showed, a maximum-weight closure may be obtained from $G$ by solving a maximum flow problem on a graph $H$ constructed from $G$ by adding to it two additional vertices $s$ and $t$. For each vertex $v$ with positive weight in $G$, the augmented graph $H$ contains an edge from $s$ to $v$ with capacity equal to the weight of $v$, and for each vertex $v$ with negative weight in $G$, the augmented graph $H$ contains an edge from $v$ to $t$ whose capacity is the negation of the weight of $v$. All of the edges in $G$ are given infinite capacity in $H$.

A minimum cut separating $s$ from $t$ in this graph cannot have any edges of $G$ passing in the forward direction across the cut: a cut with such an edge would have infinite capacity and would not be minimum. Therefore, the set of vertices on the same side of the cut as $s$ automatically forms a closure $C$. The capacity of the cut equals the weight of all positive-weight vertices minus the weight of the vertices in $C$, which is minimized when the weight of $C$ is maximized. By the max-flow min-cut theorem, a minimum cut, and the optimal closure derived from it, can be found by solving a maximum flow problem.


[1] Picard, Jean-Claude (1976), "Maximal closure of a graph and applications to combinatorial problems", Management Science, 22 (11): 1268–1272, doi:10.1287/mnsc.22.11.1268, MR 0403596.

$\endgroup$

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.