
March 3rd, 2014, 12:50 PM
#1
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
#2
Re: Underlying Algorithm for this Graph Problem
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 friendset).
There's also the set of all users that should be reached (the targetset).
The problem becomes, what's the smallest number of friendsets that together as a union contains all users of the targetset or more?
There's an efficient approximately optimal greedy algorithm for this problem:
First select the friendset that share the most users with the targetset. Remove these from the targetset. Then repeat this with the remaining friendsets until the targetset is empty. It's then covered by the selected friendsets.
Last edited by razzle; March 3rd, 2014 at 05:48 PM.

March 3rd, 2014, 07:02 PM
#3
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
#4
Re: Underlying Algorithm for this Graph Problem
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 NPcomplete 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?
Last edited by razzle; March 15th, 2014 at 04:48 PM.

May 3rd, 2014, 06:45 AM
#5
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.
Tags for this Thread
Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules

Click Here to Expand Forum to Full Width
