3
$\begingroup$

Suppose there is graph problem $L$ such that the instance $x$ of $L$ is a simple graph with $n$ vertices and $m$ edges.

In the Turing machine model, we can encode a graph using $O(n^2)$ cells or $O((m+1)\log n)$ cells. (i.e., $|x| = O(n^2)$ or $|x| = O(m \log n)$).

Now I want to study the lower bound and the upper bound on the time/space complexity with respect to the number of vertices $n$. Suppose we have found the upper bound is $O(f(|x|))$ and lower bound $\Omega(g(|x|))$. Since $m = O(n^2)$ and $m = \Omega(n)$, we can only conclude that $$O(f(|x|)) = O(\max\{f(n^2), f(m\log n) \}) = O(f(n^2\log n))$$ and $$\Omega(g(|x|)) = \Omega(\min \{g(n^2), g(m\log n)\}) = \Omega(g(n\log n))$$ The gap become larger. It is not tight even $f = g$.

Is there way to solve my confusion?

Now I define the graph problem as a pair $(L', O)$ where for every instance $x'$ of $L'$, it is only encoded by the number of vertices, $O$ is an oracle whose valid input is a pair of vertices $(u,v)$, it returns 1 if $uv$ is an edge in the graph and it returns 0 otherwise. Can I solve my confusion by using this model? (However it seems that $|x'| = O(\log n)$ which is very small.)

$\endgroup$
1
  • $\begingroup$ What exactly is your question? What do you mean by "the (time/space) complexity of the number of vertices n"? That doesn't make sense. You can talk about the complexity of a problem, but the number of vertices is not a problem. Can you formulate a more specific question than "Is there way to solve my confusion?"? I can't tell what you're trying to achieve or what you want to know. "Is there a way to study ...?" is probably too vague/open-ended as I'm not sure how to answer that. $\endgroup$ – D.W. May 25 at 8:13
2
$\begingroup$

I will try to lift some of the confusion you have.

Let $G$ be some graph, with $n$ vertices and $m$ edges. Then what is $|G|$? Lets say we encoded it as adjacency matrix, so it takes up $n^2$ space. Therefore, $f(|G|)=f(n^2)$ and $g(|G|)=g(n^2)$. There won't be a "gap" here.

What about if we encode it with $m\log(n)$ space? then we would have $|G|=m\log(n)$ and thus $f(|G|)=f(m\log(n))$ and $g(|G|)=g(m\log(n))$.

So what went wrong with your calculations? The difference here is that you used max once and min once to represent the same quantity. You probably did this to "give a bound" only, but notice the following interesting thing: why would we want max? we can always encode the graph in the smallest way possible, so essentially $|G|=\min \{n^2,m\log(n)\}$. Substitute this and get $g(|G|)=g(\min \{n^2,m\log(n)\})$. In the same way, $f(|G|)=f(\min \{n^2,m\log(n)\})$.

Notice I didn't give the bounds in terms of $\Omega$ and $O$, but we could. In any case, the transition $g(\min \{n^2,m\log(n)\})=\Omega(g(n\log(n)))$ is not strict, since there are many times that $\min \{n^2,m\log(n)\}> n\log(n)$. The same goes with the transition $f(\min \{n^2,m\log(n)\})=O(f(n^2)))$ (making this a min automatically made the bound better).

I hope this helped you understand a bit more how the bounds behave with respect to the size of the graph and its different encodings.

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