On the complexity of tree embedding problems (Q1209372)

An embedding of one graph \(G\) into another graph \(H\) is a one-to-one association of the vertices in \(G\), the source graph, with the vertices in \(H\), the host graph. Much research has appeared on problems of how to embed one graph into another while minimizing various costs. The cost depends on the particular motivating application. Such applications include VLSI layout and routing problems, communication costs in multiprocessor architectures, and efficient representations of data structures. The dilation cost of an embedding is the maximum distance in \(H\) between vertices that are adjacent in \(G\). The problem of minimizing dilation when \(H\) is a line (bandwidth minimization), is NP-complete even when \(G\) is a binary tree, see \textit{M. R. Garey}, \textit{R. L. Graham}, \textit{D. S. Johnson} and \textit{D. E. Knuth} [SIAM J. Appl. Math. 34, 477-495 (1978; Zbl 0385.05048)]. \textit{J. B. Saxe} [SIAM J. Algebraic Discrete Methods 1, 363-369 (1980; Zbl 0496.68032)], and \textit{E. M. Gurari} and \textit{I. H. Sudborough} [J. Algorithms 5, 531-546 (1984; Zbl 0556.68012)] gave polynomial time dynamic programming algorithms for this problem when the dilation cost \(k\) is fixed. In [SIAM J. Comp. 11, 227-242 (1982; Zbl 0486.05055)] \textit{J.-W. Hong} and \textit{A. L. Rosenberg} discuss the problem of embedding a graph into a complete binary tree, but they do not consider the general complexity of the problem. The congestion cost of an embedding is the maximum over all edges \(e\) in \(H\) of the number of edges in \(G\) that run through \(e\). An edge in \(G\) runs through an edge \(e\) in \(H\) if the unique path in \(H\) between the images of its endpoints contains \(e\). When \(H\) is a line this problem (min cut linear arrangement) is NP-complete in general, but is solvable in \(O(n\log n)\) time when \(G\) is a tree, see \textit{M. Yannakakis} [J. Assoc. Comput. Mach. 32, 950-988 (1985; Zbl 0633.68063)]. These results are in contrast with the ones for BMP. Minimizing dilation is harder than minimizing congestion cost, a distinction which also appears in our results, as we shall see. In this paper we prove that there exist polynomial time algorithms which determine whether a graph can be embedded into a complete binary tree with fixed dilation \(k\), or fixed congestion cost \(k\). Our main result is that both problems can be solved by an Alternating TM in \(O(\log n)\) space. Since \(\text{ASPACE}(\log n)=P\), see \textit{A. K. Chandra}, \textit{D. C. Kozen} and \textit{L. J. Stockmeyer} [J. Assoc. Comput. Mach. 28, 114-133 (1981; Zbl 0473.68043)], this implies that polynomial time algorithms exist for both problems. The details of these polynomial solution can be found in the first author's thesis [Layout problems in graphs (1986)] where it is shown that one can determine whether a graph can be embedded into a complete binary tree with fixed dilation \(k\), in time \(O(n^{2^ k})\); and fixed congestion cost \(k\), in time \(O(n^{(3k+5)/2})\).