An algorithm problem .. Big Oh

• Feb 19th 2011, 08:21 PM
mathdigger
An algorithm problem .. Big Oh
The following problem is from a book exercise and I've been stuck at it for quite some time:

Question: Alice wants to throw a party and is deciding whom to call. She has n people to choose from, and she has made up a list of which pairs of these people know each other. She wants to pick as many people as possible, subject to two constraints: at the party, each person should have at least 5 other people whom they know and 5 other people whom they don't know.
Give an efficient algorithm that takes as input the list of n people and the list of pairs who know each other and outputs the best choice of party invitees. Give the running time in terms of n.

My attempt: The title of the chapter is greedy algorithms so lets use a greedy approach. I start with an nxn matrix named A, full of zeros (this will be my adjacency matrix). Simultaneously, I keep a counter for each person.
I start traversing the list of pairs now, and for every pair (a, b), I insert a '1' in the corresponding place in matrix A. Simultaneously, I increment the counters of a and b by 1.

When I've done this for all the pairs, I look at the counters table. Every person X who's counter is less than 5 or greater than (n-5), i throw him out. Then i look at his row in A, and wherever I had a 1, I check those people's counters (these are the people X knew). If any of them has a counter less than 5 or greater than (n-5), I throw him out and then look at his row. I keep doing this. I keep doing this until everyone satisfies the conditions.

Is this approach correct? I keep thinking that I'm making it too complicated, and that there's a better approach. Secondly, I don't know what the running time of my approach is :( It seems to be atleast O(n^2), probably even more.

Any help would be appreciated!