# Prove that following graph problem is in $L$

I have some interesting problem:

Prove that following problem is in $L$ (decidable in logarythmic time). Decide if given undirected graph $G=(\{1,\ldots,n\}, E)$ such that $\forall_{i,j\in \{1,\ldots,n\}} i\le j \to \operatorname{dist}(1, i) \le \operatorname{dist}(1,j)$. Graph is represented as adjacent matrix.

This is exercise that I can't deal with it. I know USTCON problem and I suppose that it may be useful (crucial) here. However, I can't solve it. Can anyone try to help me defeat it ?

• The notation $\mathsf{L}$ usually refers to logarithmic space rather than time. – Yuval Filmus Jul 17 '17 at 12:30

Let $N_k$ be the set of vertices at distance $k$ from 1. A graph satisfies the property if the sets $N_k$ are intervals, and $N_{k-1} < N_k$ (every member of $N_{k-1}$ is smaller than every member of $N_k$). We will check this property inductively: assuming $N_{k-1}$ is known (starting with $N_0 = \{1\}$), we will show how to calculate $N_k$ and verify that it has the correct properties.

Suppose that $N_{k-1} = \{a,\ldots,b\}$. If $b = n$, we can stop. Otherwise, go over all neighbors of the vertices in $N_{k-1}$, and record the minimal and maximal indices $c,d$ encountered among those larger than $b$. Verify that $c = b+1$. Now go over all $e \in \{c,\ldots,d\}$, and verify that it is a neighbor of some vertex in $N_{k-1}$. If so, we have verified that $N_k = \{c,\ldots,d\}$, and can continue with $N_{k+1}$.

You can check that this algorithm can be implemented in logspace.

• "You can check that this algorithm can be implemented in logspace." Task was about log time, no logspace – Haskell Fun Jul 25 '17 at 19:36
• The problem cannot be decided in logarithmic time (you can show this using an adversary argument). The notation L, which appears in the question, refers to logarithmic space. – Yuval Filmus Jul 25 '17 at 19:37
• Oh no, on the my exam I thought that I must show log time - I know adversary technique :D So this task became fairly easy as I think. I will analyze and I will accept your answer. Thanks – Haskell Fun Jul 25 '17 at 19:40
• Thanks, it was enlightening. Adversary argument is very easy. Using log time we can't see every node.. – Haskell Fun Jul 26 '17 at 17:57