finding all vertices in a graph with degree smaller than their neighbors

Question

I'm trying to write an algorithm that will find the set of all vertices in a graph with degree smaller than their neighbors. My initial approach is to find the degree of each vertex, then work through the list, comparing the degree of each vertex with the degree(s) of its neighbors. Unfortunately, this looks like it could be very time consuming. Is there a more efficient way to find this set?

Answer 1

One comment - if you're working with undirected graphs (thanks, Brian R. Bondy), once you've determined that a vertex has degree less than that of all its neighbours, you don't need to check the neighbours, as none of them will have that property. Consider using that knowledge to help you out and speed things up.

Answer 2

I would imagine a greedy approach for an undirected graph as follows:

let Q = all nodes which haven't been checked (initialize all V)
let Q* = all nodes which satisfy the required condition (initialize to empty)
start with an arbitrary node, v in Q
while Q is not empty
    let minDeg be the minimum degree of all v's neighbors
    if degree(v) < minDeg
        add v to Q*
        remove all neighbors of v from Q
        remove v from Q
        set v = new arbitrary node, v in Q
    else
        remove v from Q
        set v = v's neighbor in Q of minimum degree

This algorithm may be slightly more efficient because at each iteration, it either finds a satisfying node, or checks a new node of lesser degree and removes a node from the graph.

At worst case, it will be equivalent to your brute-force algorithm. On average, though, I think it should perform better.

Answer 3

Perhaps "this looks like it could be very time consuming", but there is a better way of finding out :-)

Suppose you've stored your graph as an adjacency list. To find the set you're seeking, you necessarily have to look at all the edges, so we have a lower bound of Ω(|E|) for the algorithm. Finding the degree of every vertex takes time O(|E|) (because you look at every edge exactly once; another proof is to use the fact that ∑d(v)=2|E|). Comparing the degree of each vertex with all its neighbours also takes only O(|E|) time (again, for each edge, you make only one comparison). This means that your algorithm runs in O(|E|) time (about 2|E| "steps", but the precise number of CPU instructions depends on your implementation), which meets the lower bound. Thus your "brute-force" algorithm, in the worst case, is essentially (up to a small constant) as fast as possible, so it is not worth optimizing any further.

If you are doing this for a real-world application and you indeed find that your algorithm is taking too much time, then use a profiler to find what parts to optimize. It is not at all obvious that optimizing the second phase of the algorithm is crucial.