3
$\begingroup$

I have an undirected graph represented by a list of nodes and a list of edges. What I need to produce from this is a list of nodes and edges representing a new graph containing only the nodes which have degree of at least 4. I think I've developed an algorithm. It uses an object called Node, which can store an integer for the degree of the node and a list of that node's neighboring nodes.

  1. For each node in the graph create a Node object in $O(|V|)$ time and store in a list.
  2. Traverse the list of edges in $O(|E|)$ time. While doing so update my list of nodes with their appropriate degree and neighbors.
  3. Search the list in $O(|V|)$ time and find the node with smallest degree. If >4, return. If <4, visit the node's neighbors, reduce their degrees by one, and remove this node from their list of neighbors. Then remove this node from the graph, in worst case $O(|V|)$ time.
  4. Repeat step 3. At worst $O(|V|)$ times.

If anyone is wondering, I'm doing this for a Civilization-esque game I'm making. I want to be able to separate cities that are part of major trade routes from minor ones.

Now, I think this algorithm is correct, but I'm not happy with its running time. If I'm not mistaken, it's $O(|V|^2)$, correct? Is there a way to make this more efficient?

Improve this question
$\endgroup$
3
  • $\begingroup$ Sorry for the lack of clarity. Really I only care about getting the names of the cities in my game, so I need the cities which were essentially part of a "4-clique" from the original graph. Those which had degree at least 4 in the original graph, but only if at least 4 of those neighbors also had degree of at least 4. $\endgroup$
    – user30206
    Mar 31, 2015 at 19:28
  • $\begingroup$ There are graphs that contain no 4-clique but in which every vertex has degree 4. An example is toroidal grids. Take a chess board, let the squares be vertices and add an edge from each square to the squares that are horizontally and vertically adjacent to it. Also, add edges from the $i$th square in the first row to the $i$th square in the last row, and from the $i$th square in the left column to the $i$th square in the right column, for $i=1..8$. Every vertex has degree 4 but there are no 4-cliques. $\endgroup$
    – David Richerby
    Mar 31, 2015 at 19:43
  • $\begingroup$ Ah, right. That was before I found out 4-core was the term for describing this phenomenon. $\endgroup$
    – user30206
    Mar 31, 2015 at 19:54

1 Answer 1

Reset to default
3
$\begingroup$

The object you are trying to find is known in graph theory as the 4-core. Batagelj and Zaveršnik give a simple linear time algorithm for finding the $k$-core for any given $k$.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Ah, thank you for the term describing this structure! This will make searching a lot easier. I'll give that paper a read now. $\endgroup$
    – user30206
    Mar 31, 2015 at 19:29
  • $\begingroup$ Note that this is linear in the number of edges so you can't immediately say that it's better than $O(|V|^2)$. $\endgroup$
    – David Richerby
    Mar 31, 2015 at 19:46
  • $\begingroup$ For my purposes the graphs will always be connected. Since that means $|E| \geq |V| - 1$, $O(|E|)$ should immediately be better than $O(|V|^2)$, no? $\endgroup$
    – user30206
    Mar 31, 2015 at 19:53
  • $\begingroup$ No, it could be that the graph is complete and so $|E| = |V|^2$. But in practice the number of edges is often much smaller than $|V|^2$, depending on the provenance of the graph. $\endgroup$
    – Yuval Filmus
    Mar 31, 2015 at 19:55
  • $\begingroup$ Ah, I see. So it's not guaranteed to be better, but it almost always will be. And it's still accurate to describe it as $O(|E|)$. Thanks! $\endgroup$
    – user30206
    Mar 31, 2015 at 19:56

Your Answer

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

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