Remove degree two vertices from an undirected graph (Skiena TADM 5-22)

Question

From the Algorithm Design Manual, 2nd edition, question 5-22:

Design a linear-time algorithm to eliminate each vertex v of degree 2 from a graph by replacing edges (u,v) and (v,w) by an edge (u,w). We also seek to eliminate multiple copies of edges by replacing them with a single edge. Note that removing multiple copies of an edge may create a new vertex of degree 2, which has to be removed, and that removing a vertex of degree 2 may create multiple edges, which also must be removed.

Because the question appears in the section on undirected graphs, assume that our graph is undirected.

Here is an algorithm for removing vertices of degree two as desired, similar to the one given here. The implementation relies on Skiena's graph, queue, and edgenode structs. g->edges[v] is a pointer to the head of v's adjacency list. g->M[u][v] returns the boolean value in row u and column v of g's adjacency matrix.

The problem: according to my analysis, it does not work in linear time, no matter whether we use adjacency lists or adjacency matrices to represent our graph.

process_vertex(graph *g, int v, queue Q) {
    int u,w;
    if (degree[v] != 2) {return;}

    u = pop_first_edge(g,v); // O(n) for AL, O(n) for AM
    w = pop_first_edge(g,v); // O(n) for AL, O(n) for AM
    if (!edge_exists(g,u,w)) { // O(n) for AL, O(1) for AM
        insert_edge(g,u,w);
    }

    if (degree[u] == 2) {enqueue(Q,u);}
    if (degree[w] == 2) {enqueue(Q,w);}
}

remove_degree_twos(graph *g) {
    queue Q;
    for (int v = 1; v <= g->nvertices; ++v) {
        if (degree[v] == 2) {enqueue(Q,v);}
    }
    while (!Q.empty()) {
        process_vertex(g,dequeue(Q),Q);
    }
}

There are two required functions that have not yet been implemented:

// removes the first edge in v's adjacency list
// and updates degrees appropriately
// returns the vertex to which that edge points
int pop_first_edge(g,v);

// determines whether edge (u,v) already exists
// in graph g
bool edge_exists(g,u,v);

If g is represented with adjacency lists, then the required functions can be implemented as follows:

// O(n)
int pop_first_edge(g,v) {
    int u = -1; // the vertex to which the first outedge from v points
    edgenode *p = g->edges[v];

    if (p != NULL) {
        u = p->y;
        g->edges[v] = p->next;
        --(g->degree[v]);

        // delete v from u's adjacency list
        p1 = &g->edges[u];
        p2 = g->edges[u];
        while (p2 != NULL) {
            if (p2->y == v) {
                *p1 = p2->next;
                --(g->degree[u]);
                break;
            }
            p1 = p2;
            p2 = p2->next;
        }
    }
}

// O(n)
edge_exists(g,u,w) {
    edgenode *p = g->edges[u];

    while (p != NULL) {
        if (p->y == w) {
            return true;
        }
        p = p->next;
    }

    return false;
}

If g is represented with adjacency matrices, then we have:

// O(n)
int pop_first_edge(v) {
    int u = -1;

    for (int j = 1; j <= g->nvertices; ++j) {
        if (M[v][j]) {
            u = j;
            break;
        }
    }

    if (u > 0) {
        M[v][u] = false;
        M[u][v] = false;
        --(g->degree[v]);
        --(g->degree[u]);
        return u;
    } else {
        return -1;
    }
}

// O(1)
edge_exists(g,u,w) {
    return g->M[u][w];
}

No matter whether we use adjacency lists or adjacency matrices, the runtime of process_vertex is O(n), where n is the number of vertices in the graph. Because O(n) vertices may be processed, the total runtime is O(n^2).

How can this be done in linear time?

Answer 1

Assume we have graph G=(V,E), where

V={1,...,n} 

is set of vertices and E is set of edges, therefore subset of set

{(x,y) : x,y in V}

Usually the graph is given by the list of edges. Let's assume we receive it this way. Now:

1. make the set of edges distinct (O(m), m = |E|), consider the edges (x,y) and (y,x) equal
2. create an array representing the degree of each vertex in G (O(m) again)
3. for each vertex v of degree 2 make a list of those 2 edges (this is O(m), one iteration over the edges is sufficient)
4. at last iterate over the vertices of degree 2 and replace the related edges with one edge getting rid of vertex of degree 2 (this is O(n) operation)
5. repeat step 1. and return edges

Here's code written in python:

def remove_2_degree_vertices(n, edges):

    adj_matrix = [[0]*n for i in xrange(n)]

    #1 O(m)
    edges = get_distinct(adj_matrix, edges)

    #2 O(m)
    degrees = calculate_degrees(n, edges)

    #3 O(m)
    adj_lists = get_neighbours(degrees, edges)

    #4 O(n + m)
    to_remove, to_add_candidates = process(n, adj_lists)    
    edges.extend(to_add_candidates)
    result = [(e0,e1) for e0, e1 in edges if to_remove[e0][e1] == 0]

    #5 O(m)
    adj_matrix = [[0]*n for i in xrange(n)]
    result = get_distinct(adj_matrix, result)

    return result

def get_distinct(adj_matrix, edges):
    result = []
    for e0, e1 in edges:
        if adj_matrix[e0][e1] == 0:
            result.append((e0,e1))
            adj_matrix[e0][e1] = adj_matrix[e1][e0] = 1
    return result


def calculate_degrees(n, edges):
    result = [0]*n
    for e0, e1 in edges:
        result[e0] += 1
        result[e1] += 1
    return result


def get_neighbours(degrees, edges):
    result = {}
    for e0, e1 in edges:
        if degrees[e0] == 2:
            add_neighbour(result, e0, e1)
        if degrees[e1] == 2:
            add_neighbour(result, e1, e0)
    return result


def add_neighbour(neighbours, key, value):
    if not neighbours.has_key(key):
        neighbours[key] = set()
        neighbours[key].add(value)
    else:
        neighbours[key].add(value)


def process(n, adj_lists):
    to_remove = [[0 for i in xrange(n)] for j in xrange(n)]
    to_add_candidates = []

    if len(adj_lists) == 0:
        return to_remove, to_add_candidates

    for key in adj_lists:
        neighbours = list(adj_lists[key])
        if len(neighbours) == 1:
            to_remove[key][neighbours[0]] = to_remove[neighbours[0]][key] = 1
        else: # len(neighbours) == 2
            remove_edge(adj_lists, to_remove, key, neighbours[0], neighbours[1])
            remove_edge(adj_lists, to_remove, key, neighbours[1], neighbours[0])
            to_add_candidates.append((neighbours[0], neighbours[1]))

    return to_remove, to_add_candidates


def remove_edge(adj_lists, to_remove, key, n0, n1):
    to_remove[key][n0] = to_remove[n0][key] = 1
    if n0 in adj_lists:
        adj_lists[n0].remove(key)
        adj_lists[n0].add(n1)