5
$\begingroup$

Given an Graph $G(V,E)$ with $|V|=n$ and $|E|=m$.

The goal is to find a vertex ordereing $\sigma$ of V such that for each vertex $v\in V$, all neighbours of $v$ occur in $O(\sqrt{m})$ sequences in $\sigma$. That is if I locate all neighbours of $v$ in $\sigma$ I find all the neighbours present in chunks in $\sigma$, where number of such chunks is $O(\sqrt{m})$.

Clearly any vertex with degree $<\sqrt{m}$ does not voilate any vertex ordering as even if all its neighbours are separated in $\sigma$ the number of sequences/chunks cannot exceed $degree$ of the vertex.

Does such an ordering always exists?Can I find such an ordering efficiently?

Best case would be to find such an ordering in $O(m)$ time. Also is it possible for find such an ordering for smaller number of chunks/sequences?

$\endgroup$

1 Answer 1

6
$\begingroup$

So if I understand it correctly you want the neighbors of each vertex to form a small number of contiguous blocks of the ordering? Then no, you need a larger number of blocks than that.

Let's suppose we have a bipartite graph with a small number $k$ of (labeled) vertices on one side and $n$ on the other. Each edge from one side to the other can be present or absent independently of the others, so there are $kn$ bits of information required to specify the whole graph.

On the other hand, suppose you could find an ordering with the neighbors of each vertex forming at most $b$ blocks. Then you could specify the same graph by listing the ordering of the big side of the bipartition (representable in $\le n\log_2 n$ bits of information) and the positions and lengths of the blocks for each of the $k$ vertices on the small side of the bipartition ($\le 2bk\log_2 n$ bits). So to have enough information to specify the whole graph we need $$ n\log_2 n+2bk\log_2 n\ge kn $$ or equivalently $$ b\ge\frac{kn-n\log_2 n}{2k\log_2 n} $$ Setting $k=2\log_2 n$ gives $b=\Omega(n/\log n)$, significantly greater than $\sqrt m=\Theta((n\log n)^{1/2})$.

$\endgroup$
4
  • $\begingroup$ Thanks a lot. I had my doubts on whether the solution exists. This was great help. $\endgroup$
    – sbzk
    Sep 10, 2015 at 8:15
  • $\begingroup$ Is this kind of information-theoretic argument used often in graph theory? (I don't recall seeing anything similar in standard undergrad textbooks.) $\endgroup$ Sep 15, 2015 at 15:38
  • 1
    $\begingroup$ I'm not sure. A more sophisticated information theory argument is used in entropy compression (en.wikipedia.org/wiki/Entropy_compression) which has some graph-theoretic applications (e.g. to nonrepetitive coloring). $\endgroup$ Sep 15, 2015 at 16:17
  • $\begingroup$ @DavidEppstein What if I want such a bound on number of such sequences with high probability and not exactly?. Does this example have some information theoretic aspects to restrict that as well? $\endgroup$
    – sbzk
    Jan 26, 2016 at 12:07

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.