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
  • 1
    $\begingroup$ The notation $\mathsf{L}$ usually refers to logarithmic space rather than time. $\endgroup$ Commented Jul 17, 2017 at 12:30

1 Answer 1

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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