Underlying Algorithm for this Graph Problem
 CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

# Thread: Underlying Algorithm for this Graph Problem

1. Junior Member
Join Date
Apr 2009
Posts
16

## 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

2. Member +
Join Date
Jul 2013
Posts
576

## 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 05:48 PM.

3. Junior Member
Join Date
Apr 2009
Posts
16

## 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

4. Member +
Join Date
Jul 2013
Posts
576

## 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.

5. Junior Member
Join Date
Apr 2009
Posts
16

## 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.

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•