Underlying Algorithm for this Graph Problem

• March 3rd, 2014, 12:50 PM
vsha041
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
• March 3rd, 2014, 05:41 PM
razzle
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.
• March 3rd, 2014, 07:02 PM
vsha041
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
• March 4th, 2014, 02:47 AM
razzle
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?
• May 3rd, 2014, 06:45 AM
vsha041
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.