1
$\begingroup$

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 ?

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

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ "You can check that this algorithm can be implemented in logspace." Task was about log time, no logspace $\endgroup$ – Haskell Fun Jul 25 '17 at 19:36
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Jul 25 '17 at 19:37
  • $\begingroup$ 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 $\endgroup$ – Haskell Fun Jul 25 '17 at 19:40
  • $\begingroup$ Thanks, it was enlightening. Adversary argument is very easy. Using log time we can't see every node.. $\endgroup$ – Haskell Fun Jul 26 '17 at 17:57

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.