On the complexity of tree embedding problems.

*(English)*Zbl 0768.68059An 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 M. R. Garey, R. L. Graham, D. S. Johnson and D. E. Knuth [SIAM J. Appl. Math. 34, 477-495 (1978; Zbl 0385.05048)]. J. B. Saxe [SIAM J. Algebraic Discrete Methods 1, 363-369 (1980; Zbl 0496.68032)], and E. M. Gurari and 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)] J.-W. Hong and 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 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 A. K. Chandra, D. C. Kozen and 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})\).

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 M. R. Garey, R. L. Graham, D. S. Johnson and D. E. Knuth [SIAM J. Appl. Math. 34, 477-495 (1978; Zbl 0385.05048)]. J. B. Saxe [SIAM J. Algebraic Discrete Methods 1, 363-369 (1980; Zbl 0496.68032)], and E. M. Gurari and 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)] J.-W. Hong and 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 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 A. K. Chandra, D. C. Kozen and 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})\).

##### MSC:

68Q25 | Analysis of algorithms and problem complexity |

68R10 | Graph theory (including graph drawing) in computer science |

05C10 | Planar graphs; geometric and topological aspects of graph theory |

94C15 | Applications of graph theory to circuits and networks |

05C05 | Trees |

PDF
BibTeX
XML
Cite

\textit{S. Simonson} and \textit{I. H. Sudborough}, Inf. Process. Lett. 44, No. 6, 323--328 (1992; Zbl 0768.68059)

Full Text:
DOI

##### References:

[1] | Aleliumas, R.; Rosenberg, A.L., On embedding rectangular grids in square grids, IEEE trans. comput., 31, 907-913, (1982) · Zbl 0488.94047 |

[2] | Bhatt, S.; Chung, F.; Leighton, T.; Rosenberg, A., Optimal simulations of tree machines, Proc. 27th IEEE symp. on foundations of computer science, 274-282, (1986) |

[3] | Chandra, A.K.; Kozen, D.C.; Stockmeyer, L.J., Alternation, J. ACM, 28, 114-131, (1981) · Zbl 0473.68043 |

[4] | Garey, M.R.; Graham, R.L.; Johnson, D.S.; Knuth, D.E., Complexity results for bandwidth minimization, SIAM J. appl. math., 34, 477-495, (1978) · Zbl 0385.05048 |

[5] | Gavril, F., Some NP-complete problems on graphs, Proc. 11th conf. on information sciences and systems, 91-95, (1977) |

[6] | Gurari, E.M.; Sudborough, I.H., Improved dynamic programming algorithms for bandwidth minimization and the MIN cut linear arrangement problem, J. algorithms, 5, 531-546, (1984) · Zbl 0556.68012 |

[7] | Hong, J.W.; Rosenberg, A.L., Graphs that are almost binary trees, SIAM J. comput., 11, 227-242, (1982) · Zbl 0486.05055 |

[8] | Hong, J.W.; Mehlhorn, K.; Rosenberg, A.L., Cost trade-offs in graph embeddings with applications, J. ACM, 30, 709-728, (1983) · Zbl 0627.68038 |

[9] | Lopez, A.D.; Law, H.F.S., A dense gate matrix layout method for MOS VLSI, IEEE trans. electronic devices, 27, 1671-1675, (1980) |

[10] | Rosenberg, A.L., Encoding data structures in trees, J. ACM, 26, 668-689, (1979) · Zbl 0423.68003 |

[11] | Rosenberg, A.L., Three dimensional VLSI: A case study, J. ACM, 30, 397-416, (1983) · Zbl 0624.94019 |

[12] | Saxe, J.B., Dynamic programming algorithms for recognizing small-bandwidth graphs in polynomial time, SIAM J. algebraic discrete methods, 1, 363-369, (1980) · Zbl 0496.68032 |

[13] | Simonson, S., Layout problems on graphs, () |

[14] | Simonson, S., A variation on the MIN cut linear arrangement problem, Math. systems theory, 20, 235-252, (1987) · Zbl 0643.68094 |

[15] | Simonson, S., Routing with critical paths, Inform. process. lett., 34, 13-19, (1990) · Zbl 0695.68045 |

[16] | Weinberger, A., Large scale integration of MOS complex logic: A layout method, IEEE J. solid state circuits, 2, 182-190, (1967) |

[17] | Yannakakis, M., A polynomial algorithm for the MIN cut linear arrangement of trees, J. ACM, 32, 950-988, (1985) · Zbl 0633.68063 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.