ON SOME PROBLEMS ON K-TREES AND PARTIAL K-TREES By D A R K O SKORIN-KAPOV B. Sc The University of Zagreb, Yugoslavia, 1978 M . Sc. The University of Zagreb, Yugoslavia, 1983 A THESIS SUBMITTED IN PARTIAL F U L F I L L M E N T O F T H E REQUIREMENTS FOR T H E D E G R E E O F D O C T O R OF PHILOSOPHY in T H E F A C U L T Y OF G R A D U A T E STUDIES (Department of Commerce and Business Administration) We accept this thesis as conforming to the required standard T H E UNIVERSITY O F BRITISH COLUMBIA May 1989 © Darko Skorin-Kapov , 1989 In presenting this degree at the thesis in partial fulfilment of University of British Columbia, I agree freely available for reference copying of department publication this or and study. thesis for scholarly by of this his or her M f t C g ^ The University of British Columbia Vancouver, Canada Date Jt(UA DE-6 (2/88) 2 0 purposes , MSl that the may be It thesis for financial gain shall not C 0 H requirements I further agree representatives. permission. Department of the that advanced Library shall make it by the understood be an permission for extensive granted is for allowed that without head of my copying or my written ABSTRACT The objective of this thesis is to investigate some structural and algorithmic properties of ktrees and partial k-trees. A k-tree can be constructed from a k-complete graph by recursively adding a new vertex which is adjacent to all vertices of an existing k-complete subgraph. Partial k-trees are graphs embeddable in a k-tree with the same vertex set. They are natural generalizations of forests and series-parallel graphs which are the first two members of the hierarchy of partial k-trees. The many applications of k-trees and partial k-trees have motivated their study from both an algorithmic and a theoretical point of view. For example, k-trees arise in reliable communication network design problems (Farley (1981), Farley and Proskurowski (1982), Neufeld and Colbourn (1983), W a l d and Colbourn (1983), Colbourn and Proskurowski (1984)) and in the study of the complexity of certain type of queries in a relational data base system (Arnborg (1979)). Moreover, the class of k-trees is special in the sense that many problems, which are NP-complete for arbitrary graphs, are solvable in polynomial time when restricted to k-trees or partial k-trees (Arnborg and Proskurowski (1989)). In Chapter 2 of the thesis we analyze a fixed cost spanning forest ( F C S F ) problem, defined over a graph G, in which some customers require service that can be generated at some facilities' sites. Both the set of customers and facilities' sites are represented by nodes in G. There is a fixed cost for opening each facility and a cost for delivering the service from open facilities to the customers. Customers do not necessarily have to receive the service directly from an open facility, but possibly through other intermediate customers. We develop a linear time algorithm for solving the F C S F problem when the customers and potential facilities' sites are located on a series-parallel network or, equivalently, a partial 2-tree. We further analyze a related cost allocation problem, in which we seek a fair method for allocating the cost of providing the service to the customers. We formulate this cost allocation problem as a cooperative game and show that, in general, the core of this cooperative game may be empty. However, we provide a sufficient condition, which can be verified in polynomial time, for the nonemptiness of the core of this game. A k-tree can be reduced to the k-complete graph by sequentially removing k-degree vertices with completely connected neighbors. We use this reduction process to develop, in Chapter 3, efficient algorithms for several optimization problems on k-trees and partial k-trees. In particular, we develop a linear time algorithm to find shortest simple paths from a given vertex to all other vertices in a k-tree, we compute the diameter of a k-tree with equal edge lengths in linear time, and we construct an 0(n ) k+2 algorithm to solve the Simple Plant Location problem in an n-vertex partial k-tree. In Chapter 4 we present a new characterization of a k-path between two vertices u and v, in an equal weight k-tree G, by means of minimal k and k+1 cliques with respect to certain partial orders defined on the collections of all k and k+l cliques in a k-tree. We use it to develop an algorithm to decompose 0(n ) 2 a vertex set V of a k-tree G to a m i n i m u m number of components, such that for any pair of vertices i and j in the same component, the cable distance between i and j is bounded by a positive integer R. We also compute the k-cable diameter of a k-tree with equal edge lengths in linear time. In Chapter 5 we derive some separation properties of partial k-trees and use them to develop N C algorithms for recognizing partial 2-trees and 3-trees. Explicitly, we prove the existence of a kseparator in a partial k-tree graph and construct a linear time algorithm that finds such a separator in k-trees. This algorithm can be used to obtain a balanced binary decomposition of a k-tree in 0(n log n) time. We derive some other separation properties of partial k-trees and use them to construct a balanced decomposition of an embedding of a k-connected partial k-tree when k = 2 and 3. Finally, we construct N C algorithms for the recognition of a partial k-tree for k — 2 and 3, which run in 0(log n) time using, respectively, 0(n ) 2 3 in and 0 ( n ) processors. 4 Table of Contents ABSTRACT i i LIST OF FIGURES i» LIST OF TABLES vii ACKNOWLEDGEMENT viii I INTRODUCTION 1 1.1 Graph-Theoretic Definitions 2 1.2 Combinatorial Optimization Problems 7 1.3 Special Classes of Graphs 10 1.4 Recognition of k-Trees and Partial k-Trees : 1.5 Summary of the Results II III 13 17 FIXED COST SPANNING FOREST PROBLEM 19 2.1 Preliminaries 20 2.2 A Linear Time Algorithm 23 2.3 The Core of the FCSF Game on Series Parallel Graphs 30 ON SOME OPTIMIZATION PROBLEMS ON K-TREES AND PARTIAL K-TREES 36 3.1 Single Source Shortest Paths Problem in k-Trees 37 3.2 Diameter of a k-Tree 40 3.3 Simple Plant Location (SPL) Problem on Partial k-Trees 42 iv IV V K - C A B L E S A N D K - P A T H S IN K - T R E E S 47 4.1 A n R k-Cable Distance Decomposition Problem 47 4.2 k-Cable Diameter of a k-Tree 56 N C A L G O R I T H M S F O R RECOGNIZING P A R T I A L 2-TREES A N D 3-TREES 60 5.1 k-Separators 61 5.2 Some Separation Properties of Partial k-Trees 66 5.3 N C Algorithms for Recognition of Partial k-Trees for k = 2 and 3 69 5.4 N C Algorithm for Recognizing Partial 3-Trees 72 BIBLIOGRAPHY 80 v List of Figures Figure 1.1 T w o drawings of the same graph Figure 1.2 Partial 3-tree G 3 14 Figure 2.1 a: AnSPM b: A binary decomposition tree T of G Figure 22 21 G 21 32 G = (V, E) vi List of Tables Table 1.1 Upper bound of k for special classes of graphs x vii Acknowledgement I would like to express my sincere appreciation to the University of British Columbia and especially to the Faculty of Commerce and Business Administration for their hospitality and financial support given through Dean Earle D . McPhee Memorial Fellowship in Commerce and Business Administration, Leslie G . J . Wong Memorial Fellowship, University of British Columbia Graduate Fellowship and Graduate Travel Grant. M y sincere thanks go to the Division of Management Science for giving me the opportunity to be one of their P h D students. I am deeply indebted to Professor Daniel Granot, my supervisor, for his guidance, friendliness, many valuable suggestions and comments and financial support. I would also like to thank the other members of my dissertation committee Dr Richard Anstee, D r Frieda Granot and Dr Maurice Queyranne for their helpful suggestions. Finally, special thanks with love to my wife Jadranka and our daughters Lea and Nina for their patience and understanding. vm To my mother Marija Skorin and to my father Dinko Skorin Mojoj majci Mariji Skorin i mom ocu Dinku Skorinu ix Chapter I INTRODUCTION The objective of this thesis is to investigate some structural and algorithmic properties of ktrees and partial k-trees. k-trees are a generalization of trees, which can be viewed as 1-trees. They can be constructed from the completely connected (complete) graph on addition of vertices, each of which is connected with k edges to k vertices by the repeated k completely connected vertices. Partial k-trees are partial graphs of k-trees, i.e., graphs obtained by deleting edges from k-trees. They generalize the notion of forests and series-parallel graphs which are respectively, partial 1-trees and partial 2-trees. The study of the class of k-trees and their partial graphs was motivated by some practical questions concerning the reliability of communication networks in the presence of constrained lineand-site failures (Farley (1981) , Farley and Proskurowski (1982) , Neufeld and Colbourn (1983)) . Therein the vertices V represent sites or nodes in the network, and the edges 1 represent communication lines. Since lines are typically costly, communication between sites is usually not done directly but via other sites. A tree network is an obvious solution. However, for a tree network site and/or line failures are catastrophic. One way to overcome this failures is to increase the connectivity (Hakimi and T a m i n (1973)). Farley (1981) proposed isolated failure immune (IFI) networks which can survive site and line failures as long as they are isolated. He also showed that two-trees are m i n i m u m IFI networks, (k-fl)-trees are IfcFI networks in which at most k nonisolated failures are allowed. This, together with the fact that for a fixed k, k-trees have a number of edges which is linear in the size of a vertex set (and thus seem to be economical), makes k-trees attractive for use in the design of reliable communication networks. Studies of k-trees and partial k-trees were also motivated in view of their relevance in modelling the complexity of queries in data base systems. Indeed the evaluation of a certain class of conjuctive data base queries was shown to be equivalent to the embedding of an associated graph, obtained from the query syntax, into a (k— 1)tree, for a m i n i m u m k (Arnborg (1979)). Moreover, partial k-trees have arisen in some real world problems. A s an example, the reliability graph of a battle ship, constructed for weapons effect simulations, had several thousand vertices but was found to be a partial 4-tree (Arnborg (1978)). Further, many examples used in the engineering literature of communication networks are usually partial 4-trees and often series-parallel graphs. Finally, the class of k-trees is special in the sense that many problems which are NP-complete for arbitrary graphs, were shown to be solvable in polynomial time when restricted to this class of graphs; see, for example Arnborg and Proskurowski (1989). The introduction is organized as follows. In Section 1.1 we review some standard graphtheoretic definitions and in Section 1.2 we discuss several well known optimization problems on general graphs. In Section 1.3 we identify some special classes of graphs. In particular we present 2 some known characteristics of partial k-trees and a number of classes of graphs that are subclasses of partial k-trees. Many graph optimization problems, that are NP-hard on general graphs, can be solved in polynomial time when restricted to these special classes of graphs. Section 1.4 is an overview of the known results on the recognition of partial k-trees and their embeddings into k-trees. Finally in Section 1.5 we give a summary of results obtained in this thesis. 1.1 GRAPH-THEORETIC DEFINITIONS We present below some basic graph theory notation and definitions. For some recommended graph theory books the reader is referred to Harary (1969) and Berge (1985). A undirected graph or simply a graph G is defined to be a pair (V, E) , elements called vertices (or sometimes nodes) and unordered pairs of V, E where V is a family is a set x 2 (e , e ,• • •, e ) l called edges (or sometimes arcs). If an element more than once in the family { v , v , • • •, v } of 2 m e = (u,v) n of elements of of E appears E , it is called a multiple edge. A n edge of the form (v,v) is called a loop. Graphs without multiple edges are called simple. If the edges are ordered pairs, then D = (V, E) , is called a directed graph ( or a digraph). In a directed graph D = (V,E) the vertices u and v are called the tail and the head of the directed edge (u,v) , respectively. (Note that very often for both undirected and directed graphs an edge from a vertex u to a vertex v is denoted by (u,v) , even though {u,v} would be more appropriate for undirected graphs. The concepts of a multiple arc, a simple graph and a loop for directed graphs are analogous to those for undirected graphs. 3 Fig. 1.1 Two drawings of the same graph We shall say that an edge («,v) connects the vertices « and v. The vertices u and v are adjacent if there is an edge connecting « and v. The edge («,t>) is said to be incident to the vertices u and v, and conversely. The vertices « and v are called the ends of the edge (u,v) . Commonly, graphs are represented by a drawing i n which vertices are represented by small circles and edges are lines connecting them (see Fig. 1.1). Some representations of graphs that are appropriate for computer implementation are an edge list, an incidence matrix and an adjacency matrix. A n edge list simply contains an entry for each edge (u,v) . Representation by edge lists is the most appropriate for the algorithms studied i n the thesis. In the case of the graph i n F i g 1.1 such a list contains (1,2) , (1,3) , (1,4) , (2,3) , (2,4) , (3,4) . Each- row of a vertex-edge incidence matrix is identified with a vertex and each column with an edge. If the vertices are numbered by the index 4 i and edges by the index k the incidence matrix of an undirected graph G , A = (a ) ik is defined as follows : 1 if vertex i is incident to edge k 0 otherwise In the case of a directed graph D the edge-vertex incidence matrix A — (a ) ik is defined as follows: ( The adjacency matrix B = (6,j) and columns indexed by connecting +1 if i is a head of a directed edge k — 1 if i is a tail of a directed edge k 0 otherwise of an undirected graph G= (V, E) V and defined as follows : (6 ) = /, tJ i and j . So is a matrix with both rows where / is the number of edges G is simple if and only if its adjacency matrix is a {0,1}—matrix. In the case of a directed simple graph D the adjacency matrix B = (6- -) is defined as follows : t 1 if there is a directed edge with a head j and a tail i 0 otherwise For any vertex v £ V, the neighborhood of v in a graph vertices adjacent to v . The degree of a vertex of a directed graph W D = (V, E) is a set of vertices such that leave V \ W. If W C V, the set of directed edges in v is the cardinality of its neighborhood. In the case we say that the directed edge (u,v) v £ W and then 6~(W) E G is defined as the set of all leaving w £ W, then enters v and leaves (v,w) is said to enter denotes the set of edges in E entering W. We let 5 6~{v) and 6 (v) + stand for u . If W and to W and 6 ({x/}) - 6 (W) + and 6 ({v}) and are called in-degree of v and outdegree of v , respectively. + A path in a graph of the form G = (V,E) ( v , t , v , e , 0 x are edges such that x e v_ t x 0 t connecting v t t t « 0 1 = and v 0 , e , v ) , where v , , u,) € .E , for = 0 are vertices and t t. 1, 2 is a sequence t W e refer to v , 0 e , ••• , e x t t> as the t Pv v • A path is simple if all its vertices and edges are distimct. If v = v endpoints of the path then the path { 2 Pv v (or p(v ,v )) , 0 t 0 t Pv v is called a cycle. A cycle without repeated edges or vertices (except for the 0 t endpoints) is called a simple cycle. A directed path from v Q to v in a digraph D = (V, E) is t defined similarly as in the undirected case except that in this case the edges in the path are directed. A graph is connected if any two vertices in it are connected by a path. Connectedness by paths induces an equivalence relation on the vertices. Its classes are called the connected components of the graph. A digraph D is called weakly connected if its underlying undirected graph is connected. D is strongly connected if there is a directed path in p uv for any two vertices u and v D. A graph G = (V',E') 1 is a subgraph of G = (V,E) if V is the family of all edges of G which have both ends in V , then and denoted by A graph G'(V') 1 C V and Ef C E. If 1 is said to be induced by G G is an embedding of the graph G 1 if it can be obtained from G 1 V 1 by addition of some G = (V, E) is a set of pairwise adjacent vertices of G . If a graph K is a clique having p vertices we call it the complete graph on p vertices and denote it by K S 1 . A partial graph of G contains all its vertices and a subset of its edges. edges. A clique in the graph subset E 5 of V is a separator of a graph p G = (V, E) if the subgraph G( V \ S) induced by has two or more connected components. A graph G = (V, E) V \ is called k-connected (or sometimes k-point-connected) if the cardinality of any minimal separator of G is at least k . 6 . A A contraction of an edge from in G = (V, E) E and identifying the vertices u and v . A graph can be obtained from results in a graph H e = (u,v) is obtained by removing e = G is contractible to a graph (?' if G ' G by a sequence of edge contractions in G \ e with the same vertex set as is a minor of a graph G. Edge extraction of G and the edge family G if it can be obtained from (u,v) e in G E \ {e} . A graph G by a finite number of contractions and edge extraction operations. Let G x = (^II-^I) if there exist mappings from V t into a n ( i & and G = (V , E ) 2 0 2 with 2 be any two graphs. being from , ti^)) and !^((t) , w )) 2 2 is homeomorphic to x 2 x 0(w) , and no two paths 2 E , onto a set of paths of G V , such that for each edge (v,w) G E , the path 2 G s n a r e a and G x 0 \P((v,w)) has ends <9(a) and vertex except possibly an end of paths. Let $ = {5j , S , • • •, S } 2 n S. The intersection graph of f be a family of distinct nonempty subsets of S whose union is is a graph whose vertices are identified with sets in f, with S f and Sj adjacent whenever t ^ j and 5,- D Sj ^ 0. In general, graphs and directed graphs are very useful in representing systems or structures that may be considered as set of elements, certain pairs of which are related in a specific way. However, in many applications arising in business, engineering, biological and social sciences, graphs and digraphs are not sufficient to adequately represent the system or structure under study. In such cases, usually numerical values are attached to the vertices and/or edges to represent construction cost, flow capacities, probabilities of destruction and so on, see, for example Ford and Fulkerson (1962). In general, any graph to which such additional structure has been added is called network. For example, a network G = (V, E) is a weighted graph such that each edge 7 e 6 E has a 'length' (weight) weights. Distance w(e) . For any u , v £ V, between two vertices the length of the path p(u,v) is the sum of its edge « and a is defined as the length of the shortest simple path p(u,v) . 1.2 COMBINATORIAL OPTIMIZATION PROBLEMS A n instance of an optimization problem is a pair points and (F,c) , where F is the set of feasible c is the cost function, c : F —• R . The problem is to find an f £ F for which c{J) < c(g) for all g £ F. 1 Such a point / is called an optimal solution to the given instance or, for short, an optimal solution. A n optimization problem is a set J of instances of an optimization problem. For example an instance of a minimum spanning tree problem has a given integer n > 0 and n x n symmetric distance matrix (d j) . The problem is to find a spanning tree, (V, E) on n t vertices that has minimal total edge length. (By a spanning tree we mean an undirected graph (V, E) with that is connected and has no cycles.) For this example V = {1,-••,»}} and c:(V,E)^ £ ( l | i ) e £ d {j F = | a l l spanning trees ( V, E) , . One can naturally divide optimization problems into continuous optimization problems and discrete (combinatorial) optimization problems. In combinatorial problems, we usually look for an object from a finite or possibly infinite set. The challenge in combinatorial optimization is to develop algorithms for which the number of elementary computational steps used to obtain an optimal solution of an instance of the problem is acceptably small. Complexity theory categorizes problems in terms of the form of mathematical functions expressing amounts of computation as a 8 function of instance size. If, for example, some algorithm uses a number of elementary operations that can be expressed as third order polynomial of the problem size, n , we say that the algorithm is order the n , or simply 0(n ) 3 3 . Generally accepted measure of efficient performance of an algorithm in realm of combinatorial optimization is that of 'polynomial boundness'. A n algorithm is considered 'good' if the required number of elementary computational steps to solve an instance of the problem is bounded by a polynomial in the size of the problem. For a given optimization problem a closely related recognition version of the problem can be defined. Given an instance (F,c) of an optimization problem and an integer L , is there a feasible solution / G F such that L . The class of recognition problems that can be solved by a polynomial time algorithm P . A recognition problem certificate for A is in the class N P if for a yes Clearly P is contained in outstanding open problem whether P = N P . It is strongly suspected that B be two recognition problems. It is said that there exists a polynomial time algorithm cost a (hypothetical) algorithm reduction of A problem x A for A P ^ N P . Let A and B i f and only if that uses several times as a subroutine at unit B . The algorithm A and which can be N P . However it is an reduces in polynomial time to .A is called a polynomial-time polynomially transforms to another recognition x , we can construct a string is a yes instance of A x if and only if y y in polynomial time (in the size of is a yes instance of B . A recognition A € N P is said to be NP-complete if all other problems in N P polynomially transform to A . Problem A to -4. for B . A recognition problem B if, given any string x) such that problem to S A is called instance x of A , there exists a x , whose length is bounded by a polynomial in the size of checked for validity in polynomial time. c(f) < is called NP-hard if it can be shown that all problems in N P polynomially reduce but it is unknown whether A belongs to N P . Problem that is NP-hard is as hard as any problem in N P . For precise definitions of complexity of an algorithm, P , 9 N P , NP-completeness and NP-hardness, see, for example, Papadimitriou and Steiglitz (1982) and Garey and Johnson (1979). It has been shown that many NP-hard graph problems become solvable in polynomial time when restricted to special structure graphs. Such special graphs are presented in the next section. Below we list several well-known NP-hard problems (Garey and Johnson (1979) to which we further refer in the sequel. Shortest Path Problem (allowing negative cycles) G = (V, E) € R. 1 is a weighted graph, such that each edge e £ E has a 'length' (weight) For a given pair of vertices u , v £ V find the length of a shortest simple path w(e) p(u,v). Longest Path Let G — (V, E) be a weighted graph, such that for each edge e £ E, u , v £ V find the longest simple path w(e) £ R . For and a set of vertices D , DC + p(u,v). Steiner Tree Problem Given a connected undirected weighted graph G = ( V, E) V ; find a tree T in G , whose vertex set contains D with a m i n i m u m total edge-weight. M a x i m u m Independent Set For a given graph independent set in a graph edge (u,v) G — (V,E) G = (V, E) find the maximum size of an independent set. ( A n is a subset is not in E.) 10 V 1 C V such that for all u , v £ V , the 1 M i n i m u m Dominating Set For a given graph G = (V, E) compute the minimum size of a dominating set. ( A set D C V is dominating in G if every vertex in V is either in D or it is adjacent to a vertex in D.) Chromatic Number For a given graph G = (V, E) compute the size of a smallest set L of colors such that V can be colored with elements from L in such a way that no two adjacent vertices have the same color. Hamiltonian cycle For a given graph G = (V, E) , decide whether there exist a simple cycle passing through every vertex. Simple Plant Location Problem in a Graph Let each vertex function G = (V, E) be an undirected weighted graph with v £ V associate a fixed cost , c , v w(e) > 0 to open a facility , for all e € E. With and a transportation cost g ( • ) which is a nondecreasing function of its argument. Each vertex is viewed as both a v potential facility site as well as a customer. Find a subset of vertices F, F C V, 11 that minimizes : 1.3 SPECIAL CLASSES OF GRAPHS W e describe bellow several classes of graphs which were extensively studied in the literature and some of which can be viewed as special cases of the class of partial k-tree graphs. Many optimization problems which are NP-hard for general graphs were shown to be polynomially solvable when restricted to these classes of graphs. Trees are possibly the simplest class of graphs. Trees are undirected, connected graphs without cycles. Forests are undirected graphs that are acyclic but not necessarily connected. G = (V, E) is an almost tree with a parameter smaller than or equal to spanning tree T that are not in Let G, in each biconnected component of i f and only if for some G there are at most k edges of G T. G = (V, E) be a graph, with n . 1= A linear ordering of G is a bijective V —• { 1 ,• • • , n } . A linear ordering / of G is said to have bandwidth k if k = mapping / : max of k ' ^l f( ) u ut £ ~ f( ) v I • The bandwidth k of G, denoted by bandwidth(G), is the minimum bandwidth of a linear ordering / over all possible orderings of G . Series-Parallel graphs are undirected graphs that can be constructed recursively from its edges by series and parallel compositions. (Definitions of series and parallel compositions are given in chapter II). Planar graphs are those graphs that do not contain K 5 or K 3j3 homeomorphs. (They can be drawn in the plane in such a way that no two lines representing edges intersect except at a common endpoint.) Outerplanar homemorphic to K 4 or K 2f3 (or 1-outerplanar) graphs are graphs that do not contain graph • (Or equivalently they are planar graphs that can be drawn in the plane in such a way that all their vertices are on the same face.) For 12 k > 2, a graph is k- outerplanar i f and only if it is planar and it has a planar embedding such that if all vertices on the exterior face and all adjacent edges are deleted, then the connected components of the remaining graph are all (k— l)-outerplanar. A graph G = (V, E) is a Halin graph if it can be obtained by embedding a tree without vertices of degree 2 in the plane and connecting its leaves by a cycle that crosses none of its edges. G — (V, E) is a chordal graph if and only if every cycle with length exceeding three has an edge joining two non-consecutive vertices in the cycle. k-trees can be defined as follows. The fc-clique is a k-tree, and a k-tree of more than k vertices can be constructed by adding a new vertex and new edges connecting it to all vertices of some fc-clique of a smaller k-tree. Partial k-trees are partial graphs of k-trees. Many NP-complete problems were solved in polynomial time on trees and forests, using mostly dynamic programming approaches, see, for example, Johnson (1985). Linear time algorithms for finding maximum independent set and minimum dominating set on almost k-trees were developed in Corneil and Perl (1984) and Coppersmith and Vishkin (1985). The technique used therein is to subdivide the problem into a collection of subproblems on the biconnected components, and for each of these to use a tree algorithm as a subroutine. The number of such calls vary, depending on the way how the excess edge influence the solution. Monien and Sudborough (1981) use a dynamic programming approach to show that a number of problems on bandwidth restricted graphs have polynomial solutions. Most of the NP-complete problems remain NP-complete when restricted to planar graphs (Johnson (1985)). However, many NP-complete problems can be solved in polynomial time on series parallel graphs. Indeed, Takamizawa et. al. (1982) provide a general approach to characterize a family of NP-complete problems, that are solvable in linear time on two 13 terminal series-parallel graphs. They consider graph properties defined by means of a finite set of graphs which are forbidden configurations in graphs with these properties. Among other problems they solve the maximum independent vertex set problem, the m i n i m u m dominating set problem and the Steiner tree problem. In Bern et. al. (1985) a different general approach was taken for solving combinatorial optimization problems. Namely a general methodology for constructing linear time algorithms is developed therein for graphs which are defined by certain rules of composition. Their approach is applicable for a wide range of problems on series-parallel graphs, outerplanar graphs, Halin graphs, and bandwidth-limited graphs. Chordal graphs can be characterized in terms of 'perfect elimination ordering'. That is, a graph G — (V,E) and only if there exist an ordering of the vertex set induced subgraph G( V \ U { Vj : j = 1, i — 1}) V , say of with | V\ = n is a chordal graph if v , v , • • •, v , such that in the vertex x 2 G, i > 1, v n and its adjacent nodes t therein form a clique (Golumbic (1980)). A perfect elimination order was used to develop polynomial algorithms for many graph problems that are NP-complete for general inputs (Johnson (1985)). Note that k-trees are chordal graphs ( although not all chordal graphs are k-trees). Arnborg and Proskurowski (1989) have analyzed the complexity of NP-complete problems on partial k-trees, and developed linear time algorithms for the following problems: vertex cover, independent set, dominating set, graph k-colorability, Hamiltonian cycle and network reliability. They have shown that partial k-trees are ^-decomposable graphs. (A graph and only if either it has at most k + 1 vertices, or there is a separator G is ^-decomposable if S of G with at most k vertices such that each of the connected components of G \ S augmented by S with completely connected vertices is ^-decomposable.) Since the component partial k-trees interact only through the separators, solutions to subproblems on the component partial k-trees may be combined to form a solution for the given partial k-tree. Using the ^-decomposable property of partial k-trees Arnborg 14 and Proskurowski (1989) and Corneil and Keil (1987) developed a general algorithm paradigm to solve efficiently some difficult problems on graphs with bounded decomposability. We note that since k-trees are chordal graphs these results are related to those obtained by G a v r i l (1972) in which polynomial algorithms were developed for solving the problems of finding m a x i m u m independent set, m i n i m u m coloring, maximum clique and m i n i m u m clique covering for chordal graphs. Observe that the class of partial k-trees can be viewed as a unifying framework for some of the special graphs discussed above. Indeed, every graph (in the worst case G — ( V , E) is a partial k-tree for some k k = \V\ — 1 ). Moreover, with many well known classes of graphs one can associate an upper bound, fcj , such that these classes can be viewed as partial k-trees for some not exceeding k . r Table 1.1 provides such an upper bound k^ for several classes of graphs. (A more detailed overview of these results is presented in Bodlaender (1986). Class of graphs Trees, forests 1 Almost trees with parameter k k + Graphs with bandwidth at most k Jb Series parallel graphs 2 Outerplanar graphs 2 Halin graphs 5 k-outerplanar graphs 3* chordal graphs with max. clique size k Table 1.1 Upper bound of k 15 t k - * for special classes of graphs 1 1 1.4 RECOGNITION OF k-TREES AND PARTIAL k-TREES It is easy to check in linear time whether a given graph G is a k-tree by simply removing successively k-degree vertices (every k-tree has at least two such vertices) and its adjacent edges until the graph G becomes empty. Thus if we can reduce a graph G to an empty graph by such an elimination process i t is a k-tree. However the recognition of partial k-trees is much more difficult and the characterization of partial k-trees as decomposable graphs (see Section 1.3) does not seem to provide an efficient algorithm for the recognition of this class of graphs. The separator property is lost in partial k-trees. Namely, in a partial k-tree we may find a 'small' separator which cannot be extended to a k-clique in an embedding of this partial k-tree into a k-tree. For example, if we extend the 3-separator 5 = {s^ , s graph which contains K 5 2 ,s } 3 of the partial 3-tree G in F i g 1.2 to a 3-clique, we obtain a as a subgraph and thus is not a partial 3-tree. Fig 1.2 Partial 3-tree 16 G Therefore, since the various polynomial algorithms which solve NP-hard optimization problems on partial k-trees (like vertex cover, chromatic number or graph reliability) require a suitable embedding of the partial k-tree into a k-tree, efforts are devoted to recognize efficiently partial k-trees and find their embeddings into k-trees. Actually, there are two types of recognition problems. The first one is of finding an embedding, of a partial k-tree into a k-tree and the second problem is of finding the minimal value of k, for which the given graph is a partial k-tree. This second recognition problem is important since the above algorithms, though linear in the size of the input, are exponential in k. For k = 2 and 3 , the recognition and embedding problem has been solved by finding a set of reductions on graphs such that any graph can be reduced to the empty graph if and only if it is a partial k-tree (see W a l d and Colbourn (1983) for and Proskurowski (1986) for k = 3 ). This set of reductions yield 0(n) k = 2 and Arnborg and O(nlogn) time algorithms for the recognition of partial 2-trees and partial 3-trees, respectively. However, already for the case of k = 4 there is no easy known generalization of these methods. Arnborg and Proskurowski (1985) presented an incomplete set of reduction rules for partial k-trees which can be used i n a heuristic decomposition method. They experimented with these heuristics, and for small values of k (up to 7) most of the graphs which they tested were correctly recognized. Arnborg et. al. (1987) have shown that the problem of finding the smallest number k such that a given graph is a partial k-tree is NP-complete. However, they also presented therein an 0(n ) k+2 time algorithm for the recognition of a partial k-tree when k is fixed. Present research is directed towards a better polynomial time recognition algorithm. Robertson and Seymour (1986) have proved that there exists an 0(n ) 2 algorithm to recognize partial k-trees. However their result is not constructive ; only the existence of such an algorithm is demonstrated and no method is provided to construct it. 17 W i t h the increasing use of highly parallel computers, it has become desirable to identify optimization problems that can be solved fast in parallel. In particular, there has been a considerable interest in problems which have parallel algorithms running in time bounded by a polynomial in the logarithm of the size of the input (i.e. , in poly-log time) and using a number of processors polynomial in the input size. Such a problem belong to the class N C (Pippenger (1979)). Some of the reasons for this interest in the class N C are: (i) N C C P . N C algorithms are more efficient compared to their sequential versions. Further they make use of a 'reasonable' amount of hardware, namely, the processors. (ii) The class N C is 'robust' under reasonable changes in the underlying machine models of parallel computation. A very basic issue in parallel complexity theory is to find the most appropriate model of a computer. Different models could lead to different computations and the number of steps executed by the same algorithm would be different, depending on the model of machine considered. The basic differences between various models are concerned with how they deal with read and write conflicts of memory access. The widely excepted model of a R A M (Random Access Machine) consists of a readonly input tape, a write-only output tape, a program and a memory (Aho et.al. (1974)). Fortune and Wyllie (1978) proposed the model P R A M (Parallel Random Access Machine) for parallel computations, which is an extension of the R A M model. In a P R A M model simultaneous reads are allowed, while simultaneous writes are not. Other models of shared memory parallel machines have been proposed i n the literature, like C R C W (Concurrent Read Concurrrent Write) P R A M (Vishkin (1983)) in which all the processors have access to a common memory and run synchronously and both simultaneous reading as well as writing on common memory locations are allowed. The N C algorithms that we consider in this thesis assume C R C W P R A M model. 18 Edenbrandt (1985) constructed a parallel algorithm for the recognition of chordal graphs that requires processors and takes improved his processor bound to 0(n ) 4 O(logn) time. Chandrasekharan and Iyengar (1986) . Tseng (1987) constructed an algorithm that recognizes whether a given 2-connected graph is series-parallel in 0(log n) 3 time using 0(n ) processors. 4 Bodlaender (1988) has constructed an algorithm for the recognition of graphs that have a tree width less than k (or, equivalently are partial k-trees), which runs in O(logn) time and uses 0(n ) 3k+4 processors. Thus, parallelism has decreased the running time but is quite inefficient in the use of processors. 1.5 SUMMARY OF THE RESULTS We provide bellow a summary of the results obtained in the thesis. In chapter II, we analyze the fixed cost spanning forest ( F C S F ) problem , defined over a network set of communities M, M C V. G = (V, E) in which the D , D C V, require service that can be generated at a set of facilities' sites There is a fixed cost for opening each facility and a cost for delivering the service from open facilities to the communities. A n y community receiving the service from an open facility can deliver it to adjacent communities. We develop a linear time algorithm for solving the F C S F problem when the underlying network G has a series parallel structure. We further analyze a related cost allocation problem, in which we seek a fair method for allocating the cost of providing the service to the customers. We formulate this cost allocation problem as a cooperative game and show that, in general, the core of this cooperative game may be empty. However, we provide a sufficient condition, which can be verified in polynomial time, for the nonemptiness of the core of 19 this game. It is well known that a k-tree can be reduced to the k-complete graph by sequentially removing fc-degree vertices with completely connected neighbors. In the third chapter we use this reduction process to develop efficient algorithms for several optimization problems on k-trees and partial k-trees. The complexity of algorithms developed on k-trees and partial k-trees the thesis expressed in terms of number of vertices and k is is assumed throughout to be a fixed constant. Observe that the number of edges of a k-tree is linear in the number of vertices for a fixed k . We develop a linear time algorithm to find shortest simple paths from a given vertex to all other vertices in a k-tree, we compute the diameter (the longest path) and the vertex center of a k-tree with equal edge lengths in linear time and we construct an 0(n ) k+2 algorithm to solve the Simple Plant Location problem in an n-vertex partial k-tree. In chapter I V we study the notion of k-cable and k-path in a k-tree. The k-cable , C(u,v) , is a collection of k vertex-disjoint paths between vertices u and ti in a ^-connected graph. We define the length of the k-cable , C(u,v) , as the sum of the lengths of the the k-cable distance between two vertices these two vertices. A k-path subgraphs KP = such that T { vertices u and u and 2 2 3 n k + 1 complete , Qn > , starting and ending with a k-clique and contains exactly two of the distinct k-cliques v in a k-tree and v is the length of the shortest k-cable between is an alternating sequence, KP , of distinct k and < Q , T , Q >T , • • • , T x k paths in C(u,v) Qi_i and Q . t A k-path between G is induced by all the minimal k-separators of u and D in G. We provide a new characterization of a k-path between two vertices u and v , in an equal weight k-tree G , in terms of minimal k and k + 1 cliques with respect to certain partial orders defined on the collections of all k and k + 1 cliques in 20 G . Further, for an equal weight k-tree G = ( V , E) and a positive integer vertex set R , R > 2k — 1 , we develop an 0(n ) 2 V into a m i n i m u m number of components, V , V , 1 vertices i and j , i ^ j € V* and < = 1 , • • • , / , algorithm to decompose the ••• , V\ such that for any pair of 2 the cable distance between i and j does not exceed R . W e also develop in chapter I V an algorithm to compute the k-cable diameter of a k-tree with equal edge lengths in linear time. Finally in chapter V we introduce the notion of a k-separator G = (V, E) . A k-separator is a set of vertices S, into sets V a vertex in x and V 1 V 2 satisfying : with a vertex in (k > 2) of an n-vertex graph \S\ = k , which induces a partition of V\ S (i) | V.-1 < J^J n , i — 1 , 2 , and (ii) no edge in E connects V • We prove the existence of a k-separator for partial k-trees 2 and construct a linear time algorithm for generating such a separator in k-trees. This algorithm can be used to construct a balanced binary decomposition tree of a k-tree in O(nlogn) time. We further derive some other separation properties of partial k-trees which are used to construct a balanced decomposition of an embedding of a k-connected partial k-tree into a k-tree when k = 2 , 3 . Finally , we develop parallel algorithms for the recognition of partial k-trees when £ = 2 , 3 . These algorithms require 0(log n) 2 time and use, respectively, 0(n ) 3 21 and 0(n ) 4 processors. Chapter II FIXED COST SPANNING FOREST PROBLEM Let edges E. G = (V, E) The subset potential facilities' sites. be a connected undirected network with a set of vertices D , D C V , is a set of communities and M , V and a set of M C V , is a set of Open facilities provide service which is required by the communities, and any community receiving the service can in turn deliver it to adjacent communities. Each community in D is required to be connected, perhaps through other communities, to an open facility. There is a cost, £ E, i f edge in D c > 0 , for opening facility t i G M and a cost c((i,j)) = • > 0 , is used to deliver service. The objective is to provide service to the communities at a m i n i m u m cost. We will refer to the above optimization problem as the Fixed Cost Spanning Forest ( F C S F ) problem. The F C S F problem is equivalent to the Steiner Tree problem on an augmented network derived from G by adding a new vertex, denoted by G 1 o , and joining it to the set of all potential facilities' sites M . The cost of any newly added edge (O,J) , i <E M , in G 1 is c oi = c- . Clearly, ( an optimal solution to the F C S F problem can be produced by finding a minimum cost Steiner tree in G 1 whose vertex set contains connected undirected weighted graph D 1 = D U { o } . For the other direction suppose that a G = (V,E) 22 and a set of vertices D , D C V are given and we want to find a tree T in G , whose vertex set contains D with a minimum total edge weight. To transform this problem to F C S F problem we identify set choose an arbitrary vertex in D D with the set of communities and we and pronounce it a facility site at which a facility can be established at zero cost. Thus, since the Steiner Tree problem is known to be NP-hard (Garey and Johnson (1979)), in general, so is our F C S F problem. When the underlying network G — (V,E) is a tree, the augmented network G 1 = (V \E') is a series parallel graph without loops or parallel edges or, equivalently, it is a partial two1 tree (Wald and Colbourn (1983)). Therefore, since there exist linear time algorithms for solving the Steiner Tree problem on partial-two trees (see, e.g., W a l d and Colbourn (1983), Prodon et al. (1985), Rardin et al. (1982), Takamizawa et al. (1982)) and Cornuejols et. al. (1985) one can employ these algorithms to solve the F C S F problem on a tree network. The main purpose of this chapter is to develop a linear time algorithm for solving the F C S F problem when the network G = (V, E) is restricted to have a series parallel structure. We further examine a cost allocation problem associated with the F C S F problem, in which one seeks a fair method for allocating the cost of providing the service among the communities. The rest of the chapter is organized as follows. In Section 2.1 we review standard definitions regarding series-parallel graphs, and in Section 2.2 we develop a linear time algorithm for solving the F C S F problem on a series parallel graph. In Section 2.3 we examine a cost allocation problem associated with the F C S F problem. We formulate this cost allocation problem as a cooperative game and show that, in general, the core of this game may be empty when G is a series parallel network. Nevertheless, we provide a sufficient condition for the nonemptiness of the core of this game, which can be verified in polynomial time. 23 2.1 PRELIMINARIES This section reviews several standard graph-theoretic concepts to be employed in the sequel. Series-parallel multigraph ( S P M ) is associated with two vertices called terminals and can be constructed recursively as. follows: A single edge is a S P M ; its end vertices are the two terminals. Further, if Q x and Q 2 are S P M s with terminals i(Qi) , j(Qi) and i(Q ) > HQ2) 1 respectively, 2 so are the multigraphs obtained by each of the following compositions. Series composition Identify a terminal of Q , say j(Qi) , with a terminal of Q , say x of the new multigraph are i(Qi) i(Q ) • The terminals 2 2 and j(Q ) • 2 Parallel composition Identify one terminal of Q , say l second terminal of Q , j(Qi) , with j(Q )1 2 i(Qi) , with one terminal of Q 2 , say i(Q2) , and the The terminals of the new multigraph are the two vertices where the identifications occur. The above recursive construction of a S P M G can be represented by a binary decomposition tree (see, e.g., Valdes et al. (1982)). This is a rooted binary tree T i n which each vertex Q corresponds to some series-parallel submultigraph of G , denoted by G( Q) , obtained as follows. Each vertex of T that has degree one represents a distinct edge of G . If Q is not a degree one vertex, then it is either of a series (S) or parallel (P) type. If Q is a parent of Q Q by the respective series or 2 , then G(Q) is submultigraph obtained from parallel composition. In particular, if Q G(Q ) 1 is the root of and G(Q ) T , G(Q) 2 1 is the multigraph G. and The construction of a binary decomposition tree of a given S P M can be done in linear time, see, e.g., 24 Valdes et al. (1982). Figure 2.1 below illustrates a binary decomposition tree of an S P M . Figure 2.1a: A n S P M G Figure 2.1b: A binary decomposition tree T of G A n optimal solution , X* , to the F C S F problem specifies the set of facilities Af, that are opened at the optimum. Each open facility set of communities through a connected network » , » G Af*, is providing the service to a T,* = (V,*,£,*) , which can be assumed to be a tree. The optimal value of the F C S F problem, associated with X* , is given by : E <+ E c ieAf* E ,*c ieAf* 0',*)e£- 25 Af*, Af* C The Directed Steiner Tree problem, which is closely related to our F C S F problem, is defined with respect to a directed weighted graph G = (V,E) subset of vertices D C V , find a directed tree . Namely, given a vertex o 6 T in G , rooted away from vertex V and a o and whose vertex set contains D , such that the total edge-weight of T is m i n i m u m . 2.2 A LINEAR TIME ALGORITHM W e develop in this section a linear time algorithm for solving the F C S F problem on an S P M G = (V, E) with a set of communities D , D C V , and a set of facilities' sites simplicity of presentation, we assume that G does not contain parallel edges. The algorithm starts by constructing a binary decomposition tree , T , of the underlying S P graph of Q , except for those corresponding to the leaves of parallel composition of two subgraphs correspond to vertices Q and 1 Q 2 q , q , q , respectively, in 1 2 successor vertices of q in T , and Starting from the leaves of and T G . Every vertex q Q — (VQ,EQ) of G , with terminals T designates a series parallel subgraph Each such subgraph M , M C V. For Q 2 i(Q) and j(Q) . T , is either a series or of G . That is, if the subgraphs T , then q and l q 2 Q , Q 1 Q l 2 are the two immediate are said to be the sons of Q . and proceeding towards its root, for each vertex q of the algorithm solves certain special cases of the F C S F problem in the corresponding subgraph The solution of these special cases in , Q T Q. Q is based on solutions of identical cases in the sons of Q , and Q , whose composition created Q , and which were previously obtained by the algorithm. 2 A t the final stage, when graph q is the root of T, the corresponding subgraph Q coincides with our SP G and an optimal solution for the F C S F on G is at hand. The special instances of the F C S F problem that we need to solve are derived from some 26 restrictions we impose on the terminals of the S P subgraphs we encounter. Explicitly, for each subgraph Q associated with a vertex q of the binary decomposition tree T , we compute the following optimal values : II: f(Q,u ,0), Q IV: V: /(Q,0,i(g)), /(Q,i(Q),0) , VIII: VII : f(Q, UQ ,j(Q)) , X: f(Q,i(Q),i(Q)) , XI: f(QJ,v ), III: Q VI : f(Q,u Q f(Q,i(Q),v ) , Q IX: ,v ) Q , f(Q,i(Q),j(Q)) , f(Q,j(Q),j(Q)) A l l the above eleven cases can be viewed as combinations of the following three types of optimal values and their symmetric counterparts : /(Q,0, . ) -optimal value of a F C S F problem in Q when there are no restrictions on the terminal problem in facility Q UQ , UQ G M D VQ , and seek the optimal value, f(Q,i(Q) i(Q) n V Q f(Q,i{Q), M'= i(Q) at no cost. Thus, for example, in case Now, let from the open facility at Q = (VQ,EQ) binary decomposition tree VIII we from some facility VQ , VQ G M' we seek the optimal value , f(Q, i(Q), i(Q)) , of Q in which an open facility is available at is provided to terminal j(Q) from some ,VQ) , of the F C S F problem in Q in which a facility is available M \ {i(Q)} , and in case X the F C S F problem in i(Q) • ) - optimal value of a F C S F problem in Q when at no cost and the service is provided to terminal j(Q) where .) - optimal value of a F C S F in which it is required that service is delivered to the terminal a facility can be established at the terminal at i(Q) ; /(Q,UQ, i(Q) at no cost, and the service i(Q) . be any subgraph of G associated with'the vertex q of the T , and assume that for some optimal solution to the F C S F problem in G vertex v , v G VQ , receives the service from facility u , u j£ VQ . Then , our algorithm uses throughout the simple observation that the path which is used to deliver the service from 27 « to v in this optimal solution must pass through at least one of the terminals i( Q) or j( Q) of Q . Recurrence Rules In the first step we find decomposition tree f(Q, •, •) for all Q corresponding to the leaves of the T , for all cases I-XI above. That is, using, for example, complete enumeration we solve the above eleven cases of F C S F problems restricted to the different edges of G . Parallel composition Let that Q Q 2 Q is derived from Qi , Q 2 and j(Qi) = j(Q ) 2 I and 1 Q be the sons of Q i and Q Q , according to the binary decomposition tree by parallel composition. Then, we identify the terminals of 2 in accordance with parallel composition, i.e. and we compute f(Q, T , such i(Q) = i(Qi) = i{Q ) i J(Q) = 2 . , . ) as follows : f(Q ,0,0)] /(Q,0,0) = min { [ / ( Q j , 0 , 0 ) + , [/(^, 2 [f(Qi,KQi)J) + f{Q ,VQ M, 2 2 \f(QiAQi)AQi)) ,0) + f(Q , 2 i(Q ),0)] 2 lf(Qn<b,v ) + Ql /(<32,MQ ))], 2 + /(0 .«g .«g )]. lf(Qi,u J(Qi)) 2 2 Ql 2 f(Q2,KQ ),KQ2))}, + + + /(<*W(02).i(C2))], 2 \f(QiAQi)AQi)) , f(Q2,u ,J(Q ))}, Q2 2 V(QiAQi)AQi)) + / ( Q , < Q ) . ^ ) ] . Lf(0i,« ,j(0i)) + /(02,«'(02),«o )]. 2 2 2 gi 2 \J(QiAQi)*« ) + /«?2.«g .i(02))] }• Ql II f(Q,« ,9) Q = min{ [/(Qn^.0) f(Q2,*q M 3 2 + /(Q ,i(Q ),0)], [ / ( O i , , 0 ) 2 + 2 . [ / ( Q i . ^ . X G i ) ) + /(Q2. «'(<&). «g )] . [/(<?!,%> 2 28 V + / ( 3 , * ( Q 2 2 ) , . \f(Qu*Qi),v ) + Ql f(Q2^Q AQi))]. 2 \f(QiAQi)AQi)) + / ( « 2 . « o , « g ) ] , \f(QiAQi)AQi)) /(«2.«g ,j'(0 ))]> [/(<&.* AQi)) + 2 2 2 + 2 f(Q2AQ7)AQ2))] Ql « ' ( 0 i ) , « ) + f(Q2AQ2)AQ2))\. \f(QiAQi)AQi)) gi > + f(Q2,<Q ),v )}}. 2 /(Q,0,^g) analogous to Q2 II. / ( Q , i ( Q ) , 0 ) = min { [/(Qi, i ( Q i ) , 0) + / ( Q , i ( Q ) , 0 ) ] , [/(Qj 2 f(Q AQ2)AQ2))], \f(QiAQi)AQi)) 2 ^ 2 + /(Q .«'(%),«g )l. + 2 2 [/(Qi,i(<?iMQi)) + / ( Q , i ( Q ) , i ( Q ) ) ] , [/(Qi,i(Qi),i(Qi)) + 2 2 2 /(Q ,i(Q MQ ))] }• 2 f(Q,$AQ)) 2 2 analogous to I V . > f(Q,u ,v ) Q Q ,v ) = min { [/(Q,,i.^ + / ( Q , i ( Q ) , j ( Q ) ) ] , \f(Qi AQi) AQi)) + 2 Q 2 2 + /( 32. '( 3 ).^ )] i f(Q , Q ,VQ )], \f(Qi>* AQi)) \f(QiAQi),v ) + f(Q2,*Q AQ2))], u 2 2 2 < Ql Ql 3 /(<2 ,i(Q MQ ))], [/(0i,f(0i),» ) 2 2 2 g i \J(QiAQi)AQi)) + f(Q2,*<j AQ2))]. 2 ? < 2 2 [/(Oi.^.iCOi)) + + /(Q ,;(Q ),y(Q ))], 2 2 \f{QiAQi)AQi)) 2 + /(Q2,«'(02),«Q )]}. 2 f(Q,u ,j(Q)) Q = min { [ / ( g 1 , « g i + /( 0 , «Q , J'( % ) ) ] } • 2 2 29 /(Q ,*(<? ),./(Q ))] , [ / ( Q i , i « ? i ) , J « ? i ) ) 2 2 2 + VIII f(Q,i(Q),v ) analogous to V I I . IX f(Q, i( Q), j( Q)) =f(Q X f(Q,i(Q),i(Q)) Q i( Qi), j( Qi)) + f(Q ,«'(Q ), lt 2 = min { [ / ( ^ , { ( Q J , { ( Q J ) j( Q )). 2 2 + f(Q ,i(Q ),j(Q ))} 2 2 , 2 [f(Q ),i(Q ),j(Q )) 1 1 1 + /(Oa,«'(%).«(%))] } • XI f(Q,j(Q),j(Q)) = min { [/(QnKQO.KQj)) + f(Q ,j(Q ),;(Q ))1. 2 2 2 [/(Qi.i(Gi),j(«i)) + / ( Q , . « ? ) , i « ? ) ) ] } • 2 2 2 Series Composition Let Q and Q be the sons of Q, according to the binary decomposition tree, with t 2 corresponding terminals from Q i(Q\) , j(Qi) and i(Q ) , j(Q ) > respectively, such that 2 2 Q is derived and Q by series composition. Then, the terminals of Q are i(Q) = i(Qi) and j(Q) x 2 = j(Q ) . (Note that when the composition took place, the terminals j(Q\) and i{Q ) were 2 identified, i.e., j(Qi) = i(Q )-) 2 We then compute 2 f(Q , . , . ) from values of f(Qi, • , • ) and /($2' • ' • ) i previously computed, as follows : I / ( Q , 0 , 0 ) = min { [ / ( & , 0 ,0) +/(Q2,0,0)] , [ / ( O i J , ^ ) + / ( Q , « ( Q ) , 0)] , 2 [/(Qi,0,i(Qi)) + /(Q ,««j 0)]}. 2 II f(Q,u ,<H) Q 2> = min {[/(^,1*^,0) + / ( Q , 0 , 0 ) ] , [ / ( Q i , ^ , ^ ) + 2 /(3 ,*(<? ),0)] , [ / ( G i . t ^ X O i J ) 2 2 30 + /(g,« j ,0)], 2 < 2 2 + / ( Q , « g , 0 ) ] }• lf(QiJ(Qi)d(Qi)) /(Q,0,fg) 2 2 analagous to I I . f(Q,*Q)J) = min | [ / ( < ? ! , i ( + / ( Q , 0 , 0 ) ] , [ / ( Q i , * ( & ) , « 2 / ( Q , * ( Q ) , 0 ) ] , \f(QuKQi)M)) 2 f(Q,®,J(Q)) f(Q,u ,v ) Q Q ) + + f(Q2,"q M 2 [f(Qi,KQi),KQi)) Q i , 2 + f(Q ,KQ2)M } • 2 analogous to I V . + / ( Q a . M ^ ) ] , [f(Qi, u ^, v J + = min[[f(Q ,u ,9) 1 Qi Q /(Q ,«(<? ),»Q )] - [f(Qi^ ^ ) 2 2 2 Ql [f(Qi,v J(Qi)) Q + /(<? ,'(Q M<? ))], Ql 2 2 2 + f(Q2,«Q ,VQ )}, Ql 2 + 2 /(^2.«Q .WQ )] } • 2 f(Q,u ,j(Q)) Q 2 = min { [ / ( Q i , t i ^ , 0) + f(Q , 0,i( Q ))] , [ / ( G i , » 2 2 /(Q ,j(Q ),;(Q ))], 2 2 Ql \f(Qi,« AQi)) 2 \f(Qi,* ,v ) Ql + Ql AQi)) + f(Q2,u ,j(Q ))}, Q2 2 + /(Q ,i(Q ),j(Q ))] } . Q 2 2 2 f(Q, i(Q), ^g) analagous to V I I . f(QAQ)AQ)) = min { \f{Q ,i{Q ),%) l l + / ( Q , 0 , ; ( Q ) ) ] , [f(QiAQi)^ ) 2 2 Ql \f(QiAQi)AQi)) f(Q2AQ2)AQ2))\> \f(QiAQi)AQi)) + /(<?2.«'(02).i(G))], + /(02,«Q,i(0))], \f(QiAQi)AQJ) 2 31 2 + 2 + /(<?,XG),;(%))]}• 2 2 x f(QAQ)AQ)) = f(QiAQi)AQi)) + /(<?,*'(<9MQ)) • xi f(Q,j(Q),j(Q)) = + /(Q .i(Q ),i(Q ))- 2 2 2 2 2 2 Validity of The Algorithm Lemma 2.2.1 The algorithm solves the F C S F problem on a series-parallel graph. Proof: A t each iteration, starting from the leaves, the algorithm solves cases subgraph Q associated with a vertex q in the binary decomposition tree finite number of iterations we reach the root of series parallel graph T T. I-XI for some Clearly, after a whose associated subgraph coincides with our G . T h e n , / ( G , 0 , 0 ) is the optimal value of the F C S F problem on G . • Complexity of The Algorithm Lemma 2.2.2 DC For a S P graph G = ( V , E) with V and a set of potential facilities' sites n vertices (| V\ = n) , a set of communities M C V , the F C S F problem can be solved in time which is linear in n . Proof: The binary decomposition tree T can be constructed in linear time (Valdes et al. (1982)). 32 Further , T has m < 2n — 3 leaves and (m — 1) vertices which are of degree greater than 1. The proof then follows since the amount of computation associated with each vertex of T a constant time. Comment dynamic requires • Berne et al. (1985) have developed a general methodology for constructing linear time programming algorithms for a certain class of graph optimization problems on decomposable graphs. Their methodology is applicable to our F C S F problem on S P graphs, and an algorithm based on this methodology would be similar to the algorithm presented here. Although this chapter has less general scope, it has the advantage that the recurrence rules are determined explicitly which is naturally required for any implementation. Moreover, as is shown in the next section, an optimal solution for the F C S F problem can be employed in order to verify, in polynomial time, whether a sufficient condition for the nonemptiness of the core of a cost allocation game associated with this problem is satisfied. 2.3 THE CORE OF THE FCSF GAME ON SP GRAPHS We examine in this section a cost allocation problem associated with the F C S F problem, and for this purpose we need first to introduce the following game theoretic definitions and notation. Let 7 V = { 1 , 2 , • • • , * » } be a finite set of players and let c : 2 ^ —+ R with c(0) = 0 be a characteristic function defined over subsets of N referred to as coalitions. If c(N) designates a cost that has to be shared by all the players then the pair (JV; c) is called a (cost) cooperative game, or simply a game. For x £ R n game (N; c) satisfies and S C N , let z(5) = i ' ^ x c o s * U a o c a *i° n v e c t or a; in a x(N) = c(N) , and the solution theory of cooperative games is concerned 33 with the selection of a reasonable subset of cost allocation vectors. Central to the solution theory of cooperative games is the concept of solution referred to as the core of a game. The core of a game (N\ c) consists of all vectors x € R n such that x(S) < c(S) for all S C N , and x(N) = c( JV) . Observe that the core consists of all allocation vectors x which provide no incentive for any coalition to secede. In general, the core of a game may be empty. The cost allocation problem associated with the F C S F problem is concerned with the allocation of the cost incurred for satisfying the communities' demand for service. W e will formulate this cost allocation problem as a cooperative game and analyze its core. Formally, given a F C S F problem, defined on facilities' sites G = (V, E) with a set of communities M C V , we denote by FCSFg FCSFg c(0) = 0 and for each and a set of potential , for S C D , the F C S F problem obtained from the original problem by simply replacing D by S. is such that D C V S C D , c(5) Then, the pair ( D ; c) , where c : 2'^' —• R is the m i n i m u m objective function value of , is a cooperative game in characteristic function form, to be referred to as the Fixed Cost Spanning Forest ( F C S F ) game. In general, the F C S F game generalizes several cooperative games studied in the literature which were used to analyze a variety of cost allocation problems. For example, the F C S F game generalizes Littlechild's (1974) airport game and Megiddo's (1978) tree game. When D = V , the core of the F C S F game coincides with the core of the minimum cost spanning tree (m.c.s.t.) game (associated with the augmented network G ) , which is known to have a nonempty core, see, e.g., 1 Bird (1976) and D . Granot and G . Huberman (1981). For the case when D ^ V , D . Granot and F . Granot (1987) have shown that the core of the F C S F game is not empty provided that tree structure. Unfortunately, this result cannot be extended to cases when G has a G has a more general structure than a tree. Indeed, we provide below an example demonstrating that the core of a F C S F 34 game defined over a graph consisting of a simple cycle may be empty. Explicitly, consider the network G = (V, E) {1,2,3,4,5,6}, E= communities and M = {4,5,6} = 1 for all G E and that c — \ for all i £ shown in Figure 2.2 below. Therein, {(1,4), (4,2), (2,5), (5,3), (3,6), (6,1)}, D = { 1 , 2 , 3 } - is the set of is the set of possible facilities' sites. Further, we assume that M. { The core, C , of the F C S F game associated with G is given by: C = { x € R: 3 x + x 2 3 «i < 2 , x < 2, x 2 < 3 , x + x x V = 2 + x 3 3 < 2 , x + x x 2 < 3 , x + x = 5 } . Figure 2.2 35 G = (V,E) Y 3 < 3, c~ Now, one can easily verify that the core constraints induced by the three two-members coalitions imply that + x + x 2 3 < 4ij for any core allocation. Thus, since any core allocation x must distribute the entire cost, i.e., associated with x 1 + x 2 + x 3 = 5 , we conclude that the core of the F C S F game G , displayed in Figure 2.2 , is empty. The proof of the nonemptiness of the core of a F C S F game when G is a tree, provided by D . Granot and F . Granot (1987), employs the polyhedral characterization of the Directed Steiner Tree problem in series-parallel graphs given by Prodon et al. (1985). T o describe this polyhedral characterization, as applied to our F C S F problem, we first need to replace the graph with the directed graph directed edges G — (V ,E) <i,j> and <j,i> in which all undirected edges , with associated costs = c- . Then, we construct the augmented network V c . t the vertex o , and to E W e will refer to G 1 the directed edges <o,i> 1 1 1 = c(<j,i>) = c~ derived from G by adding to for all t G M , with as the directed augmented network derived from a m i n i m u m cost directed Steiner tree in • G are replaced by two c» = c(<i,j>) G = (V ,E*) G = (V, E) which is rooted away from c • = c(< o,i>) = G . Note that finding o and whose vertex set contains D , is equivalent to solving the F C S F problem in G . Further, we need the following notation; for a directed edge / = <i,j> the tail and j as a head of / , and for a subset of vertices directed edges having their heads, but not their tails, in S. admissible cut-set of G , if » ^ 5 C V 1 subgraphs G '(5) and We denote by A^, G'(V\ 1 S we denote by we refer to 8(S) i as the set of all A subset S , S C V , is said to be an 1 , S D D ^ 0 (D is the set of communities) and both S) of G' induced by S and V \ S , respectively, are connected. the set of all admissible cut-sets of G . 1 It follows from Prodon et al. (1985) that if the directed augmented network G parallel graph, then the incidence vector of a minimum cost directed Steiner tree of G 36 1 1 is a series , directed away from vertex o and whose vertex set contains Q U {0} , for any Q C D , is an optimal solution of the linear programming problem, LP( Q) , defined as follows: LP(Q) : min lex: x(6(S)) >l,SeA.,,SnQ^®,x>o\ (2.1) In fact, in view of favorable computational results obtained by Prodon et al. (1985) with instances of the Directed Steiner Tree problem on more general graphs than two-trees, they were led to conjecture that the inequalities describing the polyhedron of the Directed Steiner Tree problem on two-trees (i.e. , the feasible region of LP(D)) , while not sufficient to describe that polyhedron for the Directed Steiner Tree problem on more general graphs than two-trees, are nevertheless important in the sense that they often produce optimal integer extreme points. However, notwithstanding this favorable computational experience, LP(D) would fail to produce optimal directed Steiner trees even for the very special case in which is a partial two-tree. Indeed, let the underlying network G G be the simple cycle in Figure 2.2 and consider the directed augmented network G . A l l the edge weights in are assumed to be G 1 minimum cost directed Steiner tree in G 1 , with root E 0 , 1 , 2 ,3 , has a weight of 5 . However x* 6 R + X* - i (0,4) 2' _ i 2 • *(*5,2) x* (5,3) - 1 X* (6,1) 2 • x* , = 0 defined as follows: x* - i (0,6) ~~ 2 ' X* = (4,2) derived from 0 and whose vertex set contains vertices i 2 • 1 1 Then, it is easy to check that the X* (0,5) - X* = (4,1) 2' 1. G - 2 1 ' = 3' X* ' i (6,3) 2' otherwise , is feasible to LP(D) associated with G' and has a lower objective function value of 4.5 . 37 Nevertheless, LP(D) Proposition 2.3.1 is still useful for the analysis of the F C S F game. Indeed, If the incidence vector of a m i n i m u m cost directed Steiner tree in the directed augmented network G' , rooted away from o and whose vertex set contains D , is an optimal solution to LP(D) , then the core of the associated F C S F game is not empty. Proof: game Let c(Q) (D;c) with formulation of denote the optimal value of LP(Q) , Q C D , and consider the cooperative c(0) = 0 . Then, (2.1) provides us with a generalized linear production game (D;c) , see D . Granot (1986). Further, one can easily verify that the sufficient conditions given therein for the nonemptiness of the core of a generalized linear production game are always satisfied for (£>;£), implying that the core of (D;c) each Q C D , let c(Q) is not empty. O n the other hand, for denote the optimal value of the integer programming problem, IP(Q) , derived from LP(Q) Observe that c( Q) coincides with the characteristic function value assigned to F C S F game. Clearly, G 1 by restricting the nonnegative decision variables therein to Q , Q C D , in the c(D) = c(D) . o and whose vertex set contains D U {o} , solves LP(D) , we Thus, in this case the core of ( D ; c) is a subset of the core of (D; c) and the nonemptiness of the core of the F C S F game then follows since the core of (D;c) empty. values. c(Q) < c(Q) , Q C D . Moreover, whenever a m i n i m u m cost Steiner Tree in , directed away from vertex have that 0 —1 is never • Moreover, when the underlying network has a series-parallel structure, we can test in polynomial time whether the sufficient condition for the nonemptiness of the core of the F C S F game, given by Proposition 2.3.1, is satisfied. Explicitly, we first find a m i n i m u m cost Steiner tree 38 T , using the algorithm developed in Section 2.2 . Then, we can apply the Prodon et al. (1985) to check if the incidence vector of will be true if and only if the T-guided algorithm of T is an optimal solution to LP(D) . This T-guided algorithm terminates with a dual feasible solution whose corresponding objective function value is equal to the weight of T. 39 Chapter III ON SOME OPTIMIZATION PROBLEMS ON k-TREES AND PARTIAL k-TREES The recursive definition of k-trees implies that a k-tree has at least two vertices, called leaves, of degree k , with completely connected neighbors. denoted by Adj(v) , and we let by removing a k-leaf v K v The neighborhood of a k-leaf v is denote the k-clique induced by it. Clearly the graph obtained and its incident edges from a k-tree is a k-tree itself. This defines a reduction process for k-trees, and such a reduction process is complete when it ends up with some kclique, R , the root of the reduction process. A reduction sequence can be thought of as giving an orientation to a k-tree (Arnborg and Proskurowski (1986)) where vertices are made descendants of kcliques. Namely, if i f is a k-clique, then v is a descendant of K in a given reduction sequence if and only if when v was removed, each vertex of Adj(v) was either a member of K or a descendant of it. k-trees are also known to have the following separation property (Rose (1974)): every minimal separator of a k-tree consists of k completely connected vertices. In this chapter we will use the notion of the reduction process and the separation property to construct, for a fixed k, efficient algorithms for several optimization problems on k-trees and 40 partial k-trees. In particular, in Section 3.1 we follow the reduction process to construct a linear time algorithm that finds shortest simple paths from a given vertex to all other vertices in a weighted k-tree having nonnegative edge weights, and in Section 3.2 we use a similar approach to compute the diameter (longest path) and the vertex center of a k-tree with equal edge lengths in linear time. Finally in Section 3.3 we construct an 0(n ) k+2 time algorithm for solving the Simple Plant Location ( S P L ) problem in weighted partial k-tree graphs, which generalizes Hassin and Tamir's (1986) 0(n ) 4 time algorithm for solving the S P L problem on series parallel graphs (i.e. partial two trees). 3.1 Single Source Shortest Paths Problem in k-trees Let G = ( V , E) be a weighted k-tree with | V | = n , such that each (directed) edge e in E has a "length" (weight) w(e) > 0 . For each pair of vertices u and v in V define d(u,v) to be the length of a shortest simple directed path from u to v . Given a vertex s in V, we wish to find the distances from s to all other vertices v in V, as well as distances from all v E V to s . This problem is recognized as the Single Source Shortest Path Problem (SSSP) problem, and we demonstrate below that it is solvable in linear time for k-trees with nonnegative edge weights. For simplicity of presentation, we will only be concerned with the shortest paths from vertices v E Let s to all other V. v obtained from be a k-leaf of G = (V,E) and denote by G by removing v and its incident edges from G 1 = (V ,E?) 1 the weighted graph G and whose edge weights, w'(e) , e E E' , have been modified as follows : min { w((i,j)) , w((i,v)) + w((v,j)) } for i,j E Adj(v) (3.1) w((i,f)) otherwise 41 Further, let d(i,j) denote the length of a shortest simple directed path from node i to j in G . d'(i,j) = L e m m a 3.1.1 Let i, j £ V Proof: where and d(i,j) for all i,j€ V. 1 d'(i,j) = w\p[j ) < d(i,j) = w(p -), and assume, on the contrary, that 1 i » to j in G p ~ and p - are shortest directed simple paths from 1 $J w'(p' ••) and y w(p--) are their corresponding lengths. Let y w((u,w)) }. Clearly |^41 > 1 . If \A\ = 1 then replacing (u,w) in p'^- by (u,v) and which = have that |^4| > 2 . < Let 1 A = { (u,w) £ p •• : w'((u,w)) < ' 1 A = {(u,w)} for some u,w G Adj(v) . Then, by p" - in G for we obtain the simple directed path (Pij) i contradicting the optimality of w ( t t j , a n d (u «w ) 2 G , respectively, and 2 p^- in A , such that be in G . So, we must and K 2 are not necessarily distinct. Then, upon replacing (MI,WI) and (« , iu ) by («i,v) , (f, Wi) and (« , a) , 2 (t), w ) in p' -j , we obtain a directed path (not simple) 2 Clearly, pj'- 2 2 p"- in G such that contains a cycle, C, in G which contains node w(p" ) < w(p-j) . v . Since we assumed that nonnegative edge weights, upon the removal of C from p"- we will obtain a simple path G satisfying complete. wCp ••) < y u> (?,•„•) y This contradicts the optimality of p.- , y G has p- in and the proof is • Lemma 3.1.1 can be used to construct a linear time algorithm to find shortest paths from some designated source node s , in a k-tree G = (V, E) , to all other vertices in G . An algorithm for solving the SSSP problem in k-trees The algorithm has two phases. Phase 1 W e successively eliminate k-leaves and their incident edges from weights of the remaining edges using (3.1). G while modifying the Since a k-tree has at least two leaves, we can always 42 avoid the elimination of the source node s . obtain a subgraph G = (V ,E ) k k simplicity, we will assume that The elimination of the k-leaves is continued until we of G , whose number of vertices is just a function of k. k | V * | = k, which can be achieved by letting G k For be a k-complete graph containing node s . Next, we solve the SSSP problem in G , whose edge weights were derived by successively k modifying the edge weights using (3.1). This can be done in 0(k ) elementary operations, which is 2 constant for a fixed G. k k. Let B y Lemma 3.1, d(s,u) , u G V*, be the weight of a shortest path from d(s,u) = d(s,u) for all M G V*, where s to u in d(s,u) is the weight of a shortest path from s to u in G . Phase 2 Let v be the last k-leaf to be eliminated at Phase 1, and consider the k-tree graph obtained by adding v and all its incident edges same edge weights, w(i,j) , as it had in Phase 1. Now, if d(s,v) from s to v in G k then d(s,v) = Lemma 3.1.1, d(s,v) = d(s,v) and (v,u) , u G Adj(v) , to G*. Let G k G k have the is the weight of a shortest path min { d(s,u) + w(u,v) , u G Adj(v) } . Moreover, by d(s,u) = d(s,u) for u G Adj(v) , which implies d(s,v) = min {d(s,u) + w(u,v), u G Adj(v) }. (3-2) Thus, by successively adding k-leaves in the reverse order to which they were eliminated in Phase 1, and by calculating the weights of shortest paths using (3.2) we solve the SSSP problem in G. • The linear complexity of the above algorithm follows from the fact that in Phase 1 we have at most n — k steps and that each recursive equation used either in Phase 1, to modify the weights, or in Phase 2, to calculate weights of shortest paths, can be computed in constant time. 43 3.2 Diameter of a k-Tree Let G = (V, E) max{d(u,v) be an undirected graph. : v £ 7 } . The diameter of will compute the diameter of a k-tree G is D = mar { ecc(«) : u £ V } . In this section we G — (V,E) The algorithm consists of two phases. of the k-tree. Initially, we set The eccentricity of u , u £ V, is ecc («) = with equal edge lengths in linear time. In the first phase we will follow a reduction process ecc (a) = 1 for all u £ V(K) K and family of all k-cliques in G (|3G| = (n — k) k + 1 , n > k) , V(K) K and ecc («) is the eccentricity of u £ V(K) K K £ 3G , where 3G is the is the vertex set of the k-clique in the subgraph of G induced by V(K) and all the descendant vertices of K in the reduction process followed by the algorithm. Let K , where V(K ) v neighbors of a k-leaf V = Adj(v) = t>, and for each {%,•••,%}, £ Adj(v) let K j denote the k-clique induced by the designate the side k-clique induced by {v} U Adj(v) \ {uj} . Before a k-leaf node is being eliminated by the reduction process we store, for K later purposes, the current eccentricities, ecc (u) = ecc (u) , of all vertices v v u £ Adj(v) . After the elimination of o , we compute the eccentricities of vertices Uj , Uj £ Adj (u) , restricted to the subgraph of the k-tree G induced by Adj (v) U {v} and the descendant vertices of all side k-cliques K j as follows : ecc (uA v = max { max ifr 3 and we update ecc (u) Kv K. ecc '(«,-) , K- min J i£V(X.) 3 ecc (x) + 1 } (3-3) , for all u £ V(K ) , V ecc {u) Kv = max { ecc (u) , ecc (u) v 44 I<v } (3.4) Clearly, in the last step of the first phase we have ecc (u) R = ecc ( « ) , « € V(R) , where R is the k-clique which is the root of the reduction process. Next, for u G V(K) , K G 3G , we denote by ecc^(u) of the k-tree G induced by in the reduction process. ecc^(w) = 0 , for all order. V(K) and the complement of the set of the descendant vertices of K In the second phase we initially set u G V(K) the eccentricity of u in the subgraph and A t each step we add a vertex D — max {ecc(u) : M G V(R) } and K G 96 , and follow the reduction process in the reverse v, compute the exact eccentricity of v in G, ecc(v) , and update D as follows : ecc(u) = max { max ecc (v) , 3 min ueAdj(v) (3.5) ecc (u) + 1 , v and (3.6) D = max { D , ecc(u) }. We further update other eccentricities in the following manner: min ecc *(x) + 1 } , (3.7) and for j = 1 , ..., k , ecc \v) J = max { min uCAdj(v) ecc (u) + 1 , v and finally 45 (3.8) ecc (u) = max { ecc^(u) v , ecc"(«) , u G Adj(v) } . (3.9) Clearly, at the end of the second phase we have computed the diameter, D , of the k-tree G . Since the reduction process has ( n — k) time required to compute Remark steps and each step requires a constant time, the total D is 0(n) . Since we compute in the above algorithm the eccentricities of all vertices in V, it follows that we can also find in linear time a vertex with the smallest eccentricity. Such a vertex is called a vertex center of G . 46 3.3 Simple Plant Location (SPL) Problem on Partial k-Trees Let G = (V, E) be an undirected weighted graph, with \V\ = n , in which each edge e, e £ E, is assumed to have a length w(e) > 0 . Further, each vertex D in fixed cost, c , to open a facility at v v , and a transportation cost function gv(d(v , . )) which is a nondecreasing function of the distance, d(v, . ) , from node potential facility site as well as a customer. defined with respect to V is associated with a v. Each vertex is viewed as both a The Simple Plant Location (SPL) problem problem, G , is concerned with the location of facilities at vertices in G so as to minimize the sum of the set up costs and the transportation costs. Formally, the S P L problem seeks a subset of vertices F , F C V , that minimizes + X) veV 9v(d(v,F)) , where d(v,F) = min d(v,f) . « For general graphs, the S P L problem is known to be NP-hard. However, Kolen and T a m i r (1986) developed an 0(n ) 2 time algorithm to solve the S P L problem on tree networks and Hassin and T a m i r (1986) constructed an algorithm to solve this problem on series-parallel graphs. c veF 0(n ) time 4 The purpose of this section is to develop an algorithm that solves the S P L problem on a partial k-tree graph in 0(n* ) +2 elementary operations. Thus, for a fixed k our algorithm is polynomial in the number of vertices, n , of G . Observe that the embedding of a partial k-tree into a k-tree, for a fixed 0(n ) k+2 k , can be done in time, as shown by Arnborg et al. (1987). Therefore, since the addition of edges with infinite length would not affect the solution to the S P L problem, we will assume in the sequel that the partial k-tree graph has been completed into a k-tree. Our algorithm follows a reduction process of a k-tree G . Accordingly, let K be some k-clique with a vertex set will denote by h(K, f , f ,• • •, f ) x G(D(K) U V(Kj) of 2 k V(K) = { «j , u ,• • •, u } . 2 k We the optimal value of the S P L problem restricted to the subgraph G, induced by V(K) and all the descendants of the k-clique K reduction process followed by the algorithm, with the stipulation that 47 in the « . is served by /,• for i = f 1 , 2 , • • •, k , and where /,• can be any node in G . Thus, the optimal value of the S P L problem on G is given by min { h(R , / , f t 2 ,• • •, f ) : A € V, i = 1 , 2 k k } , where .R is the root of the reduction process followed by our algorithm. An algorithm for solving the SPL problem on a k-tree Suppose that v is the k-leaf which is currently being eliminated in the reduction process followed by the algorithm. Let whose vertex set is = Adj(v) U {v} \ {uj} , j = 1 V(Kj) Adj(v) — { « ! , • • • ) « * } and denote by k. Kj Let K v the 'side' k-clique be the k-clique whose node set is Adj(v) . For any side k-clique the optimal values { h r'h } 1 t n e n °d h(Kj e s e t K j , which was not previously considered, the algorithm first finds , fa ,-••,/*) °f V(K j) > t for all n V, ii = 1 ,• • •, k . it is easy to verify that for all (/j ,• • •, f ) , /,• 6 V , « = n k ; i f e j f { ,A f) k is the facility serving (A > A? >'••)/*) k k' =«=iE /, + «E=i 9 WiJi)) c j , { // ,• • •, f' , } t k E i=i - Si r'.(^') - !) ' is the set of all distinct v h(Kj , fa h(K v , f\ >•, AO » c a n /,'s ; (Ai'iA) We will say that 48 r 10 appearing in , / ,• • •, /j.) . 2 . A s it will be shown, the expressed in terms of the optimal D e A) i associated with the side k-cliques K - , j = 1 introduce some notation. 3 ' > and <(//) denotes the number of instances that / / appears in (f optimal value of the S P L problem, (- ) c Next, we solve the S P L problem associated with the k-clique K values, In fact, if we denote by k , and side k-clique, K - , not previously considered h(K where e /,• € is a k. First, we need to facility assigment for vertices { ' i >•••> k } if node lj receives the service from facility f.,j= be a facility assignment for 1 fc. Adj(v) = { « ! , - • • , Then, the facility assignment F to 1 } , and let Adj(v) r. Let F = (A A) V(K •) fl .Adj(i>) , j V• = Fj induces a facility assignment to = Vj , specifying for each node in V(K j) , except node i>, the facility providing service to it. F = Then, one can verify that for any facility assignment { "1 (A »"••»/*) to Adj(v) = «* } , , / ) = min j A(/f, , A t h(K v ,A t f) + £ k j , (*i - «)) ~ j=i (k-1) g (d(v,s)) - v dS^k-l) j=i + 6) 2 - «=i A' (3.11) + (l-«,,-)(*-2))] - ( l - * ) [ E (*-l) 4 3 i=i M («../.)) + E /;- (*4,i * + rf c i=i ' (*-!))]:« e (jDiKA U { « } U { / 1 ,-,/*}}, i=i where 6 = 1 if s ^ { A' >'"•> X and <(/,') = } and 1 and zero otherwise; 6 z e r o 3 otherwise and = 1 if f5 = 1 if s = / ' G { / / , • • •, f i } 2 A(if« , A i " " » / * ) = 0 previously encountered by the algorithm) and zero otherwise , 6 otherwise, i G {1 , k' } . Further, ( F - , s) 49 k 4 i (i.e . if,, was not = 1 if <(// ) > 1 and zero is the facility assignment to V(Kj) which consists of the facility assignment and v is supplied from Fj to s . The set V • , induced by the facility assignment { {[ , •• •, f^, } and F to Adj(v) , <(/' ) , i = 1 , • • •, k have the same f meaning as in (3.10), and D(K) denotes the set of descendant vertices of the k-clique The algorithm will terminate after h(R) , given by h(R) — min { h(R , f\ K. n — k steps with an optimal value to the S P L problem, , fa) fa € V, i = 1 , • • •, k } , where R is the root of the reduction process followed by the algorithm. Proposition 3.3.1 The above algorithm solves the S P L problem on a partial k-tree graph in 0(n ) elementary operations. Proof: The embedding of a partial k-tree into a k-tree requires k+2 of distances between all pairs of vertices requires 0(n ) 2 0(n ) time. The computation k+2 time, using the algorithm developed in Section 3.1. W e assume that the computation of g (d(v,x)) , for a given x , requires constant time. v Further, in each step of the algorithm we need, in the worst case, h(Kj,--- 0(n ) k+1 time to compute h(K v time to compute ) using (3.11). Hence, the total time to solve the S P L problem on a partial k-tree is bounded by 0(n ) k+2 k+l k ) , using (3.10), for all side k-cliques that were not previously considered by the algorithm. It takes 0{n )) 0(kn ) = 0(n ) k+2 . • 50 + 0(n ) 2 + (n — k) (0(kn ) k + Chapter IV k-CABLES AND k-PATHS IN k-TREES In this chapter we study the notion of k-path and k-cable in a k-tree. In Section 4.1 we present a new characterization of a k-path in k-trees and develop an 0 ( n ) 2 algorithm for solving an R k-cable decomposition problem of a k-tree. In Section 4.2 we construct a linear time algorithm for finding the k-cable diameter (i.e. length of a longest k-cable) in a k-tree having equal edge weights. 4.1 An R k-cable Distance Decomposition Problem Let G = (V, E) be a k-tree and R a positive integer, R > 2 k — 1 . We are seeking in this section a decomposition of V to a minimum number of components, that for any pair of vertices and defined below, between i i and ; j , i, j € V* and does not exceed 1 V , •••, V ' , such 2 t = 1 , • • • , / , the cable distance, to be R . W e will refer to this problem as the R k- cable distance decomposition problem. We develop in this section an 51 V, 0(n ) 2 time algorithm for finding such a decomposition in the special case when G is a k-tree in which a l l the edge weights are equal to one. First, we need to introduce some new definitions and notation. The k-cable, denotes a collection of k vertex-disjoint paths between vertices The length 1 of the k-cable C(u,v) , W(C(u,v)) C(u,v) . The k-cable distance, c c C(«,D) is the collection of all k-cables between « and v i n a k-connected graph. , is the sum of the distances of the k paths in d (u,v) , between vertices cable between these two vertices. That is, d (u,v) C(u,v) , u and v is the length of a shortest k- = min { W(C(u, v)) : C(u,v) G C(u,u) } , where u and v . Apparently, the notion of a k-path, introduced and studied by Proskurowski (1984), plays a major role i n the analysis of our decomposition problem. Definition 4.1.1 and (Proskurowski (1984)). k + 1 complete subgraphs with a k-clique and such that and A k-path is an alternating sequence, KP = < Q , T , Q , T , • • •, T r T { 2 2 3 n KP , of distinct k , Q > , starting and ending n contains exactly two of the distinct k-complete subgraphs Q i l Q . { It was shown by Proskurowski (1984) that i n a k-tree G , the vertices of the minimal subgraphs separating two nonadjacent vertices induce a k-path. Proposition 4.1.1 1 The k-cable distance between two nonadjacent vertices Proskurowski (1984) defined the length of a k-cable, u and v i n a k-tree G C(u,v) , to be the length of a longest path i n C(u,v) . He also suggested therein other plausible definitions for the length of a k-cable, one of which is the definition of the length of a k-cable used i n this thesis. 52 with edge lengths equal to one is equal to the length, W(C(u,v)) , of the k-cable C(u,v) induced by the vertices of the unique minimal k-path separating adjacent then d (u,v) = 2 k + t where u and v in v . Moreover, if u and v are not t is the number of (k+l)-cliques appearing in the unique c k-path between w and G . (Observe that the number of (k+l)-cliques in C(u,v) may be zero.) Proof: Let C(u,v) < Qi , T , Q , •• > T 2 u and 2 n be the k-cable induced by the , Qn > , between u and v , and let k-path C'(u,v) KP(u,v) , KP(u,v) = be any other k-cable between v . B y Theorem 3.2 in Proskurowski (1984), each path p' of C ' contains all the vertices of some path p in C(u,v) , implying the minimality of implies that each one of the (fc-f l)-cliques to the k-cable T in t C(u,v) . The remaining edges in The proof follows since Q and x Q n W(C(u,v)) . The construction of the k-path KP(u,v) C(u,v) are k-cliques. contains exactly one edge that belongs are (u,i) , i £ Q , and (j,v) , j £ Q 1 n . • Next, we will present an alternative characterization of a k-path which will be used in the sequel. First, we need to introduce some additional notation. Let G = (V, E) 3G (resp. , %') denote the collection of all k-cliques (resp., (k+l)-cliques) in G. V, Q £ % , Q £ %' we let S (U) = max „,„.d Cv 1 0 where V(A) v a n ( 2 ^ vCV(Q) Definition and 6'Cv) ' v = max Q' , U £ ,d Cv,v), c vCV(Q') ' y t as follows : for ^(^j) — ^Q ^ 3^ > V 2 Q f 1 u r t n e r and i Q in 2 <»i;.) 4.1.2 { for all pairs v , { The extended Vj 3G , Qi <v v- Q-x i two inequalities is satisfied as a strict inequality. orders (3G' , , v) e For a vertex denotes the vertex set of A . For each pair v , vj £ V we define a partial order on 3G , (3G , < „ . „ . ) &Q ( i) ' V be a k-tree and let Q if l <.. Q v v 2 if and only if 6 Q (v ) { < Q i <v vj Qi and at least one of the Similarly, using f 6Q(*0 , we define the partial £ V. k-path between 53 vertices v t and «• , KP(v , t v •) = < T , Q , T x x 2 , Q , •••, T 2 (k-t-l)-cliques 7\ and T Proposition 4.1.2 vertices , Qn , T n , where n+1 > , is the k-path n + 1 and X in the k-tree graph KP{v ,vf) = i extended with the two { V ^ ) = { » J U V(Q ) The extended k-path and KP(v ,Vj) V(T ) = {} n+1 < T , Q , •••, Q x U V(Q ) Vj x , T n . n > n + 1 between G = (V, E) consists of all minimal k and (k+l)-cliques of G with respect to the partial orders (9G , <«,.«.) and (96' , <«,-«.) . respectively. Proof W e first show that any (k-f-l)-clique that is not contained in with respect to (3G' , <«,.«.) • be a vertex in M such that (k+l)-clique in KP(v ,Vj) Let 7\ f with the highest index such that p <v Vj t M. <v Vj T Otherwise, let . contrary, that there exists a (k+l)-clique cannot be in KP^v^Vj) such that T p <v Vj t M. , and let t x T be the (k+l)-clique in p Then, d (vj,x) > c v(T m a x v e KP(v ,Vj) i ) ^ ( ji ) c v ' v M . Next, we will show that every (k+l)-clique M KP(v ,Vj) have no (k+l)-cliques in common { is in KP^v^x) p is not minimal Observe that x is not a vertex of any and KP(v ,x) f then it is easy to see that T = max^^. y^jd^v^v). i . Now, if KP(v ,Vj) i implying that M be a (k+l)-clique which is not in d (v ,x) c KP^v^vf) T in KP(v ,Vj) is minimal. Assume, on the { M such that M <v Vj T. B y definition, it follows that t . Moreover, by the above there exists a (k+l)-clique Since (3G' , <v Vj) is transitive, that would imply t T p T p £ <«,« J KP(v ,Vj) i T, which is impossible. Next, we will show that every k-clique which is not in KP(v , { be a k-clique not contained in dcK,Zi) KP^v^Vj) = ™<M ) veV(M dc(v ,v) { KP(v , t and vfj , and let vertices d {vj,x ) c = max 2 have no k-cliques in common then between two subcases. 54 Q x veV(M) d (v ,x) c j <« v - M. i J x x w •) is not minimal. and x 2 in M So, let be such that . Now, if KP^v^x^) and Otherwise, we need to distinguish In subcase 1, clique, T Q Q <v P KP(v , , such that Vj) t <v x v {Vj x± and, in fact, all vertices of £ y ( T M, rfc(»,-,t;) j where Q and = T p p — d (vj,x ) c 2 m a x Vj — x 2 separator. Then, Q By the above, there exists a k-clique transitivity of (3G , <«,-«•) implies that Let G = (V, E) V : ddv^v) < q}. be a k-tree, v ( T ) ^ ( j^ ) The subgraphs Proof 1) € V unique k-path KP (v ,v) t in KP(v ,Vj) Q Q p M <«,-« - Q- in p contained in Clearly, J t Q <v^j p <«,-« - Q , which is impossible. i u? (fe,«,) < m c v is a k-leaf in . M. Then, V. — { v € t { d^v^v) v£V = m. Then, there exists a rf and ¥ Let Q, be the k-clique adjacent to ¥ in the x x for all t t V . = < Q , T , Q , T , • •, T, , Q, > , between 0 W v G V, are sub-k-trees of G . max dc^jTT) = U| • J 2 v£ Q, e V . It is easy to see that any other vertex > m . Thus, node p M is not in KP(v ,Vj) such that KP(v ,Vj) G ( V , ) = ( V^E^, , KP(v ,'v) . Clearly, { Q (3G,< . .) . q — a positive integer, and for any u , - G V let such that t d^v^x^ • Then, it is easy to see that v is minimal with respect to { which determines a k-cable (7(1^,¥) of length m. KP(v ,U) v . Moreover, Further, denote by G(V^) the subgraph of G induced by Proposition 4.1.3 Choose are vertices of some k-cliques in , in KP^^Vj) p e v £ Assume that there exists a k-clique M such that dc(vi,v) Then, there exists a k- \ {rj . Finally, we show that every k-path M . Then, M is a k-clique of some (k+l)-clique, T { a is both a u,- — x± separator and p . { M. i V j KP(v ,Vj) m Q KP(v ,Vj) but which is a k-clique of some (k-f-l)-clique, Vj) { In subcase 2, = is not a vertex of any k-clique in x , not necessarily contained in KP(v , p , of p x v v and thus the vertex set of adjacent to Q, is v , if exist, would have G(V ) . B y eliminating 17 and repeating the above { 55 procedure we construct a reduction process for G(V ) , implying that it is a k-tree. • { Recall that a reduction process in a k-tree with respect to k-cliques in G. and t G , then K t induces a descendancy relation of vertices Such a relation can be extended to a descendancy relation among k- cliques and (k+l)-cliques in G. In general, if K in G Kj are two k-cliques (resp. (k+l)-cliques) is said to be a descendant of Kj if every node that is either contained in K or i is a descendant of K { (resp., some k-clique in K) { is also either contained in Kj or is a descendant of Kj (resp., descendant of some k-clique in Kj) with respect to the reduction process. This descendancy relation in can be used to index all G k(n — k) + 1 (k-f-l)-cliques) in G , such that the index of a k-clique (resp., (k-f-l)-clique) index of a k-clique (resp., (k+l)-clique) Now, let G(V ) and is a descendant of K { t and %j (resp., %[ and Kj. ) , respectively. Further, let and 3G- (resp., 9G' - and %'j ) , respectively, and assume that that t Krj be the k-cliques (resp., (k+l)-cliques) having the highest indices, ; is smaller than the K G(Vj) be two sub k-trees of G with a corresponding collection of k- { cliques (resp., (k+l)-cliques) % and Kj if ^-cliques (resp. n — k r < t 9G,- n %j ^ 0 (resp., 9&J D %'j ^ 0) if and only if K i r - and t { r- , in 3G,- Tj . Then, it is easy to verify € %j (resp., K I T{ Kr T{ G 3G'- ) . This result can be used to establish the Helly property of a set of collections of k-cliques (resp., (k+1)cliques) of sub k-trees of a given k-tree, as follows : Proposition 4.1.4 Let G x G m be a collection of sub k-trees of collections of k-cliques (resp., (k-fl)-cliques) 3G ,---,3G 1 m (resp., % I 1 G with an associated , •••, % ,) . Let f 3G = {%!,•••, 3G } and 3G' = { 3G' , • • •, %' } . Then, 3G and 3G' have the Helly property. That is, m m if 3G n 9G. ^ 0 (resp., %' D 9Gj # 0) for all i and j, then ; ; { # 0). 56 3G # 0 4 (resp. n™ 5&( ; Proof: Let K r{ (resp., K ) be the k-clique (resp., (k-fl)-clique) with the highest index in 3G,- T{ (resp. , 3G' ) and assume, without loss of generality, that (resp., 3C[ n %'j ^ 0) for a l l j we have Theorem 4.1.1 K r < r • for all j . S x £ %j (resp. , K fl Let G = (V, E) be a k-tree, l rj £ %'j ) for all j . • V = { v , v ,• • •, v } , n > k +1 , and let x 2 be n an even integer, R > 2k. For each v £ V let G ( K , ) be the sub k-tree of G induced by V = { { { v € V : <f (",f,-) < j + k — 1 } , with an associated collection, 9G,- , of ^-cliques. e Then, D - %>i 7^ 0 > I Q { 1 > 2 , • • •, n } , if and only i f d (v , Vj) < R for all pairs t, j £ I. eI c Proof: Suppose that ^- j^i G(VA we have that Q , 4.1.1 it follows that V v and C W(C ^ ) < f Q V and KP(v ,Vj) { satisfying m a z ^ ^ dc(v ,v) t all k-cliques i n KP(v and v W(C paths in C(v;, vA which are in the component C Next, assume that for any pair t ,Vj) i, j £ I, y ; Proposition 4.1.1, d (vj, c ; = § • v) < § + t and Vj , respectively. t Q ) < § , into two From Proposition , implying that de(v ,Vj) { = W(C Q^} denotes the total length of the V . n d (v ,Vj) c t < R . Then, let Q t be a k-clique i n { If KP(v ,Vj) does not contain a k-clique then { Vj are adjacent and the k-clique containing U < 4 + k — 1. ' — 2 1 = d(v ,x{) = ^ + k — 1 . If no such k-clique exist then are in 3G,- PI 3C- . Proposition 4.1.1, W(C . Q ) v { Q ) < R , where, for example, Q) + W(C dJv^v) C(v , vf) , induced by KP(v ,Vj) , containing v , l l v ; v£V(Q ) Q separates the cable ^ which is in 3G D %j . B y definition of Vj) { *' ' — * v t components (sides) C KP(v , , dciv^.v) < § + k — 1 and max v£V(Q ) Now, the k-clique W(C in the k-path l max " v ¥^ 0 • Then, it follows from Proposition 4.1.2 that for any pair i, j £ £ I there exists a k-clique t v { implying that and Vj is in 3G^ n %j . W(C V 57 7^ 0- t Otherwise, by Q), < § • Therefore, again by k - 1 for all v £ Q, . Thus, Helly property of the collections 96^ we have that D -g. v E Q, £ % CI %j , and by the { Theorem 4.1.2 Let G = (V,E) be a k-tree, V—{ v ,v t R > 2k — 1 . For each be an odd positive integer, v } , n > A + 1 , and let R 2 n v G V let G(V ) be the sub k-tree of G t i induced by V — { v £ V: d (v, v ) < L f J + A- } , where ["J is the largest integer smaller than t e { n a , and let 3G- be the collection of (k+1 )-cliques i n G(Vj) . Then, 9Gj ^ 0 , I C { l , - - , n }, if and only i f d (v ,Vj) < R for all pairs i , j € I. c Proof: { Suppose that f~1 .^3Gj ^ 0 . Then, it follows from Proposition 4.1.2 that for any pair 1£ G I there exists a (k-fl)-clique be the k-cliques in KP(v ,Vj) that induce { and thus, < Lf J • Similarly, W(C ^ ) V Q implies that W f C ^ J Lf J + T, i n KP^^Vj) < Lf J . Thus, T , . Clearly, dc(v ,v) f <f«;(V , v) < [§ J + k c t „,) = ^ ( C „ . l+1 < [§ \ + k — I for all v G Qi 1 d (v , Q Q ( 1 uG Q for all , which 1+1 ^(^.Q^^ + !<[§] + ) + i = RNext, assume that for every pair KP^^vA satisfying t clique then t, j G I, d^v^Vj) = max d^v^x^ then a l l (k+1 )-cliques in KP(v < R. Let T, be a (k-f-l)-clique in = Lfj + k. If no such (k+1)-clique exist ,Vj) are i n 3G' f l 36'- . If KP(v ,Vj) does not contain a (k+1)- dc(v ,v) t { v and i> • is i n 3G' f l 3G'-. v and Vj are adjacent and the (k-t-l)-clique containing f Otherwise, T G 3Gj- . Suppose that l Q ) = Then, = T, G 3G' n 3G^. . Let Q, and such that i, j T l Lf J + 1 • Therefore, [ f J > which implies that d (vj,v) c [ f J + k for all v G T, , implying that conclude that f~l is induced by the k-cliques 3G{ ^ 0 . < W(C Q and Q i l ) = R - V Q [f J + k — f 1 for all t E l+ Lf J ~ 1 = i n KP(v , { Lf J • Further, «•) . + 1 - 1 d (v-, c v) < T, G 3G'- . By the Helly property of the collections 3G' we • Observe that in Theorem 4.1.1 and 4.1.2 we restrict 58 R to be at least 2 A — 1 . It can be easily shown that if R < 2 k — 1 then the only decomposition of decomposition problem coincides with the vertex set V for our R k-cable distance V. In general, we solve our R k-cable distance decomposition problem by using the properties of two clique-intersection graphs associated with G , which are constructed as follows. If (resp., 1} G (Vi) denote the sub k-tree of G induced by k+1 V (resp., = { G V: d (v, { v c v) = k (V,E ) k G (Vi)) k+1 G (resp., , v G V, where { G (V ) k { { V = { v G V: d (v, u.) < f + k { c t G (V ) k t = k+1 v G V let |_§J + k } ) . Let % (resp., 3G[) designate the collection of < t k-cliques (resp., (k-f-l)-cliques) in G is even (resp., odd) then for each R (V,E ) k+1 V= { v : { G (V^)) , and consider the intersection graph k+1 (resp., , induced by the sub k-trees G V} and (S.-.w^) G G (V ) k (resp., { (resp., (B.-.S^) G E ) if k+1 3Gi n 3G- ^ 0 (resp., 3G' D 3C'- ^ 0) . Then, following the lead of, for example, Kolen and Tamir ; (forthcoming), one can use Proposition 4.1.4 to demonstrate that both G and k G k + 1 are chordal graphs. By combining Theorem 4.1.1 , 4.1.2 and the fact that we can construct an 0(n ) 2 G k and G k + 1 are chordal graphs time algorithm for generating an R k-cable distance decomposition of the vertex set of a k-tree. Indeed, Theorem 4.1.3 (V,E) Proof The R-cable distance decomposition problem can be found in a k-tree in 0(n ) 2 G = time . If R is even (resp., odd) we construct the clique-intersection graph G k By Theorems 4.1.1 and 4.1.2 , a minimum clique cover in G k or G k + 1 (resp., G* + 1 ). provides us with a solution to the decomposition problem. The overall complexity of an algorithm which generates the decomposition can be established as follows. From Theorem 4.1.1 (resp., 4.1.2) it follows that for an even (resp., odd) R , (v , v t •) G G* Thus, the clique-intersection graphs (resp., G k (v , { (resp., 59 Vj) G* + 1 G G* + 1 ) if and only if d (v , c { ) Vj < R . ) will be at hand after all cable distances, d (v , Vj) , for a l l v , Vj i n e i V have been found. t other vertices The k-cable distances from a vertex t> to a l l 4 v, v £ V, can easily be computed i n linear time. Indeed, we initially set dciy^v) — 2k — 1 for all u £ A«y'(«,-) . Then, we simply successively build up the k-tree G so that whenever a vertex v, v £ V , is added to a current sub-k-tree, the construction of G d (u,-,u) = e Adj(v)^ ( ' ) m a x c c u (resp., G * ) takes 0 ( n ) time. Since G f c + 1 2 graph, its minimum clique cover can be found in Vi ^ ' Thus, u (resp., G * k + 1 ) is a chordal 0(n) time, see, for example, Gavril (1972) . Therefore, the complexity of the algorithm is dominated by the construction of G * (resp. G * which takes 0(n ) time. ) • 2 4.2 + 1 k-Cable Diameter of a k-Tree Let G = (V, E) denote by D ,D c = c be a k-tree, \ V\ = n , in which a l l edge weights are equal to one, and ^(^21^3) — m a x v . .£V ^(i c V v i j) » ^ v k-cable diameter of G . In this n e section we develop a linear time alogrithm for finding a longest k-cable, d (v ,v ) c diameter, D , of a k-tree. 2 3 , and the k-cable Our algorithm is similar to Handler's (1973) algorithm for finding a c longest path in a weighted tree. Before introducing the algorithm, we need to recall some notation introduced in Section 4.1. For any non adjacent pair of vertices shortest k-cable KP(v , Vj) t v it v p { a n d C t . Further, any (k+l)-clique i separates C(v , Vj) v T (. i> j) C C(v ,Vj) «- , «• £ V, the extended k-path, v T,( i> j) v v jt T KP(Vi,Vj) (resp., k-clique p , induces a Q ) contained in p into two sides (components), one of which could be possibly empty, ( ?-' vt,Q ( i> i) res C v r v a n d C Vj,Q ( i> j)) v p v ' not containing V j and V{ , respectively . Theorem 4.2.1 Let v 1 be any k-leaf of a k-tree G = (V,E) , and let v 2 60 be any vertex i n G such that m a Proof: Let . v) . Then, D = d (v ,v ) . x 2 v c 2 £ — max^^ dc(v ,v) c ydc(v , x v d (v , v ) Let v , v 4 T p and KP^jV^) 2 c 2 3 Further, let be any pair of vertices in 5 V. lt T , is in KP[y^,v^) T^, T and p G V be such that d (v ,v ) c 2 d (v , v ) < c 4 d (v ,v ). 5 with the lowest index such that 2 T^, exist since v± is a k-leaf and = 3 c T . We will assume, without loss of generality, that 1 3 3 with the highest indices such that 2 be the (k+l)-clique in KP(v ,v ) v ) . Note that v We will show that be the (k + l)-cliques in KP(v v ) and Further, let KP(y , T, 1 P 2 3 is in p < p' . T^„ is in T^,, exists since v 2 is a k- leaf. Now, we need to consider two cases. Case 1: p" > p . B y definition of T , and T^,, and since p " > p', we have that f is contained in KP(v , v ) . Thus, by the construction of v 2 4 3 ^(^,T>2^ ))> W(C 3 and by the construction of v 2 1= W(C V T (v v ))n lt x W(C 2 rfe(» ,t;3) 2 2 (4.1) 4 we have that : W(C. Let we have : (v ,v )) T T ,, v = ( " i ' "2)) > W(C ^ (v ,v )) T d> 2 p'' (4.2) 5 Then, by (4.1) and (4.2) K.Dj)). T > , , v )). T ^ . . T . K . ^ ) ) 3 + + W(C W(C K,* )) - / 2 T (4.3) 2' p' T Jv ,v )) 2 4 - I. We further claim that W(C T^V^V,)) + W(C 61 T (v ,v )) n 2 4 - I > d (v ,v ) c 4 5 . (4.4) Indeed, if p < p ' then T , is in KP(y , ^4) and (4.4) is satisfied as equality. Otherwise, p = p ' . 2 Then, i f T , is not i n KP{v , v) 4 (4.4) clearly holds, while i f T , is i n KP(v , 5 contained i n at least one of the two k-paths generality, we can assume that KP(v ,v ) 2 T , is i n KP(v , and 4 Q^, is in KP(v , . 5 Without loss of d (v , v ) > d (v , v ) . c 2 3 c 4 5 T , is i n KP(v , 2 v ) . Let Q^, be 3 u ) and having the highest index among all such x k-cliques. B y the construction of v 2 4 p " < p ' . In this case we clearly have that the k-clique i n T , such that KP(v ,v ) T^, is 5 v ) , which was shown above to imply (4.4) . W e 2 conclude therefore by (4.3) and (4.4) that i f p " > p ' then Case 2 r; ) then 4 2 we have that : 3 ( v„Q W C , ( « 2 . » 3 ) ) W > ( C v n ( («2,«4)) • (4-5) Further, by the construction of v , (4.2) holds. Now, by (4.2) and (4.5) , 2 dc(v ,v ) 2 = 3 W(C Q (v ,v )) 2 + W(C 3 T ( ,v ))) Vl 2 (4.6) ^ >2^4)) + p 4 ^ r ( ^ , 4 o p We claim that ^ , ,0 ( C 4 Indeed, i f p < p ' , not in KP(v 4 f W 2,»4)) T , is i n KP(v , 2 + mC^r ( « ! , ! % ) ) > (4-7) rfe(«4,»6)- t> ) and (4.7) is satisfied as equality. If p = p ' and T^, is 4 , « ) , then (4.7) is clearly satisfied. Otherwise, p = p ' and T , is i n KP(v , 5 4 In this event, similar to the proof in Case 1, we can assume without loss of generality that 62 v) . 5 T , is in KP(v ,v ) 2 , which was shown above to imply (4.7). We conclude that (4.7) holds, which completes 4 the proof. • Now, as explained in the proof of Theorem 4.1.3, computed in linear time which implies, by Theorem 4.2.1, that in linear time. 63 d^t^,^) D c and = d (v ,v ) c 2 3 d (v ,v ) c 2 3 can be can be computed Chapter V NC ALGORITHMS FOR RECOGNIZING PARTIAL 2-TREES AND 3-TREES In this chapter we introduce the notion of a k-separator (k > 2) of an n-vertex graph G = ( V, E) . Formally, a k-separator is a set of vertices S, \S\ = k , which induces a partition of V \ S into sets V\ and V 2 connects a vertex in satisfying (i) with a vertex in j Vj| < (k/k+\)n , i = 1,2, and (ii) no edge in E V • We prove the existence of a k-separator for partial 2 k-trees and construct, a linear time algorithm for generating such a separator in k-trees. This algorithm can be used to construct a balanced binary decomposition tree of a k-tree in 0(n logn) time. W e further derive other separation properties of partial k-trees which are used to construct a balanced decomposition of an embedding of a k-connected partial k-tree into a k-tree when 2,3. Finally, we develop parallel algorithms for the recognition of partial k-trees when k = 2 , 3 . These algorithms require k = k = 0(log n) 2 time and use, respectively, 0(n ) 3 and 0(n ) 4 processors. For 2 and 3 our algorithms improve considerably the processor bound of Bodlaender's (1988) 64 general algorithm for the recognition of partial k-trees, which would require, respectively, and 0(n ) 0(n ) processors for these cases. 13 The chapter is organized as follows. In Section 5.1 we study k-separators of partial k-trees and describe an trees. O(nlogn) algorithm for constructing a balanced binary decomposition tree for k- In Section 5.2 we obtain additional separation properties of partial k-trees, and show that they can be used to construct a binary balanced decomposition of an embedding of a k-connected partial k-tree when k = 2 and 3 . In Section 5.3 we develop N C algorithms for the recognition and embedding of a 2-connected (resp., 3-connected) partial 2-trees (resp., 3-trees), and in Section 5.4 we develop an algorithm for recognizing partial 3-trees which are not necessarily 3-connected. 5.1 k-SEPARATORS Let G = (V, E) set of vertices S, be a partial k-tree (k > 2) with of cardinality |5| = | V\ = n . A k-separator of G is a k , which induces a partition { V^, V } 2 of V \ S satisfying \V \ t < n, i = 1,2, (5.1) and no edge in E connects a vertex in V x with a vertex in V 2 (5-2) Observe that a k-separator extends the notion of a 2-separator defined for series parallel graphs (i.e. partial two trees), see, e.g., Hassin and T a m i r (1986) . 65 Theorem 5.1.1 Every partial k-tree contains a k-separator. Moreover, for a k-tree a k-separator can be constructed in linear time. Proof: of Since any k-separator of a k-tree G — (V, E) is also a k-separator of every partial graph G, it is sufficient to prove the existence of a k-separator for k-trees. For that purpose, we construct below a linear time algorithm for finding a k-separator of a k-tree G . The algorithm follows a reduction process until reaching, for the first time, a k-leaf vertex corresponding set of descendant vertices, D(K ) V , of the k-clique K v for which the induced by Adj(v) , contains v at least | n distinct vertices. Formally, the algorithm has two steps. Step 1 We initially set D(A) = 0 for all k-cliques A of G. In general, let v be a k-leaf which is currently being considered for elimination in the reduction process. Let Adj(v) = { « 1( u k } and V(Kj) denotes the vertex set of a graph A. K v , and = Adj (v) U {v} \ {«,}, Then, update D(K ) V j = V(K ) where V = V(A) , the set of descendant nodes of |D(i(\,)| as follows: D(K ) V \D(K )\ V = k (U k = £ IKKJ)) U D(K ) U V |Z)(tf,.)l + \D{K )\ V i=l 66 W + 1. (5.3) (5.4) If I Z > ( ) | < | n , we continue with the reduction process; otherwise, we go to Step 2 where the k-separator is produced. Observe that Step 1 will terminate whenever n > 3k . If n < 3 k every minimal separator of G is a k-separator. Step 2 We need to distinguish between two cases. J2\ ( j)\ D Case 1 K + 1 > g»- j=l Let Vj = D(Kj) 7, be such that and let , j = I , - , *, and V = V \ {(U* k+1 | V. j = max. , , JK,-|. J = l , • ••,k+l = 1 VA U Adj(v) U > } } , We will prove that the set of vertices J s, S= is the required k-separator. Further, ( Adj(v) \ _ [_ V(K,) if 1= {V where V} lt 2 k+l otherwise V\ = V, and V = V \ (V 2 t U 5) is the required partition of V \ S satisfying (5.1) - (5.2) . Indeed, by assumption, Y<) \ j\ V =1 = Y?l \ (K j)\ D =1 > i» ~ !> w h i c h coupled with £+1 E y - i I^jl = n — (^+1) implies that V \ k+1 < n - ( i + 1) - (§n - 1) < \n. Moreover, since v is the first node encountered by the reduction process for which 67 (5.5) l-D^u)! > I n , we have that 1101 < h , j= k. 3 (5.6) Thus, by (5.5) and (5.6) \V,\ = Furthermore, j t?" | = | K , | > - — x \ V <§»<E£I > * > 2 . ^ , which implies that \ < n - k - 2 By the definition of , V S , and there is no edge in E 2 (5-7) n — ^ I < j ^ and 5 we also have that with endpoints i n V 1 n . V nV 1 and V 2 2 (5.8) = • Thus, 5 <D,V \JV =V\ 1 2 is the required It- separator. Case 2 J \D(Kj)\ + 1 < | n. i=i We will prove that i f Case 2 holds then D(K ) is the required k-separator. Let denote the set of descendant nodes of K„ just before it was updated by (5.3), which V resulted with D(K ) . V |D(iir„)| > | n , and construct the new sets B y assumption, 1 V = li'j-x D(Kj) U {v} and V = x 2 \V \ < | n . Further, \V \ < | n , since otherwise Step 1 would have 1 terminated earlier. Now, let V V\ (V S = Adj(v) 2 x = V± if | ^ | > | V 1 and V 2 l = V 2 otherwise, and let V — U S) , where 5 = Adj(v) . Since | V \ < § n, i = 1,2, we have that { 68 2 Moreover, by (5.4) 1^1 + 2 mar ( | V \, | V | ) > \ n . Since | | V " V I^J = + \ V \ = n — k we derive 2 x \D(K )\ > § n , which implies that \V \ = 2 2 | < n - J t - i n < j|-jn, k> 2 . Again, by the definition of V\ , V 2 and 5 we also have that 0 and there is no edge with endpoints in V\ and ^ U V 2 = V \ S , V \ fl V" = 2 V . 2 The above algorithm will produce a k-separator for a k-tree in linear time since Step 1 will be executed at most n — k times, (5.3) and (5.4) require constant time for each iteration and Step 2 requires constant time. Let S into • G = ( V, E) be a k-tree and S a k-separator of G which induces a partition of {Ki,^} that satisfies (1) and (2) . induced, respectively, by V\ U S and Then, the subgraphs G ^ U 5 ) G recursively until we end up with k-cliques. That rooted binary tree in which the root v represents the graph of q 2 in T then q x and 2 2 entire decomposition can be represented by a balanced binary decomposition tree, q G(V Uff) V U 5 are also k-trees which can be similarly decomposed. We can proceed in this manner to decompose ?! and and V\ 2 T, which is a G , and if some vertex q is a parent are sub-k-trees of q obtained by the above decomposition of q . Corollary 5.1.1 G Let G = (V,E) b e a k - t r e e . Then, a balanced binary decomposition tree, T, of can be constructed i n O(nlogn) time. 69 Proof: Let L denote the subset of vertices in vertex in L has / edges. The leaves of T are T such that the path from the root of T to a k+l cliques and there are at most n — k of them. Thus the number of vertices in all subgraphs of G represented by elements in L is bounded by TI + k(n-k) . That implies that, the construction of k-separators of subgraphs of G represented by vertices in L takes 0(n) time. The proof then follows since T is, by (5.1), at most deep, i.e. the path from the root of T to any of its leafs contains at most 5.2 0(log n) 0(log n) edges. SOME SEPARATION PROPERTIES OF PARTIAL k-TREES We derive in this section some separation properties of partial k-trees into k-trees which will be used later to develop N C algorithms for the recognition and embedding of partial k-trees into ktrees when k = 2 and 3 . Lemma 5.2.1 V\S Let G = (V, E) be a graph and S a separator of G which induces a partition of into {V , 1 V} such that 2 0 < \S\ = I < k , \ V U S\ > k , i = 1,2, and the subgraph { of G induced by S, G(S), is an /-clique. Then G is a partial k-tree if and only if the subgraphs Gj = G(V 1 Li S) and G 2 = G( V U S) induced, respectively, by 2 V U S x and V 2 U S are partial k-trees. Proof: If G is a partial k-tree then since G± and k-trees. O n the other hand, assume that E-i) and G subgraph of 2 = (V 2 G t and U S , E ), 2 G x and G G 2 2 are subgraphs of G they are also partial are partial k-trees and let G x = (V 1 U S , respectively, be their embeddings into k-trees. Clearly, G(S) is a G . Therefore, there exist fc-cliques K 2 x 70 and K 2 contained, respectively, in G and l G and such that both 2 i • • •) and since and x denote the nodes in consider the graph i = / + 1 K G obtained from K contain the 2 l ^ i ^ ) and G = (V, E / = 0, we simply choose for are contained in Then, it is easy to see that G and x K x and K such that G .) • 2 S C S x C V we will denote by 2 G(S For a graph ; K^S^) 2 which is augmented with all arcs between pairs of nodes of S Lemma 5.2.2 Let G = (V, E) i = 1,2. G 2 Then, = G(V 2 Proof: U S; K({s ,s })) 1 v{ \i i) v s x 2 joining and 2 2 V ^ 0 and 2 { | V U 5 | > k, { ^({^I,* })) , i 2 with x p(^i,s ) 2 Thus, suppose that Sj and s, 2 v x 6 V x G is a partial k-tree. 2 contracting the edges along p(si, Thus, G(V 2 s) 2 U S; respectively, in the subgraph s x and G( 5 2 U S). in would yield a 2-clique with a vertex set ,s »)," 2 71 Since V ^ x and two disjoint paths, p(*>i,Si) form a simple path, p(si,S2)' between G is contractible to x = 1,2, are partial k-trees then, by using Lemma 5.2.1 we G is a partial k-tree. v x are partial k-trees. 2 is two-connected, there exists a vertex p(v ,s ) , S S , S — { s j , s } , a separator of x If G(Kj U 5 ; G x if they are missing in G . x V \ S into { V , V } such that x S, G is a partial k-tree if and only if the subgraphs G = G( V U S ; K({ s , s })) can conclude that and G — (V, E) and subsets the subgraph of G induced by be a two-connected graph and G which induces the partition of and G is a k-tree, and in the above proof any two k-cliques which 2 We will use in the sequel the following notation. 2 after the addition of the edges («,-,«•) , G is a partial graph of G , it follows that G is a partial k-tree. (Note that in the degenerate case, when S k 2 2 Jfc , j — I + 1 , •••, k and j > i. v l+l K(iif ), respectively, that are not in S, and \J E ) 1 /-clique G(S) . Let v , which implies that G(V 2 and Therefore, 1 U S), S = G ( K U S; 0 and {si,^}- ^({sj,s })) 2 is a partial k-tree. well. Analogously, we obtain that G(V U S; K({si,s })) 1 is a partial k-tree as 2 • Lemma 5.2.3 separator of and Let G = (V,E) be a triconnected simple graph and G inducing a partition of | Vj U 5| > Jfc, « = 1,2 . V \ S into Then, G { V , V} 1 S, S = { u , « , u }, a x such that 2 2 3 | Vj \ > 2 , i = 1 , 2 , is a partial k-tree if and only if the subgraphs G( V,- U S; iT(5)) , i = 1 , 2 , are partial k-trees. Proof: If G( Vj U 5 ; are partial k-trees then, by using Lemma 5.2.1 we can conclude that so is G . So, assume that of v , v 1 G , there exist at least three vertex disjoint paths between separator and G G is a partial k-tree and let be in 2 v x x and v 2 in G , and since 5 is a | S\ = 3 , at least two of these paths are contained in G( V U S) . Therefore, since x is assumed to be a simple graph, these two paths form a cycle C in G( V U S) with at least 3 1 vertices. B y the triconnectivity of G there exist 3 vertices, say ~s , S 1 disjoint paths in V . B y the triconnectivity G(V , "sO , ?2( 2 > "* 2) > Ps( 3 > ^3) ( s U S) , such that 1 1 . 2 , '.\ , respectively. identify s t with s p,(Sj ,Tj) i = 1,2,3, s o m e t for i = 1,2 ,3 , 3 , in C and vertex possibly degenerated to a single vertex) intersect with Clearly, if we contract edges in the paths "s , and T 2 C only i n nodes T j , i Pi(s , T ) t f respectively, we create a cycle , i — 1 , 2 , 3, C' that contains s , s , s . Again, appropriate contractions of edges in C ' will create a 3-clique K(S) . Thus, 1 2 3 is contractible to G( V U S ; #(5)) and we conclude that 2 Analogously, we can show that G(V 1 U S ; K(S)) G( V U S ; if(5)) 2 is a partial k-tree. and G is a partial k-tree. • We note that the above separation properties of partial k-tree imply the existence of a balanced decomposition tree, T , of an embedding of a biconnected (resp., triconnected) partial 2- 72 tree (resp., 3-tree) and q G into a 2-tree (resp., 3-tree). The root, r , of T is the graph G, and i f q x are sons of 2 r G ( l ^ U S; i^(5))) , where in T 5 then q x (resp., g ) is the graph 2 is a two-separator (resp. 3-separator of G(V 1 U 5 ; K(S)) (resp., G) satisfying (5.1) and (5.2), and whose existence follows from Theorem 5.1.1. The biconnectivity (resp., triconnectivity) of G implies that G(V r U S; K(S)) and G(V 2 U S; K(S)) are biconnected (resp., triconnected). Thus, i f they have sufficient number of nodes, they can be decomposed in a similar manner. In general, the leaves of the decomposition tree T are biconnected (resp., triconnected) 2trees (resp., 3-trees) which are not necessarily further decomposable in the same manner since they have less than 9 (resp., 20) nodes. 5.3 NC ALGORITHMS FOR RECOGNITION OF PARTIAL k-TREES FOR k = 2 AND 3 In this section we present NC-algorithms for recognizing a partial 2-tree (resp., connected partial 3-tree) graphs three- G and finding its embedding into a 2-tree (resp., 3-tree). Without loss of generality, we assume here and in Section 5.4 that G is a simple graph. Algorithm 5.1 Procedure BBD(G,a,L) Input A two-connected (resp., three-connected) simple graph G = ( V, E) . Output a = 1 if G is a partial 2-tree (resp., 3-tree), and a = 0 73 otherwise. Further, i f a = 1 then the output L contains an embedding of G into a 2-tree (resp., 3-tree). Step 0 Set a = 1 and 1 = 0. Step 1 (1.1) If \E\ > 2n - 3 (resp., 3n - 6) set a = 0 and exit . (1.2) Else, i f | Vj < 9 (resp., 20) check i n constant time whether (resp., 3-tree). If yes, find an embedding, G is a partial 2-tree G, of G into a 2-tree (resp., 3-tree), let L = L U {G} . Else, set a = 0 and exit . Step 2 Else, for each pair (resp., triple) of distinct vertices S = {siiS } 2 (resp., S = {s\,s ,s }) 2 3 of V, i n parallel, find a l l the connected components of G (V \ S) and denote their vertex sets by Vj : j = 1, ••• , r (2.1) If \ Vf\ for some r^ > 1. g > l\V\ (resp., |V/| > ||V|) for some ; = 1, ••• , r reject s 5. If all the pairs (resp., triples) S were rejected set a = 0 and exit. (2.2) Else, i f l\V\ < \Vf\ < \\V\ and for some j, (2.3) 1< j < r M = Vf U S and x Else, for an unrejected S compute q, = a binary search to find Set M = u j x (2.4) , set g (resp., \\V\ < \Vf\ < \\V\) for some = 1 x = 0 or a n BBD(G(M l ; K(S)),a x \\V\ 2 > ' = ^» (resp., Vf). ' s • r a n d \\V\ < q < n , L) t and BBD(G(M ; K(S)),a ,L ). 2 2 2 = 0 set a = 0 and exit. Else, set L = L U L . E x i t . x 74 a PP^ v \\V\). U S. 2 2 l^/l n for which \\V\ < q < Vf U S and M = (V\Mj) C a l l i n parallel either a Ylj<i M = (V \ 2 If 5 Theorem 5.3.1 graph Algorithm 5.1 recognizes whether a two-connected (resp., three-connected) simple G= (V, E) with | V\ = n is a partial 2-tree (resp., 3-tree) and produces an embedding of G into a 2-tree (resp., 3-tree) in 0(hg n) time using 0(n ) 2 Proof: 3 (resp., 0 ( n ) ) processors. 4 We first show that the steps of Algorithm 5.1 are valid. If (1.1) in Step 1 is valid then, since every 2-tree (resp., 3-tree) has exactly 2n — 3 (resp., 2n — 6) edges, it follows from Lemma 5.2.2 (resp., Lemma 5.2.3) that G is not a partial 2-tree (resp., 3-tree). If all pairs (resp., triples) in Step 2 were rejected, G does not contain a 2-separator (resp., 3-separator) and then, by Theorem 5.1.1, G is not a partial 2-tree (resp., 3-tree). 5.2.3) we can conclude that triconnectivity) of G G Thus, by Lemma 5.2.2 (resp., Lemma is not a partial 2-tree (resp., 3-tree). The biconnectivity (resp., implies the biconnectivity (resp., triconnectivity) of the minors G(M ; K(S>)), i = 1,2, created in (2.2) and (2.3) of Step 2 respectively. Therefore, by Lemma { 5.2.2 (resp., Lemma 5.2.3), G G(M ; K(S)), i i=l,2, is a partial 2-tree (resp., 3-tree) if and only if all the minors created in Step 2 are partial 2-trees (resp., 3-trees). Next, we will show that Algorithm 5.1 requires processors. 0(log n) 2 time and 0(n ) 3 (resp., 0(n )) 4 In Step 1, (1.2) can be performed in constant time using, for example, the sequential algorithm for the recognition and embedding of partial 2-trees (resp., 3-trees) into 2-trees (resp., 3trees) of W a l d and Colbourn (1983) (resp., Arnborg and Proskurowski (1986)). components of G(V\ S) can be found, by the parallel algorithm of Shiloach and Vishkin (1982), in O(logn) time and using 0(n + m) 0(n) . Since there are 2 Step 2 requires 0(n ) 3 A l l connected 0(n ) processors, where (resp., 0(n )) 3 m = \E\ . Note that in our case m = pairs (resp., triples) to be considered simultaneously, (resp., 0 ( n ) ) processors. Further, in Step 2, (2.3) takes 4 75 O(logn) time using 0(n ) processors in order to compute partial sums, q , and to perform a binary search on them. t Since in (2.2) and (2.3), \M \ < §|V| { terminate after performing at most (resp., \M \ { O(logn) < \\V\), i = 1,2, nested calls of Procedure BBD(G,a, algorithm recognizes whether a two-connected (resp., three-connected) graph G (resp., 3-tree) and delivers in L time using 0(.n ) (resp., 0(n )) 3 an embedding of processors. 4 G Algorithm 5.1 will L). Thus, our is a partial 2-tree into a 2-tree (resp., 3-tree) in 0(log n) 2 • Note that in Algorithm 5.1 we have restricted G to be biconnected (resp., triconnected). However, the recognition of partial 2-trees which are not necessarily biconnected can be easily carried out by a slight modification of Algorithm 5.1. Indeed, we can find all biconnected components of G using the parallel algorithm of Tarjan and Vishkin (1985) in O(logn) 0(n) processors. time with If G does not have biconnected components, then it can be decomposed by zero or one separators into subgraphs of cardinality less than or equal to 3. Then, since every graph on 3 vertices is a partial 2-tree, Lemma 5.2.1 implies that G is a partial 2-tree. Otherwise, we perform Algorithm 5.1 on all biconnected components of G. B y Lemma 5.2.1, only if all biconnected components of requires 0(log n) 2 time and 0(n ) 3 G are partial 2-trees. G is a partial 2-tree i f and Clearly, the modified algorithm processors. The recognition of partial 3-trees which are not necessarily three-connected requires a major modification of Algorithm 5.1, which is developed in the next section. 5.4 NC-Algorithm for Recognizing Partial 3-Trees 76 We develop in this section an NC-algorithm for recognizing a partial 3-tree which is not necessarily 3-connected. The performance of this algorithm is identical to that developed in Section 5 for recognizing and embedding 3-connected partial 3-trees. That is, it requires <3(n ) processors. 4 0(log n) time and 2 However, its description is somewhat more involved and it depends on some new separation properties which are developed below. First, we need to introduce a new definition. For two disjoint paths p = Pi( , i) and v s x Vi — P ( > ) u 2 s G = (V,E), m 2 having only the vertex v in common, the path p = p(k, 1) will be called a bridge path between p± and p 2 p originates at some node k in py, otherwise vertex disjoint with p Lemma 5.4.1 of v { and terminates there exists a vertex with Sj, j = 1 , 2 , 3 . among the paths p(v ,Sj), t If for j= G 1,2,3, implies that if tree. K x with a vertex of and three disjoint paths V . Assume that for 2 p(t) ,s ) , i J j = 1,2,3, which is contained in G ( V , U 5 ) , then and G( V U S ; K(S)) 2 joining G is contractible to G( V U S; K(S)) x G ( ^ U 5 ; ^(5)) , i = 1 , 2 . and p(v ,s ) , i J j= 1 , 2 , 3 , for i G( V U S ; #(5)) . Thus, if 2 O n the other hand, L e m m a 5.2.1 G( V U S ; K(S)) , i — 1,2, are partial k-trees then t G is a partial k- are partial k-trees. The existence of a bridge path between some pair of the paths is a partial k-tree, so are but p is i = 1 and 2 there exists a bridge path between a pair of paths r = 1 and 2 imply that v, 2 t tree if and only if G( V U 5 ; K(S)) Proof: 2 be a separator of G = ( V , E) inducing a partition { Vy, V ) 6 V t I in p , I ^ 2 3 v at vertex p . s} 2 v, V \ S such that no edge in E connects a vertex in = 1,2 i and t Let S = {s ,s , 1 k ^ if G must also be a partial k- 0 Lemma 5.4.2 Let S = { s , s , s : 2 3 } be a 3-separator of a 2-connected simple graph 77 G = ( V, E) which induces a partition {V , V } of x edge in E connects a vertex i n vertices v { V \ 5 such that 2 < | 2 | < | | V | , t = 1 , 2 , and no Vy with a vertex i n V . Assume that for i = 1,2 there exist 2 G V,- and three disjoint paths p(v ,Sj) , j = t 1,2,3, joining v t with vertices in 5 . If for « = 1 or 2 there exists no bridge path between any pair of paths among the paths p(v ,Sj) , { j = 1,2,3, which is contained i n {1,2} , {v , Sj} G(V U S) i then for some is a separator of G which induces a partition t j G {1,2,3} {V[, V } of 2 and i G V\{vf,Sj} such that j L | y | - 2 < | V / | < l\V\. Proof: Assume, without loss of generality, that there is no bridge path between any pair of paths among the paths s(v), s(v) in S \ G(V\ 1 G S, and a path from Now, any node {s(v)}. {«(*>), %}) p(v,~s(v)), or to v v, v Since G is connected, for any s(v), x and p(v,s(v)) and p(v ,~s(v)), x E V there exists a node x ^ v , must be in some connected component of {s(v)}. x Indeed, otherwise there must exist a path, v to a node ~s(v) , ~s(v) G S \ {«(*>)} , which does not pass through either But, the paths p(v ,s(v)) S\ v v i n G which does not pass through nodes p(v,s(v)), € V and which does not contain i n G from s(v) . between 1,2,3. p(v ,Sj),j= p(v,J(v)) i n G induce a bridge path i n G(V U S) 1 which is a contradiction. x Next, for < = 1 , 2 , 3 let C denote, respectively, the union of all connected components of i G(V\ {*>i,S(}) which do not contain any node i n S\ {s } t . We claim that the sets C ,t G t { 1 , 2 , 3 } , are mutually exclusive. Indeed, from the 2-connectivity of G and the definition of the sets C it follows that i f v G C,- , i G { 1 , 2 , 3 } , t s^) , s G 5 , which does not pass through t {1,2,3} and i ^ p(fli,S;) and where j, p(v!,Sj), the paths p(v,s ) { and and v 9^ v , then there exists a path x {v^} U S \ {s,} . Thus, i f v G C,- D Cj , ij G p(v,Sj) i n G would induce a bridge path between which is a contradiction. Thus, we have that V(C ) denotes the set of nodes in C . Let \V(Cj)\ t t 78 ^ ^ 1 V^C*)! = = 1 1^1-1, = max{ \ V(C )\ : t = 1 , 2 , 3 } , and t set V[ = V(Cj) and and thus, \V[\ > V' = V\ - Clearly, 2 2. ( F U { t ) , sA) . Since 5 , 1 1 V(C ) C ^ is a 3-separator, | V \ | > \\V\ , t = 1 , 2 , 3 , and thus \V[\ < t - 3 • We use the above separation results to construct an NC-algorithm for recognizing a partial 3-tree. Algorithm 5.2 Procedure Input REC{ G, A simple graph Output a — 1 if Step 1 a) G = (V, E). G is a partial 3-tree and a = O otherwise . Find all biconnected components of G . If G has no biconnected components, set and exit. Otherwise, perform in parallel procedure components Procedure G^ = ( V ^ , ^ ) REC\(G, of G . If any a t RECl(G , Input A simple biconnected graph (V,E). Output a = 1 if G is a partial 3-tree and a = 0 otherwise . Step 0 a = 1. Step 1 79 a,) for all biconnected = 0 set a = 0 and exit. a) G = i a = 1 (1.1) If IJE7| > 3n - 6 , set a = 0 and exit (1.2) Else, if | V\ < 36 check, in constant time, whether G is a partial 3-tree. If G is not a partial 3-tree set a = 0. Exit . Step 2 S — {si,s ,«3} Else, for each triple of distinct vertices °f 2 V, in parallel, find all connected components of G(V \ S) and denote their vertex sets by for some r ,r , s > 1. g (2.1) Vf, j = If\Vf\> l\V\ for some j =!,••• , r , reject 5. If all triples S are g rejected, set a = 0 and exit. (2.2) Else, if set Mi = (2.3) \\V\ < \Vf\ < f | V | for some ^' ' ^' " ' 5 ' = r 1 = 5 U a n and for all S d a PPi v for t = 1,2, z ^ j = 1, • • • , r s ( U Vf :j< n) and M G(M t j , z , j € {1,2,3} . 2 G(M 2 (3.2) C 1 ) 2 # 0 , C 2 ) 3 # q t = x \ {*,-,*j}) which do not contain Denote by C] j 2 If , compute = (V \ M ) U 5 . connected components, and let C^j = C)^ U C ^ for all {i,j} (3.1) $ binary search to find an n for which \ \ V\ < a Find, in parallel, connected components of {SJ,SJ} 1 < j < r , 2 817 < II V| . Set ¥ Step 3 j, Vf U S a n d Af = ( V \ V ? ) . Else, for an unrejected ^><jl S and for some 0 and C 0 let the union of all such € {1,2,3} , i ^ j • = G(M ; #(5)) and G two distinct pairs {i,j} and 1 ) 3 ^ S\ G t X 2 = ; K(S)). Else, if there exist at U {Pi ?} = {1)2,3} such that least Cj t 80 = 0 and C , P q {p,q ^ 0 proceed as follows: },{i,j} (a) inCi, )| + If 2 \ V(C , )\ \ 5"|, 1^(^1,3)1 < (b) find U (3.3) V\C\j) 2 c ) S ,} ; t G { 1 , 2 } , | V ( C * ) | + |V(C2,s)l + I K ^ s ) ! components of 1 ) 2 = 3 G 2 ) 3 = 0 and C 1 3 = 0 find, t Vj(v, s) , j — 1, t m(u,s ) > t ••• , m ( u , s ) } , reject the pair t If all pairs {f,St }, t G { 1,2,3} and ,,})). v G K , and denote their ( ; G(7(C£,,) x in parallel, connected ••• , m ( u , s ) , for some |V -(«,Sj)| > Q\V\ for some j, j € {I, l ^ t \ S\ G = k G( K \ {s , «}), for all t € { 1 , 2 , 3 } and vertex sets by (o) ) | } and let k>l 2 0 , J ) 3 V(C )) U K , s , } ; K({s , and G = G{{V\ t S C = 1>a tf({s , ,})) Else, if G ^ - , then 2 2 f >3 2 is the vertex set of component I V(C*,i)l = m a * { | V ( C * , ) | , | K ( C i , ) | , | V ( C {5 | K ( C ? , ) | + |KCS )I + and G = G(M ; Jf(S)) . 1 Else, if for some \MAS\ and 3 where let G = G(M ; K{S)) x inCi, )l < + 2 3 1. If {f,s }. t v G V , were rejected let G = G ( M j ; x K(S)) and G = G(Af ; K(S)) . 2 (6) 2 Else, if = - Vj (v,s ) t G(Af' ; 1 (c) 2 < | 1^ ( v , s ) | for some U { v, tf({t;,sj)) G { 1 , ••• , m(v, t s } t and M and G = ; 2 Else, for an unrejected pair = > 2 V \ compute t s) t set Af^ t and let G q, = ^ t < J | V , - (v, s )\, <||V|. t M ! = {*;,«,} U ( U l A 1 GiM , 1 (3.4) = (»,*,) : j < ; /£-({!),«,})) and G = G(M C a l l in parallel 2 RECl^, a) x 0 set a = 0. Exit. 81 I 2 1;) M , ;K({v,s })) and = (V l 2 VH\) I = t l , - - - , m(v,s ) , and apply a binary search to find n for which ^ | V\ -2 < Set = x . tf({i/,6-,})) {v,s } Vj (v, s ))}, U {v,s } t , G = x . t REC1(G , 2 a ). 2 If either a x = 0 or a 2 Theorem 5.4.1 Algorithm 5.2 recognizes whether a simple graph G = (V ,E) with | V | = n is a partial 3-tree i n 0(log n) time using 0 ( n ) processes. 2 Proof: 4 W e will first prove the validity of Algorithm 6.1. If, i n Procedure G is REC(G,a), found not to contain biconnected components, then it could be decomposed by zero or one separators into subgraphs of cardinality at most 4 . 5.2.1 implies that Since every graph on 4 nodes is a partial 3-tree, Lemma G is a partial 3-tree. The validity of Step 1 i n in Algorithm 5.1. If all triples were rejected i n Step 2 , Theorem 3.1, G is not a partial 3-tree. In Step 3, i f C j ^ t biconnectivity of 0 for some G t a) was explained does not contain a 3-separator and by Otherwise, i n Step 2 algorithm 5.2 finds a 3-separator. i ^ j, then {SJ,SJ} G and Lemma 5.2.2 it follows that augmented with edge (s ,Sj) REC1(G, is a separator of G, and by the G is a partial 3-tree i f and only i f G is a partial 3-tree. T h u s , by L e m m a 5.2.3, i f (3.1) holds, then G is a partial 3-tree i f and only i f G{M ; K(S)) and G(M ; K(S)) are partial 3-trees. If (3.2) holds X then, by L e m m a 5.2.2, we can augment must exist vertices G(M ) i , i=l,2. G(M ), v, t 2 G with edge (p,q). v G M \ S , i = l , 2 , and three disjoint paths from t t Thus, by Lemma 5.4.1, since (p,q ) v to a l l s G S in { is a bridge path both i n G(M ) 1 and G is a partial 3-tree i f and only i f G(M ; K(S)) and G(M ; K(S)) are partial 3-trees. 2 1 2 On the other hand, i f 3.2b) holds then, by Lemma 5.2.2, G(V(Ci,,) U{ s , s, k } ; A'({ s , s,})) and G((V\ k trees. If (3.3) holds, then for each in Therefore, i f 3.2a) is valid, there G(M ) from { i = 1,2 G is a partial 3-tree i f and only i f 1^,,)) U and for each ; K({s ,s,})) k v GM { are partial 3- there exist three disjoint paths v to all nodes i n S . Therefore, by Lemma 5.4.2, i f all pairs are rejected i n 3.3a), there must exist a bridge path both in GiMy) and G(M ) 2 82 satisfying the stipulations i n Lemma 5.4.2 . Then, by G(M 2 G(M 1 I Lemma 5.4.1, G is a partial 3-tree if and only if G(M ; K(S)) X and ; K(S)) are partial 3-trees. Otherwise, by Lemma 5.2.2, G is a partial 3-tree if and only if ; K({ v, s })) and G(Af* 5 ^({v,s })) t 2 a r partial 3-trees. e t Next, we will show that algorithm 5.2 requires 0(log n) time using 0 ( n ) processors. A l l 2 4 biconnected components can be found in Step 0, using the parallel algorithm of Tarjan and Vishkin (1985), in O(logn) time using 0(n) processors. In Step 1, (1.2) can be carried out in constant time using, for example, the sequential algorithm for recognizing partial 3-trees of Arnborg and Proskurowski (1986). The connected components in Step 2 can be found by the parallel algorithm of Shiloach and Vishkin (1982) in 0(n ) 3 triples S 1 O(logn) time using 0(n ) which do not contain 5\{s,-,s^} processors, and since there are O(logn) time and G (V\ 0(n) 0(n ) 2 pairs and q^ > Step 3.2b) O(logn) Since there are time and In Step 3, connected components of 0(n ) 4 O(logn) time using t O(n) processors. can be found in {s , v) to be considered simultaneously, Step (3.3) t t processors. Further, 3.3c) takes | K (CX )| > in (2.3) O(logn) G(M \ {s;,Sj}) {s , v}) processors. Finally, observe that in (2.2) | V ? | > | | F | , 3-separator, in processors. Step 2 requires can be found in Similarly, connected components of 0(n + m) processors to compute, in Step 2.3, partial sums 2 and perform a binary search on them. requires time with to be considered simultaneously, processors. It takes q O(logn) O(logn) q„ > \\V\ V\ — 2 . Therefore, we can have at most O(logn) algorithm 5.2 would terminate in 0(log n) time using 0(n ) 2 4 83 time using s )\ t > ±\V\ nested calls of RECl(G,a), processors. 0(n) 0(n ) 2 a n d , since S is a Further, in Step 3.3, \ Vj{v, jf time using • - 2 and Bibliography A . V . Aho, J.E. Hopcroft and J.D. Ullman, "The Design and Analysis of Computer Algorithms," Addison- Wesley, Reading, 1974 S. Arnborg, Transactions "Reduced State Enumeration: Another on Reliability 27 (1978), 101-105. Algorithm for Reliability Evaluation,'" IEEE S. Arnborg, " O n the Complexity of Multivariable Query Evaluation," F O A Rapport C 20292-D8, National Defence Research Institute, Stockholm, Sweden (1979). S. Arnborg, "Efficient Algorithms for Combinatorial Decomposability - A Survey," BIT 25 (1985), 2-33. Problems on Graphs with Bounded S. Arnborg, D . G . Corneil and A . Proskurowski, "Complexity of Finding Embeddings in a k-tree," SIAM Journal on Algebraic and Discrete Methods 8 (1987), 277-284. S. Arnborg and A . Proskurowski, "Characterization and Recognition of Partial k-Trees," Numerantium, 47 (1985), 69-75 Congressus S. Arnborg and A . Proskurowski, "Characterization and Recognition of Partial 3-trees," SIAM on Algebraic and Discrete Methods 7 (1986), 305-314. Journal S. Arnborg and A . Proskurowski, "Linear Time Algorithms for NP-hard Problems on Graphs Embedded in k-trees," Discrete Applied Mathematics 23 (1989) 11-24. S. Arnborg, A . Proskurowski and D . Corneil, "Forbidden Minors Characterizations of Partial 3-trees," CIS-TR-86-07, University of Oregon, July 1986. N . W . Bern, E . L . Lawler and A . L . Wong, " W h y Certain Subgraph Computations Require Only Linear Time," Proc. 26th Ann. IEEE Symp. on Foundations of Computer Science (1985), 117-125. C . Berge, "Graphs," 2 USA, 1985. n d revised edition Amsterdam, North Holland Publishing Company, NY, NY, C . Bird, " O n Cost Allocation for a Spanning Tree: A Game Theoretic Approach," Networks 6 (1976), 335-350. H . L . Bodlaender, "Classes of Graphs W i t h Bounded Tree-Width," Utrecht, The Netherlands, November 1986. RUU-CS-86-22, Rijksuniversiteit H . L . Bodlaender, "NC-Algorithms for graphs with small treewidth," RUV-CS-88-4, Rijksuniversiteit Utrecht, The Netherlands, February 1988. N . Chandrasekharan and S.S. Iyengar, " N C Algorithms for Recognizing Chordal Graphs and k-Trees," Technical Report 86-020, Department of Computer Science, Louisiana State University, 1986. C . J . Colbourn and A . Proskurowski, "Concurrent Transmission in Broadcast Networks," Proc. Conf. Automata, Languages, Programming, Springer-Verlag L N C S 172 (1984), 128-136. 84 Int. : D . G . Corneil and J . M . K e i l , " A Dynamic Programming Approach to the Dominating Set Problem on k-Trees," SIAM Journal on Algebraic and Discrete Methods 8 (1987), 535-543. D . G . Corneil and Y . P e r l , "Clustering and Mathematics 9 (1984), 27-39 Domination in Perfect Graphs," Discrete Applied G.Cornuejols, J.Fonlupt and D.Naddef, "The traveling Salesman Problem and Some Related Integer Polyhedra," Mathematical Programming 33 (1985), 1-27 A . Edenbrandt, "Combinatorial Problems University, Ithaca, N Y , July 1985. in Matrix Computation," P h . D . Thesis at Cornell A . M . Farley, "Networks Immune to Isolated Failures," Networks 11 (1981), 255-268. A . M . Farley and A . Proskurowski, "Networks Immune to Isolated Line Failures," Networks 12 (1982), 393-403. L . R . Ford Jr. and D . R . Fulkerson, "Flows in Networks," Princeton 1962. University Press, Princeton S. Fortune and J . Wyllie, "Parallelism in Random Access Machines," Proceedings ACM Symposium on Theory of Computing, (1978) 114-118. of the 10th N.J. Annual M . C . Golumbic, "Algorithmic Graph Theory and Perfect Graphs," Academic Press, New York, 1980. M . R . Garey and D.S. Johnson, Computers Completeness, Freeman, San Francisco (1979). and Intractability: A Guide to the Theory of NP- F. G a v r i l , "Algorithms for M i n i m u m Coloring, M a x i m u m Clique, M i n i m u m Coloring by Cliques and M a x i m u m Independent Set of a Chordal G r a p h , " SIAM Journal on Computing 1 (1972) 180-187. D . Granot, " A Generalized Linear Production Model: A Unifying Model," Mathematical 34 (1986), 212-223. Programming D. Granot and F . Granot, " A Fixed-Cost Spanning-Forest Problem," University of British Columbia, Working Paper No. 1235, March 1987. D. Granot and G . Huberman, " M i n i m u m Cost Spanning Tree Games," Mathematical (1981) 1-18. Programming 21 S.L. Hakimi and A . T . A m i n , " O N the Design of Reliable Networks," Networks 3 (1973), 241-260 G. Y. Handler, "Minimal 287-293. Location of a Facility in an Undirected Tree Graph," Transp. Sc. 7 (1973), F . Harary, " G r a p h Theory," Addison Wesley, Reading, Mass., 1969. R. Hassin and A . T a m i r , "Efficient Algorithms for Optimization and Selection on Series-Parallel Graphs," SIAM Journal on Algebraic and Discrete Methods 7 (3), July 1986, 379-389. D.S. Johnson, "The NP-Completeness Column: A n Ongoing Guide," Journal of Algorithms 434-451. 85 6 (1985), A . Kolen and A . T a m i r , "Covering Problems" Chapter 6. in Discrete Location and D . B . Mirchandani, eds., John Wiley, New York (forthcoming). S.C. Littlechild, " A Simple Expression for the Nucleolus in a Special Case", Game Theory 3 (1974), 21-29. Theory, L . R . Francis International Journal on N . Megiddo, "Computational Complexity and the Game Theory Approach to Cost Allocation for a Tree", Mathematics of O.R. 3 (1978), 189-196. B . Monien and I . H . Sudborough, "Bandwidth-Constrained NP-complete Problems," Proceedings of the 13th Annual ACM Symposium on Theory of Computing, New York (1981), 207-217. E . M . Neufeldt and C . J . Colbourn, "The Most Reliable Series-Parallel Networks," Dept. of Computer Science, University of Saskatchewan, TR83-7 (1983). C . H . Papadimitriou and K . Steiglitz, "Combinatorial Optimization Algorithms and Complexity," Prentice Hall, Inc., 1982. N . Pippenger, " O n Simultaneous Resource Bounds," Proc. 20th Ann. IEEE Symp. on Foundations Computer Science (1979), 307-311. of A . Prodon, M . Liebling and H . Grb'flin, "Steiner's Problem on Two-Trees," R O 850315, Department of Mathematics, E P F Lausanne, Switzerland, March 1985. A . Proskurowski, "Separating Subgraphs in k-trees: Cables and 49 (1984), 275-285. Caterpillars," Discrete Mathematics R . L . Rardin, R . G . Parker and M . B . Richey, " A Polynomial Algorithm for a Class of Steiner Tree Problems on Graphs, " I S Y E Report Series J-82.5, Georgia Tech., August 1982. N . Robertson and P . D . Seymour, " G r a p h Minors II: Algorithmic Aspects of Tree W i d t h , " Algorithms 7 (1986), 309-322. N . Robertson and P . D . Seymour, "Disjoint paths - A survey," SIAM Discrete Methods 6 (1985), 300-305. D . J . Rose, " O n Simple Characterizations of k-Trees," Discrete Mathematics Journal on Journal of Algebraic and 7 (1974), 317-322. J . C . Sheperdson and H . E . Sturgis/'Computability of Recursive Functions," Journal of the ACM 10, (1963), 217- 255 Y . Shiloach and U . Vishkin, " A n O(logn) Parallel Connecting A l g o r i t h m , " Journal of Algorithms (1982), 57-67. 3 K . Takamizawa, T . Nishizeki and N . Saito, "Linear-Time Computability of Combinatorial Problems on Series-Parallel Graphs," Journal of the ACM 29 (1982), 623-641. R . E . Tarjan and U . Vishkin, " A n Efficient Parallel Biconnectivity A l g o r i t h m , " SIAM Computing 14 (1985), 862-874. 86 Journal on P . Tseng, "Parallel Computation for Edge Weighted Network Problems on Series-Parallel Graphs," Working Paper #1240 , University of British Columbia, December 1987. J . Valdez, R . E . Tarjan and E . L . Lawler, "The Recognition of Series-Parallel Digraphs," SIAM on Computing 11 (1982), 298-313. Journal U . Viskin, "Implementation of Simultaneous-Memory Access in Models That Forbid It," Journal of Algorithms 4, (1983), 45-50 A . W a l d and C . J . Colbourn, "Steiner Trees, Partial 2-trees, and M i n i m u m IFI Networks," Networks 13 (1983), 159-167. 87
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- On some problems on k-trees and partial k-trees
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
On some problems on k-trees and partial k-trees Skorin-Kapov, Darko 1989
pdf
Page Metadata
Item Metadata
Title | On some problems on k-trees and partial k-trees |
Creator |
Skorin-Kapov, Darko |
Publisher | University of British Columbia |
Date Issued | 1989 |
Description | The objective of this thesis is to investigate some structural and algorithmic properties of k-trees and partial k-trees. A k-tree can be constructed from a k-complete graph by recursively adding a new vertex which is adjacent to all vertices of an existing k-complete subgraph. Partial k-trees are graphs embeddable in a k-tree with the same vertex set. They are natural generalizations of forests and series-parallel graphs which are the first two members of the hierarchy of partial k-trees. The many applications of k-trees and partial k-trees have motivated their study from both an algorithmic and a theoretical point of view. For example, k-trees arise in reliable communication network design problems (Farley (1981), Farley and Proskurowski (1982), Neufeld and Colbourn (1983), Wald and Colbourn (1983), Colbourn and Proskurowski (1984)) and in the study of the complexity of certain type of queries in a relational data base system (Arnborg (1979)). Moreover, the class of k-trees is special in the sense that many problems, which are NP-complete for arbitrary graphs, are solvable in polynomial time when restricted to k-trees or partial k-trees (Arnborg and Proskurowski (1989)). In Chapter 2 of the thesis we analyze a fixed cost spanning forest (FCSF) problem, defined over a graph G, in which some customers require service that can be generated at some facilities' sites. Both the set of customers and facilities' sites are represented by nodes in G. There is a fixed cost for opening each facility and a cost for delivering the service from open facilities to the customers. Customers do not necessarily have to receive the service directly from an open facility, but possibly through other intermediate customers. We develop a linear time algorithm for solving the FCSF problem when the customers and potential facilities' sites are located on a series-parallel network or, equivalently, a partial 2-tree. We further analyze a related cost allocation problem, in which we seek a fair method for allocating the cost of providing the service to the customers. We formulate this cost allocation problem as a cooperative game and show that, in general, the core of this cooperative game may be empty. However, we provide a sufficient condition, which can be verified in polynomial time, for the nonemptiness of the core of this game. A k-tree can be reduced to the k-complete graph by sequentially removing k-degree vertices with completely connected neighbors. We use this reduction process to develop, in Chapter 3, efficient algorithms for several optimization problems on k-trees and partial k-trees. In particular, we develop a linear time algorithm to find shortest simple paths from a given vertex to all other vertices in a k-tree, we compute the diameter of a k-tree with equal edge lengths in linear time, and we construct an O(n[sup k+2]) algorithm to solve the Simple Plant Location problem in an n-vertex partial k-tree. In Chapter 4 we present a new characterization of a k-path between two vertices u and v, in an equal weight k-tree G, by means of minimal k and k+1 cliques with respect to certain partial orders defined on the collections of all k and k+1 cliques in a k-tree. We use it to develop an O(n²) algorithm to decompose a vertex set V of a k-tree G to a minimum number of components, such that for any pair of vertices i and j in the same component, the cable distance between i and j is bounded by a positive integer R. We also compute the k-cable diameter of a k-tree with equal edge lengths in linear time. In Chapter 5 we derive some separation properties of partial k-trees and use them to develop NC algorithms for recognizing partial 2-trees and 3-trees. Explicitly, we prove the existence of a k-separator in a partial k-tree graph and construct a linear time algorithm that finds such a separator in k-trees. This algorithm can be used to obtain a balanced binary decomposition of a k-tree in 0(n log n) time. We derive some other separation properties of partial k-trees and use them to construct a balanced decomposition of an embedding of a k-connected partial k-tree when k = 2 and 3. Finally, we construct NC algorithms for the recognition of a partial k-tree for k - 2 and 3, which run in O(log²n) time using, respectively, O(n³) and O(n⁴) processors. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2010-10-18 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
DOI | 10.14288/1.0098333 |
URI | http://hdl.handle.net/2429/29288 |
Degree |
Doctor of Philosophy - PhD |
Program |
Business Administration |
Affiliation |
Business, Sauder School of |
Degree Grantor | University of British Columbia |
Campus |
UBCV |
Scholarly Level | Graduate |
Aggregated Source Repository | DSpace |
Download
- Media
- 831-UBC_1989_A1 S57.pdf [ 4.26MB ]
- Metadata
- JSON: 831-1.0098333.json
- JSON-LD: 831-1.0098333-ld.json
- RDF/XML (Pretty): 831-1.0098333-rdf.xml
- RDF/JSON: 831-1.0098333-rdf.json
- Turtle: 831-1.0098333-turtle.txt
- N-Triples: 831-1.0098333-rdf-ntriples.txt
- Original Record: 831-1.0098333-source.json
- Full Text
- 831-1.0098333-fulltext.txt
- Citation
- 831-1.0098333.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0098333/manifest