3
$\begingroup$

Consider a sequence of vertex and edge additions and removals to an initially empty (undirected, simple) graph.

Is it possible to update the ordered list of vertex degrees in constant time (and space), for each addition or removal? How?

Is it easier to update only the maximal degree (lower time or space complexity)? How?

$\endgroup$
0

2 Answers 2

2
$\begingroup$

I would assume here that adding/removing edges/vertices will be done one at a time. Please take note, the term node is used for a node in a linked list and I tried my best not to use it interchangeably with the term vertex.

The structures for storing vertices and edges

Let A be your adjacency list for the graph.

Let V be an array (ordinary/associative depending on your actual vertex representation) of pointers. An entry in V points to a vertex stored in the structure D given below.

Let D be a doubly linked list. A node n of this list holds two data: d an integer that represents the degree and a doubly linked list l containing all vertices with degree d. We shall maintain that the nodes of D are ordered in increasing value of d. You can think of nodes in D like a bucket containing all vertices with the same degrees. D will have a tail pointer that points to the end (bucket containing vertices with maximal degree).

Initially, D only has a node n0 such that n0.d = 0, which will contain all newly added vertex (assuming that newly added vertex has no edge yet).

The entries of list l are vertices with degree d. Each vertex v in l has a pointer b that points back to the node in D where l belongs.

Adding a new vertex

When you add a new vertex v, create an entry in A and add it to n0.l and finally add an entry in V that will point to v in D. Set v.b to n0.

Adding and removing edges

When a new edge (u,v) is added, add the nodes (using the procedure above) if they do not exist yet. Update the entries of A. Then, follow the pointer of u in V. At this point, the degree of u will increase by 1. Follow u.b pointer to get the node n in D containing u. Let n' be the node following n in D. If n'.d = n.d + 1, transfer u to n'.l. If n' does not exists or n'.d > n.d + 1, insert a new node m after n such that m.d = n.d + 1 and transfer u to this node. Update u.b. If after this n.l becomes empty , delete it, except when n = n0. Do the same update to vertex v. Finally, update the tail pointer of D in case the the last node in D changes.

When you remove an edge, you can simply reverse the process of adding (I will leave this one for you to think about).

Removing a vertex

Removing a vertex v can be implemented by first removing all its edges one at a time using the edge removal procedure above, then finally removing v from D, V, and A.

Analysis

Updating the edges of a vertex and maintaining the order of D after adding a vertex and updating edges takes $O(1)$ time (ignoring the cost of adding a new entry in A and V which is dependent on how you implement them). This is because we only need to follow and update constant number of pointers and create/remove constant number of nodes in the linked lists.

As for the removal of a vertex v, the time is $O(deg(v))$, which I think is optimal since you have to update that many vertices too since you have to update the neighbors of the removed vertex.

Each entire representation requires $O(n)$ extra space for the pointers and linked list nodes for each vertex. This is $O(1)$ additional space per vertex.

$\endgroup$
5
  • $\begingroup$ Nice proposal, thank you! I need some time to check the details, but I wanted to say that I consider the removal of $v$ in time $O(deg(v))$ as constant time per vertex/edge removal, since it does remove $deg(v)$ edges. $\endgroup$ Mar 10, 2022 at 19:08
  • $\begingroup$ BTW, I would love to know your thoughts on that question: cs.stackexchange.com/questions/146325/… if any. $\endgroup$ Mar 10, 2022 at 19:09
  • $\begingroup$ I agree with your proposal, thanks! I would be interested in a purely array-based one, but I am now pretty sure it is feasible. $\endgroup$ Mar 17, 2022 at 15:50
  • $\begingroup$ Just to clarify, what do you mean by pure array-based? If you want to remove the double linked list, you can replace it with an array $\endgroup$
    – Russel
    Mar 20, 2022 at 10:01
  • $\begingroup$ I just posted a solution to a more general problem, see my answer here, which I would call array-based. Thanks for your help. $\endgroup$ May 11, 2022 at 18:44
0
$\begingroup$

This is a special case of sorted counters, for which a constant-time solution is given there.

For degrees, a counter is needed for each vertex, and its value is bounded by the number $n$ of (present) vertices. If $n$ is known beforehand, and if vertices are numbers from $0$ to $n-1$, then the generic solution may be optimized: hash tables and dynamic arrays may be replaced by static arrays, which gives a constant worst case time complexity.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.