# Is there a way to study precisely the complexity with respect to the size of vertex set for some graph problem?

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.)

• 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.
– D.W.
May 25 at 8:13

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).