1
$\begingroup$

Prove that determining if a non-directed graph of $n$ vertices has or doesn't have a length $2$ path requires time $\Omega(n^2)$, assuming that the graph is represented as an adjacency matrix.

$\endgroup$
1
$\begingroup$

Suppose the algorithm does less than $\frac{n^2-n}{2}-2(n-1)$ accesses to the matrix, then, there is at least one column (restricted to the upper triangular part of the matrix) such that there are at least two elements the algorithm have never checked.

This can be proved by contradiction, if every column has at most one unchecked element, then the algoritm have done at least $\frac{n^2-n}{2}-(n-1)$, but this contradicts the hypothesis.

Then, supposing every $a_{ij}$ element the algorithm has checked is equal to $0$, whatever the output of the algorithm, it may be wrong. Indeed, if the algorithm sais there are no paths, then, in the "doublely unchecked" column can happen that $a_{ij}=a_{kj}=1$, so there will be a path $i\to j\to k$ whose lenght is two. Otherwise, if the algorithm says there is a path, the matriz could be entirely made of $0$'s.

Note that if the graph is represented with an adjacency list for each vertex the statement does not hold, beacause there is an easy algorithm in $\mathcal{O}(n)$.

$\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.