Question

Hi can anyone give a hint as to what is the underlying graph problem for this one ?

https://icpcarchive.ecs.baylor.edu/external/64/6450.pdf

I personally think about it like this:

Sort the number of nodes of the graph by decreasing number of edges. Then choose the top most one. After that ignore all the nodes that this top one was connected to. And choose the next one after that.

For first test case

Answer is 1 because the graph is fully connected and choosing any node will make sure all other nodes are covered.

For second test case

We can choose node 5 (this will cover node1, 2 and 4).Then we can choose node 3. This way all nodes are covered.

The problem is that this approach looks to me just made up one. This is not any graph algorithm.

It will be great if someone can give a hint. Thanks.

VVV

Was it helpful?

Solution

This is the Dominating Set problem, which is NP-hard, so unless P = NP, there is no polynomial solution for it.

Note that n < 20, so luckily we can still solve it fast enough. For every user 0 ≤ i < n, let's represent its neighborhood by a bitmask b(i) with n bits that has all the bits set that represent users reachable from i via paths of length ≤ 1. We can precompute b(i) in O(n²).

Let's define f(i,m) to be the minimal number of users needed to reach all users represented by the bitmask m, posting only on the walls of users with index ≤ i. We can compute f using the following algorithm:

f(i,m) = ∞  for all i, m
f(0, 0) = 0
f(0, b(0)) = 1
for i = 1 to n - 1:
    for m = 0 to 2^n - 1:
        f(i, m) = min(f(i, m), f(i - 1, m))
        f(i, m | b(i)) = min(f(i, m | b(i)), f(i - 1, m) + 1)    

The answer is f(n - 1, 2^n - 1). Runtime: O(n * 2^n)

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top