# Inviting an optimal subset of persons such that all friends of a person invited are invited

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?

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

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.