Underlying Algorithm for this Graph Problem

Hi,

Can anyone give an hint as to what is the underlying problem for this graph problem?

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

I think we need to sort the number of nodes by most edges and as we choose a node, ignore the nodes to which this selected node is connected to?

Any hints will be appreciated.

Thanks

Re: Underlying Algorithm for this Graph Problem

Quote:

Originally Posted by

**vsha041**
the underlying problem?

I'd say it's a set cover problem.

Associated with every user there's a set of friends (a friend-set).

There's also the set of all users that should be reached (the target-set).

The problem becomes, what's the smallest number of friend-sets that together as a union contains all users of the target-set or more?

There's an efficient approximately optimal greedy algorithm for this problem:

First select the friend-set that share the most users with the target-set. Remove these from the target-set. Then repeat this with the remaining friend-sets until the target-set is empty. It's then covered by the selected friend-sets.

Re: Underlying Algorithm for this Graph Problem

Thanks Razzle for your time and effort. This problem turns out to be NP Complete and the problem is basically Dominating Set Problem.

http://en.wikipedia.org/wiki/Dominating_set

Re: Underlying Algorithm for this Graph Problem

Quote:

Originally Posted by

**vsha041**
This problem turns out to be NP Complete and the problem is basically Dominating Set Problem.

Well, I think my formulation as a Set Cover problem is correct. In the Wikipedia entry Dominating Set is listed as related so I guess both formulations are possible.

Set Cover is also NP-complete but it has the advantage of efficient approximate solutions (of which I mentioned one). It's almost a necessity if an NP hard algorithm is to be used in practice. I don't know the situation for Dominating Set.

Please feel free to explain why you prefer Dominating Set?

Re: Underlying Algorithm for this Graph Problem

Sorry for late reply but your answer is also right. I got my code ACCEPTED by writing brute force solution of dominating set problem.