I was going through the classic text "Introduction to Automata Theory, Languages, and Computation" by Hofcroft, Ullman and Motwani where I came across the encoding of an instance of Kruskal's Mininum Weight Spanning Tree ($MWST$) problem so that it could be given as input to a Turing Machine. The encoding is as shown.

The Kruskal's problem could be couched as: "Given this graph $G$ and limit $W$ , does $G$ have a spanning tree of weight $W$ or less?"


Let us consider a possible code for the graphs and weight limits that could be the input to the $MWST$ problem. The code has five symbols, $0$, $1$, the left and right parentheses, and the comma.

  1. Assign integers $1$ through $m$ to the nodes.

  2. Begin the code with the value of $m$ in binary and the weight limit $W$ in binary, separated by a comma.

  3. If there is an edge between nodes $i$ and $j$ with weight $w$, place $(i, j, w)$ in the code. The integers $i$, $j$ , and $w$ are coded in binary. The order of $i$ and $j$ within an edge, and the order of the edges within the code are immaterial. Thus, one of the possible codes for the graph of Fig. with limit $W = 40$ is

$100, 101000(1, 10, 1111)(1, 11, 1010)(10, 11, 1100)(10, 100, 10100)(11, 100, 10010)$

If we represent inputs to the $MWST$ problem above, then an input of length $n$ can represent at most $O(n/\log n)$ edges. It is possible that $m$, the number of nodes, could be exponential in $n$, if there are very few edges. However, unless the number of edges, $e$, is at least $m-1$ the graph cannot be connected and therefore will have no $MWST$, regardless of its edges. Consequently, if the number of nodes is not at least some fraction of $n/\log n$, there is no need to run Kruskal's algorithm at all we simply say "no there is no spanning tree of that weight."

I do not understand the mathematics behind the lines which are given in bold. How are they bounding the number of edges by dividing the total input size $n$ by $\log n$ . If the number of edges are less then how can the number of node $m$ be exponential in $n$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.