Let’s say that you want to invite a person u in 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 to 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) ∈ F doesn’t mean that v treats u as a friend of v. Also, every person u in P has a quality measure, pu (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)}, pa = 10, pb = 1, pc = 1, pd = −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 pb + pc + pd = −18 which is not maximized. The optimal subset A of this example is {c} with total quality is pc = 1.

Now I need to design an algorithm that finds this optimal subset in O(|P|(|P| + |F|)²) time. My thoughts: The elements in F are directed edges, and the elements in P are the nodes. As we are kind off dealing with a maximum flow problem, and as the required running time resembles the running time of the Ford Fulkerson algorithm O(VE²), 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(in) and u(out) with the directed arc u(in)->u(out) and edge weight the pu. 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 pu.

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