-
March 3rd, 2014, 01: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, 06: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 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.
Last edited by razzle; March 3rd, 2014 at 06:48 PM.
-
March 3rd, 2014, 08: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, 03: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 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?
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
|