
Sequential and Parallel Algorithms for Embedding Problems on
Classes of Partial kTrees
Arvind Gupta? Naomi Nishimuray
Abstract
We present sequential and parallel algorithms for various embedding problems on bounded degree partial ktrees and kconnected partial ktrees; these include subgraph isomorphism and topological embedding, known to be NPcomplete for general partial ktrees. As well as contributing to our understanding of the types of graphs for which these problems are tractable, this paper introduces new methods for solving problems on graphs. In particular, we make use of a treelike representation of the graph (the treedecomposition of the graph) to apply techniques used to solve problems on trees to solve problems on more general classes of graphs.
1 Introduction
In devising sequential and parallel algorithms for subgraph isomorphism and topological embedding of bounded degree partial ktrees and kconnected partial ktrees, we make advances in two streams of research. One stream of research is the identification of problems for which a bound on the treewidth of a graph allows a more efficient solution than in the general case; a partial ktree is also known as a graph of bounded treewidth. The other stream is the identification of classes of graphs for which these embedding problems are tractable: the subgraph isomorphism problem, and consequently the more general problem of topological embedding, is known to be NPcomplete for general graphs [GJ79], and remains so even for graphs of bounded treewidth [Sys82]. The algorithms presented in this paper make use of techniques developed in each of these streams, and in addition introduce general methods for enabling the techniques in one stream to be applied to problems in the other.
As we will see in Section 2, graphs of bounded treewidth can be characterized as the class of partial ktrees, and include many natural classes of graphs, such as trees, outerplanar graphs, seriesparallel graphs, and Halin graphs. Of great interest for our algorithms is the fact that any graph in this class can be represented as a special type of tree, namely a treedecomposition, of bounded width. Such graphs have the property that there are small separators which break the
?School of Computing Science, Simon Fraser University, Burnaby, Canada, V5A 1S6. email: arvind@cs.sfu.ca,
FAX (604) 2913045. Research supported by the Natural Sciences and Engineering Research Council of Canada, the
Center for System Sciences and the Advanced Systems Institute.
yDepartment of Computer Science, University of Waterloo, Waterloo, Ontario, Canada, N2L 3G1. email:
nishi@plg.uwaterloo.ca, FAX (519) 8851208 Research supported by the Natural Sciences and Engineering Research
Council of Canada.