The Square of a Graph Continued.....

Article Under Construction:
I just realized that I accidentally posted what I am currently working on but haven't finished yet. I won't delete it since there are some that have already started looking at it. Just note that it is not complete, though I hope that what is here so far is nice! Below you will see some explanation about the different types of graph implementations out there. This post will primarily be concerned with the adjacency list implementation. Enjoy!

In my last post I discussed the notion of squaring graph. To recap, the square of a graph G has the same vertex set as G and two vertices in the square are connected via an edge if they are at distance at most two in G.  Because each vertex is a distance of zero from itself there will be loops in the square of G. A simple way of determining G^2 involves matrix calculations, (mainly multiplications), with the adjacency matrix of the graph that is being squared. Since matrix multiplication is the dominant operation in this simple method the complexity is around O(n^3) where n is the size of the vertex set of G; not very good if you have a lot of vertices to look at in your graph.

So....a natural question would be: is there a faster method for squaring a graph? It's a question that I am still mulling over and will continue to address in this blog, though for the time being I have at least thought of an alternative method for determining the square of a graph that does not involve matrices or matrix calculations. My method relies on another popular implementation of graphs: that which involves so-called adjacency lists. What I will discuss in the following paragraphs will sort of be a mash up of linked lists and queues with the words adjacent and adjacency popping up a lot. Let's see what this is all about.

So...., what's an adjacency list? Well first of all, let's look at adjacency matrices in a little bit more detail. If you have a dense graph with lots of edges relative to vertices, you'll expect to see significantly more ones than zeros in the associated adjacency matrix. That's okay. Your matrix has a lot of space to store graph information but almost all of the space is being used as needed. No problem. However, consider the opposite case: your graph is sparse with relatively few edges to vertices. If you draw out your sparse graph with the dots and lines shown in previous posts, it may look kinda flimsy; not a whole lot of edges holding your vertices together. A simple example of a sparse graph would be a tree (has exactly n-1 edges defined for its n vertices). Below is a picture of some trees for reference. This same "flimsiness" will be reflected in the adjacency matrix of the graph in the form of lots of zeros. Since all of those zeros simply reflect the lack of connection between two vertices, using an entire n by n matrix for a sparse graph would be wasting space (and as n continues to get larger a considerable waste of space). That's where adjacency lists come in. Adjacency lists are basically linked lists that store only the information that is necessary for a graph.

In the adjacency list implementation of a graph, each vertex is assigned a linked list of its own that contains references to all of its neighbors. If vertex A is not adjacent to vertex B then neither of them will have a reference to each other in their associated adjacency lists. This can save a lot of space, though in terms of any drawbacks I should note that it can involve more searching time due to the nature of linked lists. Any readers that are curious about this last statement can refer to any source on linked lists which should provide details on their searching time complexities. Below is a picture of a graph along with a drawing of its associated adjacency list storage to give you a better idea of how this works.

Don't Be Such a Square!

I think that this blog has some good momentum going. Up to this point I've discussed some of the basic terminology of graphs, introduced you to graphs with interesting sounding names, and in my last post I went into a little bit more detail about one particular graph, the so-called caterpillar graph or caterpillar tree. Rather than delve right into a proof of the claims that were made at the end of that post, it would be a lot more thorough and just interesting to address some of the other things leading up to that result. I will do so in the order in which they were stated. Remember that the first claim was the following:

The square of a caterpillar graph contains a Hamiltonian path.

A natural question then is, "What exactly is the square of a graph?" You can think of the square of a graph as the original graph plus some things extra. The extra are edges that you add between two nodes in the graph if they satisfy a certain relation. In total the square will consist of the same set of vertices as the original graph with the relation defining edge connection being that two nodes x and y are neighbors if there is a path of length at most 2 between them in the original graph. That's a bit of a mouthful. Below is an illustration of this whole squaring process. To the left is our original graph which I am calling G. To the right is its square called G^2. Notice that if two nodes are already connected in the original graph then they don't need to have another edge added between when calculating the square.Also notice that the square of a graph will have a loop from each vertex to itself.

Seems simple enough. In computational terms though how difficult is it to compute the square of a graph? From a computational perspective it might be interesting to know if the square of a graph can be computed efficiently (informally meaning in a "reasonable" amount of time). This is a question that I will explore in the remainder of this graph. It is one that I am currently trying to find information for. There are plently of papers online that address the question of calculating roots of graphs, but I don't see any that at least in the title state that they are looking into algorithms for computing powers of a graph. I don't know what the computational complexity is for computing the square of a graph but in the following paragraphs I will describe a simple method for determining a graph's square and talk about its complexity.

Method #1:

One very simple way of determining the square of a graph is by performing some calculations on its underlying adjacency matrix. The adjacency matrix of a graph is a matrix representation of the connections between nodes. The rows and columns correspond to the vertices of the graph. Row i corresponds vertex i and column j vertex j. If an edge exists between vertices i and j then the i-jth entry of the matrix is a 1. Otherwise the entry is a zero. This is the typical definition of an adjacency matrix for a simple undirected and unweighted graph. Below is an example of such a graph and its corresponding adjacency matrix. In this example I have labeled the vertices a through d and the columns and rows of the adjacency matrix correspond to those vertices in the same order from left to right and top to bottom. Notice that since the graph is simple the entries along the main diagonal are all zeros. This just reflects the fact that we are excluding loops.

There is a basic result in graph theory that shows that if you square the adjacency matrix of a graph, the i-jth entries  correspond to the number of walks of length 2 between pairs of vertices i and j. I will not go into the proof of that but simply state it as fact in this post. It follows from that result that if you 1. add the entries in the original adjacency matrix to the non-diagonal entries of the square and  2. convert the nonzero entries to the number one you will obtain the adjacency matrix for the square of the graph. This method then gives us a simple way of determining the square of a graph.See if you can follow steps 1 and 2 on the first graph of the post to obtain the adjacency matrix of its square on the right.

Now for the complexity part. In the computation for this method, the two key steps are 1. matrix multiplication, and 2. matrix addition. Out of the two steps the one that takes more time computationally is the multiplication which takes running time around O(n^3) (The O here stands for big-O notation). I say around because the amount of time really depends on which matrix multiplication algorithm you select for squaring the adjacency matrix. The traditional method of multiplying rows by columns is O(n^3). There is a better algorithm for multiplying matrices though that is O(n^log7). It is known as Strassen's algorithm and was noteable for being the first one to break the O(n^3) barrier. The addition of two square matrices just involves adding elements of the corresponding matrix entries and is O(n^2). So using some basic results involving big-O notation we can say that this simple method of squaring a matrix is O(n^3).

Some of you may wonder if a better method for the problem at hand exists. In terms of complexity you may wonder if  we can improve on this upper bound in any way. One possibility that I will consider in an upcoming post is to look at the incidence matrix representation of the graph rather than the adjacency matrices that were involved in the above calculations. What exactly incidence matrices are as well as an elaboration on their uses will be discussed in that post. Try to see if you can find or think of faster ways of computing the square of a graph. As I hinted above, the answer may lie in the underlying implementation of the graph. As a side note it turns out there are lots of ways of storing the information of a graph besides the simple matrices discussed above. In terms of their set up they may seem more complex but are well worth the effort in other ways.

So until the next post....keep on graphing! :-)