I have the following homework question on an assignment:

Consider the following reduction operation on a multigraph. Whenever a vertex has degree 2, delete the vertex, and add an edge between its two neighbors. Whenever a vertex has degree 1, delete the vertex. Whenever you have 2 edges between the same pair of vertices, delete all but 1 of these edges. Show that this reduction can be done in O(n m) time.

I am unsure how to go about this. Any help would be appreciated, thanks!

CodePudding user response：

This reduction isn't unique: consider a graph with two vertices and one edge, v-w, which has two possible reductions. I will explain how to get an arbitrary valid reduction.

You'll first want to remove duplicate edges: this can be done using a set or a hash-table to identify duplicates, in O(n m) time. I'll assume you're storing the graph as a dictionary from vertices to their adjacency sets.

After this, you'll want to iterate over the vertices, and keep a set (or any container with O(1) membership testing) to store 'to be deleted' vertices. After this first pass over vertices, this will contain any vertices with degree 1 or 2.

Now, while your 'to be deleted' set isn't empty, you'll:

• Pop a vertex v from the set.
• If v has degree 0, ignore it.
• If v has degree 1 and its neighbor is w, delete v from your graph and remove v from w's adjacency set. If w now has degree 1 or 2 and isn't in the 'to be deleted' set, add it to the set.

Otherwise, v has degree 2, and two distinct neighbors u, w.

• If u and w are not adjacent: add an edge from u to w, remove v and its edges from your graph.

• If u and w are adjacent: remove v and its edges from your graph. If u or w now have degree 1 or 2, add them to the 'to be deleted' set.

This does constant work per vertex and edge, but relies upon a certain graph representation of 'adjacency sets' where edges can be deleted in constant time. Converting to and from this representation, given adjacency lists or a list of edges, can be done in O(m n) time.