page 1  (37 pages) 2

Sequential and Parallel Algorithms for Embedding Problems on

Classes of Partial k-Trees

Arvind Gupta? Naomi Nishimuray

Abstract

We present sequential and parallel algorithms for various embedding problems on bounded degree partial k-trees and k-connected partial k-trees; these include subgraph isomorphism and topological embedding, known to be NP-complete for general partial k-trees. 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 tree-like representation of the graph (the tree-decomposition 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 k-trees and k-connected partial k-trees, 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 k-tree is also known as a graph of bounded tree-width. 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 NP-complete for general graphs [GJ79], and remains so even for graphs of bounded tree-width [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 tree-width can be characterized as the class of partial k-trees, and include many natural classes of graphs, such as trees, outerplanar graphs, series-parallel 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 tree-decomposition, 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) 291-3045. 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) 885-1208 Research supported by the Natural Sciences and Engineering Research Council of Canada.