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.