algorithmgraph-theory

An Interesting theoretical graph theory problem

My dad recently introduced me to a difficult problem he is trying to solve. The original problem arose while trying to find the optimal way to perform certain sql operations. I will be rephrasing the problem to make it far more concise and because I’m only interested in the theoretical algorithm and not the particular implementation.

Here is my colorful recreation of the problem:

You need to make everyone like you. You can make a targeted person like you by bribing them directly or sometimes by bribing a specific group of people, who already like you, to convince the target to like you.

Given the total number of people N, and a list L of K bribing options find out the cheapest way to make everyone like you.

Each bribing option shall either contain

  1. Two numbers with the first number representing the person to bribe into liking you and the second number representing the cost of the bribe.
  2. A list of numbers representing the group of people to bribe, a number representing the person to convince to like you, and a final number representing the total cost of the bribe. In order to perform a group bribe, you must of already made every individual in that group like you.

Here is an example: People: 3 Options:

In this example the optimal solution is to use the first, second, and fourth options to make everyone like you for a total cost of 18.

Can y’all help me find a generalized algorithm that will work for any case?

There aren’t concrete number limits, but I can say that the number of people is almost always going to be small (< 10) and the number of bribing options could be very large (N * (2^(N-1))).

Solution

  • Since n (number of people) is small, an approach inefficient in n may be okay.

    Let's think of the digraph like this. Each node is a state, where each of the n people is either bribed or not bribed. Then, there are 2^n nodes.

    Each node gets an arc to each node that is immediately reachable from it, i.e., that consists of the same set of bribed people as the node in question, plus one additional. The weight/cost of each arc is the cheapest cost of going between the nodes.

    Once the weights are assigned, it's a matter of using your favorite algorithm to find the shortest-path in a DAG with (presumably) nonnegative weights. https://en.wikipedia.org/wiki/Shortest_path_problem

    So how do we assign those weights? Here's one approach:

    First, give each node an id where the i'th bit is set if the i'th person is bribed. So the initial state node gets an id of 0, its children get ids that have 1 bit set, and so on.

    Next, associate the id that goes to each group that can be used for a bribe with the cost & id of the person to be bribed. Since one group can be used to bribe multiple people, represent this as a map {person_to_bribe => cost}.

    Next, parse all nodes in order of their distance from node 0. Each nodes map gets created/updated based on its predecessors, with the cost to each node being the min of its and its predecessors maps. Once this is done for depth i, assign the appropriate weight to the arcs out of each depth i node, based on the updated map.

    This is not efficient, but since n < 10 this should be fine.

    nodes: 2^n <= 2^9 = 512
arcs: choose(n,0) * choose(n,1) + choose(n,1) + choose(n,2) + ... + choose(n,n-1) * choose(n,n) <= 43,758 (equals this for n=9)