Matrix of a graph and computational complexity

Question

Given a simple undirected graph with no self-loops, $G = (V,E)$, where $V = {1,2,...,n}$, an $n × n$ matrix $A$ is said to be the adjacency matrix of $G$ if $A_{i,j}$ is $1$ if $(i, j) ∈ E$ and $0$ otherwise. Now, suppose we define a special kind of matrix product for matrices whose entries are only 0 or 1. In this special matrix product we replace addition by OR and multiplication by AND. With this being our definition of the matrix product answer the following questions:

1. If $B_2 = (A+I)^2$ then argue that $B_2 = C_2 +I$ where $C_2$ is the adjacency matrix of the graph $G′ = (V,E′)$ with the same vertex set as $G$. We say that $(i,j) ∈ E′$ if $(i,j) ∈ E$ or there exists a $k ∈ V$ such that $(i,k),(k,j) ∈ E$.

2. Is it possible to compute $C_2$ (by some other way perhaps) in time which is $o(n^2)$? Or is there some example on which the time taken to compute $C_2$ has to be $Ω(n^2)$? Cause I think that in this case the time taken would be $θ(n^2)$

I tried manipulating $B_2$ and then applying the new matrix product properties, but I wasn't able to give a concrete argument about $C_2$. As far as the complexity goes, I have no idea on how to go about with it. Any help is appreciated. Thanks!

Answer 1

Let $B_1 = I + A$. Then $B_1(i,j) = 1$ iff $d(i,j) \leq 1$, where $d(i,j)$ is the distance between $i$ and $j$ in the graph. Now $B_2 = B_1^2$, and so by definition, $$ (B_2)_{ij} = \bigvee_k (B_1)_{ik} \land (B_1)_{kj}. $$ In words, $(B_2)_{ij} = 1$ iff there exists a vertex $k$ such that $(B_1)_{ik} = (B_1)_{kj} = 1$, i.e. $d(i,k) \leq 1$ and $d(k,j) \leq 1$.

We can now prove that $(B_2)_{ij} = 1$ iff $d(i,j) \leq 2$. Indeed, if $(B_2)_{ij} = 1$ then there exists $k$ such that $d(i,k),d(k,j) \leq 1$, and so $d(i,j) \leq d(i,k) + d(k,j) \leq 2$. Conversely, suppose that $d(i,j) \leq 2$. We consider two cases. If $d(i,j) \leq 1$ then $k := j$ satisfies $d(i,k) \leq 1$ and $d(k,j) = 0 \leq 1$, and so $(B_2)_{ij} = 1$. If $d(i,j) = 2$, choose a shortest path from $i$ to $j$, and let $k$ be the vertex in the middle. Then $d(i,k) = d(k,j) = 1$. In both cases, $(B_2)_{ij} = 1$.

You cannot compute $C_2$ faster than $n^2$, simply because it contains $n^2$ many entries. The asymptotically fastest way known to compute $C_2$ is by squaring $I + A$ (using the usual matrix multiplication), zeroing the diagonal, and replacing each entry larger than 1 with 1. This takes time $O(n^\omega)$, where $\omega$ is the matrix multiplication constant.