1
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ The standard matrix multiplication takes $O(n^3)$ time. Do you actually mean $o(n^3)$ time? Another way to obtain the adjacency matrix of $G'$ is just using the standard matrix product of A and itself, but replacing its non-zero entries with 1. $\endgroup$ – Apass.Jack Nov 16 '18 at 16:19
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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