UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

On some problems on k-trees and partial k-trees Skorin-Kapov, Darko 1989

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

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

ON SOME PROBLEMS ON K-TREES AND PARTIAL K-TREES By DARKO SKORIN-KAPOV B. Sc The University of Zagreb, Yugoslavia, 1978 M. Sc. The University of Zagreb, Yugoslavia, 1983 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF T H E REQUIREMENTS FOR T H E D E G R E E OF DOCTOR 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 OF BRITISH COLUMBIA May 1989 © Darko Skorin-Kapov , 1989 In presenting this thesis in partial fulfilment of the requirements for an advanced degree at the University of British Columbia, I agree that the Library shall make it freely available for reference and study. I further agree that permission for extensive copying of this thesis for scholarly purposes may be granted by the head of my department or by his or her representatives. It is understood that copying or publication of this thesis for financial gain shall not be allowed without my written permission. Department of C 0 H M f t C g ^ The University of British Columbia Vancouver, Canada Date Jt(UA 2 0 , MSl  DE-6 (2/88) ABSTRACT 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 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(nk+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 0(n2) 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 N C 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 N C algorithms for the recognition of a partial k-tree for k — 2 and 3, which run in 0(log2n) time using, respectively, 0(n3) and 0 (n 4 ) processors. in 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 : 13 1.5 Summary of the Results 17 II 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 III 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 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 V N C A L G O R I T H M S F O R R E C O G N I Z I N G P A R T I A L 2 - T R E E S A N D 3 - T R E E S 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 B I B L I O G R A P H Y 80 v List of Figures Figure 1.1 Two drawings of the same graph 3 Figure 1.2 Partial 3-tree G 14 Figure 2.1 a: A n S P M G 21 b: A binary decomposition tree T of G 21 Figure 22 G = (V, E) 32 vi List of Tables Table 1.1 Upper bound of kx for special classes of graphs 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 PhD 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, Dr 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 k-trees 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 k vertices by the repeated addition of vertices, each of which is connected with k edges to 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 line-and-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 represent 1 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 Tamin (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 minimum 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 minimum k (Arnborg (1979)). Moreover, partial k-trees have arisen in some real world problems. As 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 graph-theoretic 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) , where V is a set { vx , v2 , • • •, vn } of elements called vertices (or sometimes nodes) and E is a family (el , e2 ,• • •, e m ) of elements of unordered pairs of V, called edges (or sometimes arcs). If an element e = (u,v) of E appears more than once in the family 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 in 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. An edge list simply contains an entry for each edge (u,v) . Representation by edge lists is the most appropriate for the algorithms studied in the thesis. In the case of the graph in Fig 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 i and edges by the index k the 4 incidence matrix of an undirected graph G , A = (aik) 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 — (aik) is defined as follows: ( +1 if i is a head of a directed edge k — 1 if i is a tail of a directed edge k 0 otherwise The adjacency matrix B = (6,j) of an undirected graph G= (V, E) is a matrix with both rows and columns indexed by V and defined as follows : (6 tJ) = / , where / is the number of edges connecting i and j . So 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 = (6t- -) is defined as follows : 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 G is defined as the set of all vertices adjacent to v . The degree of a vertex v is the cardinality of its neighborhood. In the case of a directed graph D = (V, E) we say that the directed edge (u,v) enters v and leaves u . If W is a set of vertices such that v £ W and w £ W, then (v,w) is said to enter W and to leave V \ W. If W C V, then 6~(W) denotes the set of edges in E entering W and 6+(W) the set of directed edges in E leaving W. We let 6~{v) and 6+(v) stand for 6 -({x/}) and 5 6+({v}) and are called in-degree of v and outdegree of v , respectively. A path in a graph G = (V,E) , Pv0vt (or p(v0,vt)) connecting v0 and vt is a sequence of the form ( v0 , tx , vx , e 2 , vt_x , et , vt ) , where v0 , « t are vertices and ex , ••• , et are edges such that e{ = , u,) € .E 1, for = 1 , 2 t. We refer to v0 , t>t as the endpoints of the path Pv0vt • A path is simple if all its vertices and edges are distimct. If v0 = vt then the path Pv0vt is called a cycle. A cycle without repeated edges or vertices (except for the endpoints) is called a simple cycle. A directed path from vQ to vt in a digraph D = (V, E) is 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 puv for any two vertices u and v in D. A graph G1 = (V',E') is a subgraph of G = (V,E) if V1 C V and Ef C E. If E1 is the family of all edges of G which have both ends in V , then G1 is said to be induced by V1 and denoted by G'(V') . A partial graph of G contains all its vertices and a subset of its edges. A graph G is an embedding of the graph G1 if it can be obtained from G1 by addition of some edges. A clique in the graph 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 Kp . A subset 5 of V is a separator of a graph G = (V, E) if the subgraph G( V \ S) induced by V \ S has two or more connected components. A graph G = (V, E) is called k-connected (or sometimes k-point-connected) if the cardinality of any minimal separator of G is at least k . 6 A contraction of an edge e = (u,v) in G = (V, E) is obtained by removing e = (u,v) from E and identifying the vertices u and v . A graph G is contractible to a graph (?' if G ' can be obtained from G by a sequence of edge contractions in G. Edge extraction of e in G results in a graph G \ e with the same vertex set as G and the edge family E \ {e} . A graph H is a minor of a graph G if it can be obtained from G by a finite number of contractions and edge extraction operations. Let Gx = ( ^ I I-^I ) a n ( i G2 = (V2, E2) be any two graphs. G2 is homeomorphic to Gx if there exist mappings & and 0 with being from Ex , onto a set of paths of G2 and 0 from V t into V2 , such that for each edge (v,w) G Ex , the path \P((v,w)) has ends <9(a) and 0(w) , and no two paths , ti^)) and !^((t)2 , w 2)) s n a r e a vertex except possibly an end of paths. Let $ = {5j , S2 , • • •, Sn} be a family of distinct nonempty subsets of S whose union is S. The intersection graph of f is a graph whose vertices are identified with sets in f, with Sf 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 e 6 E has a 7 'length' (weight) w(e) . For any u , v £ V, the length of the path p(u,v) is the sum of its edge weights. Distance between two vertices « 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 (F,c) , where F is the set of feasible points and c is the cost function, c : F —• R1 . The problem is to find an f £ F for which c{J) < c(g) for all g £ F. 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 (dtj) . The problem is to find a spanning tree, (V, E) on n vertices that has minimal total edge length. (By a spanning tree we mean an undirected graph (V, E) that is connected and has no cycles.) For this example F = | a l l spanning trees ( V, E) , with V = {1,-••,»}} and c:(V,E)^ £ ( l | i ) e £ d{j . 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 n 3 , or simply 0(n3) . Generally accepted measure of efficient performance of an algorithm in the 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 c(f) < L . The class of recognition problems that can be solved by a polynomial time algorithm is called P . A recognition problem A is in the class N P if for a yes instance x of A , there exists a certificate for x , whose length is bounded by a polynomial in the size of x and which can be checked for validity in polynomial time. Clearly P is contained in N P . However it is an outstanding open problem whether P = N P . It is strongly suspected that P ^ N P . Let A and B be two recognition problems. It is said that A reduces in polynomial time to B i f and only if there exists a polynomial time algorithm -4. for A that uses several times as a subroutine at unit cost a (hypothetical) algorithm S for B . The algorithm .A is called a polynomial-time reduction of A to B . A recognition problem A polynomially transforms to another recognition problem B if, given any string x , we can construct a string y in polynomial time (in the size of x) such that x is a yes instance of A if and only if y is a yes instance of B . A recognition problem A € N P is said to be NP-complete if all other problems in N P polynomially transform to A . Problem A is called NP-hard if it can be shown that all problems in N P polynomially reduce to A 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, N P , NP-completeness 9 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) is a weighted graph, such that each edge e £ E has a 'length' (weight) w(e) € R1. For a given pair of vertices u , v £ V find the length of a shortest simple path p(u,v). Longest Path Let G — (V, E) be a weighted graph, such that for each edge e £ E, w(e) £ R+. For u , v £ V find the longest simple path p(u,v). Steiner Tree Problem Given a connected undirected weighted graph G = ( V, E) and a set of vertices D , DC V ; find a tree T in G , whose vertex set contains D with a minimum total edge-weight. Maximum Independent Set For a given graph G — (V,E) find the maximum size of an independent set. (An independent set in a graph G = (V, E) is a subset V1 C V such that for all u , v £ V1, the edge (u,v) is not in E.) 10 Minimum 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 G = (V, E) be an undirected weighted graph with w(e) > 0 for all e € E. W i t h each vertex v £ V associate a fixed cost , cv , to open a facility , and a transportation cost function gv( • ) which is a nondecreasing function of its argument. Each vertex is viewed as both a potential facility site as well as a customer. Find a subset of vertices F, F C V, that minimizes : 11 1.3 SPECIAL CLASSES OF GRAPHS We 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 k i f and only if for some spanning tree T of G, in each biconnected component of G there are at most k edges of G that are not in T. Let G = (V, E) be a graph, with 1 = n . A linear ordering of G is a bijective mapping / : V —• { 1 ,• • • , n } . A linear ordering / of G is said to have bandwidth k if k = maxu t' £^l f(u) ~ 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 K5 or K3j3 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 (or 1-outerplanar) graphs are graphs that do not contain graph homemorphic to K4 or K2f3 • (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 k > 2 , a graph is k-12 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 minimum 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) with | V\ = n is a chordal graph if and only if there exist an ordering of the vertex set V , say vx, v2 , • • •, vn , such that in the vertex induced subgraph G( V \ U { Vj : j = 1, i — 1}) of G , i > 1 , vt and its adjacent nodes 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 G is ^-decomposable if and only if either it has at most k + 1 vertices, or there is a separator 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 Kei l (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 Gavri l (1972) in which polynomial algorithms were developed for solving the problems of finding maximum independent set, minimum coloring, maximum clique and minimum 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 G — ( V , E) is a partial k-tree for some k (in the worst case 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 k not exceeding kr . 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 + 1 Graphs with bandwidth at most k Jb Series parallel graphs 2 Outerplanar graphs 2 Halin graphs 5 k-outerplanar graphs 3* - 1 chordal graphs with max. clique size k * Table 1.1 Upper bound of kt for special classes of graphs 15 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 it 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^ , s2 , s 3} of the partial 3-tree G in Fig 1.2 to a 3-clique, we obtain a graph which contains K5 as a subgraph and thus is not a partial 3-tree. Fig 1.2 Partial 3-tree G 16 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 Wald and Colbourn (1983) for k = 2 and Arnborg and Proskurowski (1986) for k = 3 ) . This set of reductions yield 0(n) 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 in 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(nk+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(n2) 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 read-only input tape, a write-only output tape, a program and a memory (Aho et.al. (1974)). Fortune and Wyll ie (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 in 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 O(logn) time. Chandrasekharan and Iyengar (1986) improved his processor bound to 0(n4) . Tseng (1987) constructed an algorithm that recognizes whether a given 2-connected graph is series-parallel in 0(log3n) time using 0 ( n 4 ) processors. 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(n3k+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 (FCSF) problem , defined over a network G = (V, E) in which the set of communities D , D C V, require service that can be generated at a set of facilities' sites M, M C V. There is a fixed cost for opening each facility and a cost for delivering the service from open facilities to the communities. Any 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 is expressed in terms of number of vertices and k 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(nk+2) algorithm to solve the Simple Plant Location problem in an n-vertex partial k-tree. In chapter IV 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 k paths in C(u,v) and the k-cable distance between two vertices u and v is the length of the shortest k-cable between these two vertices. A k-path is an alternating sequence, KP , of distinct k and k + 1 complete subgraphs KP = < Qx , T2 , Q2 > T3 , • • • , Tn , Qn > , starting and ending with a k-clique and such that T{ contains exactly two of the distinct k-cliques Qi_i and Qt . A k-path between vertices u and v in a k-tree 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 G . Further, for an equal weight k-tree G = 20 ( V , E) and a positive integer R , R > 2k — 1 , we develop an 0(n2) algorithm to decompose the vertex set V into a minimum number of components, V 1 , V2, ••• , V\ such that for any pair of vertices i and j , i ^ j € V* and < = 1 , • • • , / , the cable distance between i and j does not exceed R . We also develop in chapter IV 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 (k > 2) of an n-vertex graph G = (V, E) . A k-separator is a set of vertices S, \S\ = k , which induces a partition of V \ S into sets Vx and V2 satisfying : (i) | V.-1 < J^J n , i — 1 , 2 , and (ii) no edge in E connects a vertex in V1 with a vertex in V2 • We prove the existence of a k-separator for partial 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 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(log2n) time and use, respectively, 0(n3) and 0(n4) processors. 21 Chapter II FIXED COST SPANNING FOREST PROBLEM Let G = (V, E) be a connected undirected network with a set of vertices V and a set of edges E. The subset D , D C V , is a set of communities and M , M C V , is a set of potential facilities' sites. 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, ct > 0 , for opening facility i G M and a cost c((i,j)) = • > 0 , £ E, i f edge is used to deliver service. The objective is to provide service to the communities in D at a minimum cost. We will refer to the above optimization problem as the Fixed Cost Spanning Forest (FCSF) problem. The F C S F problem is equivalent to the Steiner Tree problem on an augmented network G1 derived from G by adding a new vertex, denoted by 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 G1 is coi = c(- . Clearly, an optimal solution to the F C S F problem can be produced by finding a minimum cost Steiner tree in G1 whose vertex set contains D1 = D U { o } . For the other direction suppose that a connected undirected weighted graph G = (V,E) and a set of vertices D , D C V are given and 22 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 D with the set of communities and we choose an arbitrary vertex in D 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 G1 = (V1\E') is a series parallel graph without loops or parallel edges or, equivalently, it is a partial two-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., Wald 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 (SPM) 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 Qx and Q2 are SPMs with terminals i(Qi) , j(Qi) and i(Q2) > HQ2) 1 respectively, so are the multigraphs obtained by each of the following compositions. Series composition Identify a terminal of Q x , say j(Qi) , with a terminal of Q2 , say i(Q2) • The terminals of the new multigraph are i(Qi) and j(Q2) • Parallel composition Identify one terminal of Ql , say i(Qi) , with one terminal of Q2 , say i(Q2) , and the second terminal of Q1 , j(Qi) , with j(Q2)- 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 in 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 Q1 and Q2 , then G(Q) is submultigraph obtained from G(Q1) and G(Q2) by the respective series or parallel composition. In particular, if Q is the root of T , G(Q) is the multigraph G. 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 SPM. Figure 2.1a: An SPM G Figure 2.1b: A binary decomposition tree T of G An optimal solution , X* , to the FCSF problem specifies the set of facilities Af*, Af* C Af, that are opened at the optimum. Each open facility » , » G Af*, is providing the service to a set of communities through a connected network T,* = (V,*,£,*) , which can be assumed to be a tree. The optimal value of the FCSF problem, associated with X* , is given by : E c< + E E c,*-ieAf* ieAf* 0',*)e£-25 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) . Namely, given a vertex o 6 V and a subset of vertices D C V , find a directed tree T in G , rooted away from vertex o and whose vertex set contains D , such that the total edge-weight of T is minimum. 2.2 A LINEAR TIME ALGORITHM We 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 M , M C V. For 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 SP graph G . Every vertex q of T designates a series parallel subgraph Q — (VQ,EQ) of G , with terminals i(Q) and j(Q) . Each such subgraph Q , except for those corresponding to the leaves of T , is either a series or parallel composition of two subgraphs Q1 and Q2 of G . That is, if the subgraphs Q , Q1 , Q2 correspond to vertices q , q1 , q2 , respectively, in T , then ql and q2 are the two immediate successor vertices of q in T , and and Q2 are said to be the sons of Q . Starting from the leaves of T and proceeding towards its root, for each vertex q of T the algorithm solves certain special cases of the F C S F problem in the corresponding subgraph Q . The solution of these special cases in Q is based on solutions of identical cases in the sons of Q , Ql and Q2 , whose composition created Q , and which were previously obtained by the algorithm. A t the final stage, when q is the root of T, the corresponding subgraph Q coincides with our SP graph 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 SP 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 : IV: /(Q,i(Q),0) , VII : f(Q, UQ ,j(Q)) , X: f(Q,i(Q),i(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 i(Q) ; /(Q,UQ, .) - optimal value of a F C S F problem in Q in which it is required that service is delivered to the terminal i(Q) from some facility UQ , UQ G M D VQ , and f(Q,i{Q), • ) - optimal value of a F C S F problem in Q when a facility can be established at the terminal i(Q) at no cost. Thus, for example, in case VIII we seek the optimal value, f(Q,i(Q) ,VQ) , of the F C S F problem in Q in which a facility is available at i(Q) at no cost and the service is provided to terminal j(Q) from some facility VQ , VQ G M' n VQ where M'= M \ {i(Q)} , and in case X we seek the optimal value , f(Q, i(Q), i(Q)) , of the F C S F problem in Q in which an open facility is available at i(Q) at no cost, and the service is provided to terminal j(Q) from the open facility at i(Q) . Now, let Q = (VQ,EQ) be any subgraph of G associated with'the vertex q of the binary decomposition tree 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 « to v 27 II: f(Q,uQ ,0), V: /(Q,0,i(g)), VIII: f(Q,i(Q),vQ) , XI: f(Q,j(Q),j(Q)) III: f(QJ,vQ), VI : f(Q,uQ ,vQ) , IX: f(Q,i(Q),j(Q)) , 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 f(Q, • , • ) for all Q corresponding to the leaves of the decomposition tree T , for all cases I-XI above. That is, using, for example, complete enumeration we solve the above eleven cases of FCSF problems restricted to the different edges of G . Parallel composition Let Q1 and Q2 be the sons of Q , according to the binary decomposition tree T , such that Q is derived from Qi and Q2 by parallel composition. Then, we identify the terminals of Qi , Q2 and Q in accordance with parallel composition, i.e. i(Q) = i(Qi) = i{Q2) i J(Q) = j(Qi) = j(Q2) and we compute f(Q, . , . ) as follows : I /(Q ,0,0) = min {[/(Qj,0,0) + f(Q2,0,0)] , [/(^, ,0) + f(Q2, i(Q2),0)] , [f(Qi,KQi)J) + f{Q2,VQ2M, lf(Qn<b,vQl) + / ( < 3 2 , M Q 2 ) ) ] , \f(QiAQi)AQi)) + /(02.«g2.«g2)]. lf(Qi,uQlJ(Qi)) + f(Q2,KQ2),KQ2))}, + /(<*W(02).i(C2))], \f(QiAQi)AQi)) + f(Q2,uQ2,J(Q2))}, V(QiAQi)AQi)) + / ( Q 2 , < Q 2 ) . ^ 2 ) ] . Lf(0i,« g i,j(0i)) + /(02,«'(02),«o2)]. \J(QiAQi)*«Ql) + /«?2.«g2.i(02))] }• II f(Q,«Q,9) = m i n { [ / ( Q n ^ . 0 ) + / ( Q 2 , i ( Q 2 ) , 0 ) ] , [ / ( O i , , 0 ) + f(Q2,*q3M . [ / ( Q i . ^ . X G i ) ) + /(Q2. «'(<&). «g2)] . [/(<?!,%> V 28 + / ( 3 2 , * ( Q 2 ) , . \f(Qu*Qi),vQl) + f(Q2^Q2AQi))]. \f(QiAQi)AQi)) + / ( « 2 . « o 2 , « g 2 ) ] , \f(QiAQi)AQi)) + / ( « 2 . « g 2 , j ' ( 0 2 ) ) ] > [ / ( < & .* Q lAQi)) + f(Q2AQ7)AQ2))] > «'(0i) ,« g i ) + f(Q2AQ2)AQ2))\. \f(QiAQi)AQi)) + f(Q2,<Q2),vQ2)}}. / ( Q , 0 , ^ g ) analogous to I I . /(Q,i(Q),0) = min { [/(Qi, i ( Q i ) , 0) + /(Q 2 , i(Q 2 ),0) ] , [/(Qj ^ + f(Q2AQ2)AQ2))], \f(QiAQi)AQi)) + / ( Q 2 . « ' ( % ) , « g 2 ) l . [ / ( Q i , i ( < ? i M Q i ) ) + / ( Q 2 , i ( Q 2 ) , i ( Q 2 ) ) ] , [ / ( Q i , i ( Q i ) , i ( Q i ) ) + / ( Q 2 , i ( Q 2 M Q 2 ) ) ] } • f(Q,$AQ)) analogous to IV . > f(Q,uQ,vQ) = min { [/(Q,,i.^ , vQ) + / ( Q 2 , i ( Q 2 ) , j ( Q 2 ) ) ] , \f(Qi AQi) AQi)) + f(Q2,uQ2,VQ2)], \f(Qi>*QlAQi)) + / ( < 3 2 . ? ' ( < 3 2 ) . ^ 2 ) ] i \f(QiAQi),vQl) + f(Q2,*Q3AQ2))], [ / ( O i . ^ . i C O i ) ) + / ( < 2 2 , i ( Q 2 M Q 2 ) ) ] , [ / ( 0 i , f ( 0 i ) , » g i ) + / ( Q 2 , ; ( Q 2 ) , y ( Q 2 ) ) ] , \J(QiAQi)AQi)) + f(Q2,*<j2AQ2))]. \f{QiAQi)AQi)) + /(Q2,«'(02),«Q2)]}. f(Q,uQ,j(Q)) = min { [ / ( g 1 , « g i + /(Q 2,*(<? 2),./(Q 2))] , [/(Qi, i«?i ) ,J«?i)) + /( 0 2 , «Q2, J'( % ) ) ] } • 29 VIII f(Q,i(Q),vQ) analogous to V I I . I X f(Q, i( Q), j( Q)) =f(Qlt i( Qi), j( Qi)) + f(Q2,«'(Q2), j( Q2)). X f(Q,i(Q),i(Q)) = min { [ / (^ ,{ (QJ ,{ (QJ) + f(Q2,i(Q2),j(Q2))} , [f(Q1),i(Q1),j(Q1)) + / (Oa,« ' (%).«(%))] } • X I f(Q,j(Q),j(Q)) = min { [/(QnKQO.KQj)) + f(Q2,j(Q2),;(Q2))1. [ / (Qi . i (Gi ) , j (« i ) ) + / ( Q 2 , . « ? 2 ) , i « ? 2 ) ) ] } • Series Composition Let Q t and Q2 be the sons of Q, according to the binary decomposition tree, with corresponding terminals i(Q\) , j(Qi) and i(Q2) , j(Q2) > respectively, such that Q is derived from Qx and Q2 by series composition. Then, the terminals of Q are i(Q) = i(Qi) and j(Q) = j(Q2) . (Note that when the composition took place, the terminals j(Q\) and i{Q2) were identified, i.e., j(Qi) = i(Q2)-) We then compute 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 2 , «(Q 2 ) , 0)] , [/(Qi,0,i(Qi)) + /(Q2,««j2>0)]}. II f(Q,uQ,<H) = min {[/(^,1*^,0) + / (Q 2 ,0 ,0 ) ] , [ / ( Q i , ^ , ^ ) + /(32,*(<?2),0)] , [ / ( G i . t ^ X O i J ) + /(g2,«<j2,0)], 30 lf(QiJ(Qi)d(Qi)) + / (Q 2 ,«g 2 ,0)] }• / ( Q , 0 , f g ) analagous to I I . f(Q,*Q)J) = min | [ / ( < ? ! , i ( + / (Q 2 , 0 ,0 ) ] , [ / (Qi , * ( & ) , « Q i ) + / (Q 2 ,* (Q 2 ) ,0 ) ] , \f(QuKQi)M)) + f(Q2,"q2M , [f(Qi,KQi),KQi)) + f(Q2,KQ2)M } • f(Q,®,J(Q)) analogous to IV . f(Q,uQ,vQ) = min[[f(Q1,uQi,9) + / ( Q a . M ^ ) ] , [f(Qi, uQ^, vQJ + /(Q 2,«(<? 2),»Q 2)] - [f(Qi^Ql^Ql) + / (<? 2 , ' (Q 2 M<? 2 ) ) ] , [f(Qi,vQlJ(Qi)) + f(Q2,«Q2,VQ2)}, + / ( ^ 2 . «Q 2.WQ 2)] } • f(Q,uQ,j(Q)) = min { [ / (Qi , t i ^ , 0) + f(Q2, 0,i( Q2))] , [ / (G i , »Ql AQi)) + / ( Q 2 , j ( Q 2 ) , ; ( Q 2 ) ) ] , \f(Qi,«QlAQi)) + f(Q2,uQ2,j(Q2))}, \f(Qi,*Ql,vQ) + / ( Q 2 , i ( Q 2 ) , j ( Q 2 ) ) ] } . f(Q, i(Q), ^g) analagous to VII . f(QAQ)AQ)) = min { \f{Ql,i{Ql),%) + / ( Q 2 , 0 , ; ( Q 2 ) ) ] , [f(QiAQi)^Ql) + f(Q2AQ2)AQ2))\> \f(QiAQi)AQi)) + /(<?2.«'(02).i(G2))], \f(QiAQi)AQi)) + /(02,«Q2,i(02))], \f(QiAQi)AQJ) + 31 /(<?2,XG2),;(%))]}• x f(QAQ)AQ)) = f(QiAQi)AQi)) + /(<?2,*'(<92MQ2)) • xi f(Q,j(Q),j(Q)) = + /(Q2.i(Q2),i(Q2))-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 I-XI for some subgraph Q associated with a vertex q in the binary decomposition tree T. Clearly, after a finite number of iterations we reach the root of T whose associated subgraph coincides with our series parallel graph G . Then, / ( G , 0 ,0 ) is the optimal value of the F C S F problem on G . • Complexity of The Algorithm Lemma 2.2.2 For a SP graph G = (V, E) with n vertices (| V\ = n) , a set of communities DC V and a set of potential facilities' sites 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 requires a constant time. • Comment Berne et al. (1985) have developed a general methodology for constructing linear time dynamic 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 SP 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 £ Rn and S C N , let z(5) = xi ' ^ c o s* aU o c a * i ° n v e c t o r a; in a game (N; c) satisfies 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 € Rn 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. We wil l formulate this cost allocation problem as a cooperative game and analyze its core. Formally, given a F C S F problem, defined on G = (V, E) with a set of communities D C V and a set of potential facilities' sites M C V , we denote by FCSFg , for S C D , the F C S F problem obtained from the original problem by simply replacing D by S. Then, the pair (D ; c) , where c : 2'^' —• R is such that c(0) = 0 and for each S C D , c(5) is the minimum objective function value of FCSFg , is a cooperative game in characteristic function form, to be referred to as the Fixed Cost Spanning Forest (FCSF) 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 G1) , which is known to have a nonempty core, see, e.g., 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 G has a tree structure. Unfortunately, this result cannot be extended to cases when 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) shown in Figure 2.2 below. Therein, V = { 1 , 2 , 3 , 4 , 5 , 6 } , E= { ( 1 , 4 ) , ( 4 , 2 ) , ( 2 , 5 ) , ( 5 , 3 ) , ( 3 , 6 ) , ( 6 , 1 ) } , D = { 1 , 2 , 3 } - is the set of communities and M = { 4 , 5 , 6 } is the set of possible facilities' sites. Further, we assume that c~ = 1 for all G E and that c{ — \ for all i £ M. The core, C , of the F C S F game associated with G is given by: C = { x € R3: «i < 2 , x2 < 2 , x3 < 2 , xx + x2 < 3 , xY + x3 < 3 , x2 + x3 < 3 , xx + x2 + x3 = 5 } . Figure 2.2 G = (V,E) 35 Now, one can easily verify that the core constraints induced by the three two-members coalitions imply that + x2 + x3 < 4ij for any core allocation. Thus, since any core allocation x must distribute the entire cost, i.e., x1 + x2 + x3 = 5 , we conclude that the core of the F C S F game associated with 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). To describe this polyhedral characterization, as applied to our F C S F problem, we first need to replace the graph G = (V, E) with the directed graph G — (V ,E) in which all undirected edges are replaced by two directed edges <i,j> and <j,i> , with associated costs c» = c(<i,j>) = c(<j,i>) = c~ = c- . Then, we construct the augmented network G1 = (V1 ,E*) derived from G by adding to V the vertex o , and to E the directed edges <o,i> for all t G M , with c • = c(< o,i>) = ct . We wil l refer to G1 as the directed augmented network derived from G . Note that finding a minimum cost directed Steiner tree in • G1 which is rooted away from 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> we refer to i as the tail and j as a head of / , and for a subset of vertices S we denote by 8(S) the set of all directed edges having their heads, but not their tails, in S. A subset S , S C V1 , is said to be an admissible cut-set of G1 , if » ^ 5 C V1 , S D D ^ 0 (D is the set of communities) and both subgraphs G '(5) and G'(V\ S) of G' induced by S and V \ S , respectively, are connected. We denote by A^, the set of all admissible cut-sets of G1 . It follows from Prodon et al . (1985) that if the directed augmented network G1 is a series parallel graph, then the incidence vector of a minimum cost directed Steiner tree of G1 , directed 36 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 G is a partial two-tree. Indeed, let the underlying network G be the simple cycle in Figure 2.2 and consider the directed augmented network G1 derived from G . A l l the edge weights in G1 are assumed to be 1 . Then, it is easy to check that the minimum cost directed Steiner tree in G1 , with root 0 and whose vertex set contains vertices E 0 , 1 , 2 ,3 , has a weight of 5 . However x* 6 R+ defined as follows: x* - i (0,6) ~~ 2 ' *(*5,2) = 3 ' X* ' i (6,3) 2 ' x* , = 0 otherwise , is feasible to LP(D) associated with G' and has a lower objective function value of 4.5 . X* - i (0,4) _ 2 ' X* = 1 (4,1) 2 ' x* - 1 (5,3) - 2 • X* - i (0,5) - 2 • X* = i (4,2) 2 • X* - 1 (6,1) 2 ' 37 Nevertheless, LP(D) is still useful for the analysis of the F C S F game. Indeed, Proposition 2.3.1 If the incidence vector of a minimum 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: Let c(Q) denote the optimal value of LP(Q) , Q C D , and consider the cooperative game (D;c) with c(0) = 0 . Then, (2.1) provides us with a generalized linear production game formulation of (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) is not empty. On the other hand, for each Q C D , let c(Q) denote the optimal value of the integer programming problem, IP(Q) , derived from LP(Q) by restricting the nonnegative decision variables therein to 0 — 1 values. Observe that c( Q) coincides with the characteristic function value assigned to Q , Q C D , in the F C S F game. Clearly, c(Q) < c(Q) , Q C D . Moreover, whenever a minimum cost Steiner Tree in G1 , directed away from vertex o and whose vertex set contains D U {o} , solves LP(D) , we have that c(D) = c(D) . 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) is never empty. • 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 minimum cost Steiner tree 38 T , using the algorithm developed in Section 2.2 . Then, we can apply the T-guided algorithm of Prodon et al . (1985) to check if the incidence vector of T is an optimal solution to LP(D) . This wil l be true if and only if the 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. The neighborhood of a k-leaf v is denoted by Adj(v) , and we let Kv denote the k-clique induced by it. Clearly the graph obtained by removing a k-leaf v 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 k-clique, 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 k-cliques. 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 wil l 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(nk+2) time algorithm for solving the Simple Plant Location (SPL) 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). 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 wil l only be concerned with the shortest paths from s to all other vertices v E V. Let v be a k-leaf of G = (V,E) and denote by G1 = (V1,E?) the weighted graph obtained from G by removing v and its incident edges from G and whose edge weights, w'(e) , e E E' , have been modified as follows : 3.1 Single Source Shortest Paths Problem in k-trees 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 . Lemma 3.1.1 d'(i,j) = d(i,j) for all i,j€ V1. Proof: Let i, j £ V1 and assume, on the contrary, that d'(i,j) = w\p[j ) < d(i,j) = w(pi-), where p1 ~ and p$J- are shortest directed simple paths from » to j in G1 and G , respectively, and w'(p' ••) and w(p--) are their corresponding lengths. Let A = { (u,w) £ p1 •• : w'((u,w)) < y y ' w((u,w)) }. Clearly |^ 41 > 1 . If \A\ = 1 then A = {(u,w)} for some u,w G Adj(v) . Then, by replacing (u,w) in p'^- by (u,v) and we obtain the simple directed path p" - in G for which = < w(Pij) i contradicting the optimality of p^- in G . So, we must have that |^4| > 2 . Let ( t t j , a n d ( u 2 « w 2 ) be in A , such that and K 2 are not necessarily distinct. Then, upon replacing (MI,WI) and («2, iu 2) by («i,v) , (f, Wi) and («2 , a) , (t), w 2 ) in p' -j , we obtain a directed path (not simple) p"- in G such that w(p" ) < w(p-j) . Clearly, pj'- contains a cycle, C, in G which contains node v . Since we assumed that G has nonnegative edge weights, upon the removal of C from p"- we wil l obtain a simple path p- in G satisfying wCp ••) < u> (?,•„•) - This contradicts the optimality of p.- , and the proof is y y y complete. • 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 We successively eliminate k-leaves and their incident edges from G while modifying the weights of the remaining edges using (3.1). Since a k-tree has at least two leaves, we can always 42 avoid the elimination of the source node s . The elimination of the k-leaves is continued until we obtain a subgraph Gk = (Vk,Ek) of G , whose number of vertices is just a function of k. For simplicity, we wil l assume that | V * | = k, which can be achieved by letting Gk be a k-complete graph containing node s . Next, we solve the SSSP problem in Gk, whose edge weights were derived by successively modifying the edge weights using (3.1). This can be done in 0(k2) elementary operations, which is constant for a fixed k. Let d(s,u) , u G V*, be the weight of a shortest path from s to u in Gk. By Lemma 3.1, d(s,u) = d(s,u) for all M G V*, where 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 Gk obtained by adding v and all its incident edges (v,u) , u G Adj(v) , to G*. Let Gk have the same edge weights, w(i,j) , as it had in Phase 1. Now, if d(s,v) is the weight of a shortest path from s to v in Gk then d(s,v) = min { d(s,u) + w(u,v) , u G Adj(v) } . Moreover, by Lemma 3.1.1, d(s,v) = d(s,v) and 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) be an undirected graph. The eccentricity of u , u £ V, is ecc («) = max{d(u,v) : v £ 7 } . The diameter of G is D = mar { ecc(«) : u £ V } . In this section we wil l compute the diameter of a k-tree G — (V,E) with equal edge lengths in linear time. The algorithm consists of two phases. In the first phase we wil l follow a reduction process of the k-tree. Initially, we set eccK (a) = 1 for all u £ V(K) and K £ 3G , where 3G is the family of all k-cliques in G (|3G| = (n — k) k + 1 , n > k) , V(K) is the vertex set of the k-clique K and eccK («) is the eccentricity of u £ V(K) 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 Kv , where V(KV) = Adj(v) = { % , • • • , % } , denote the k-clique induced by the neighbors of a k-leaf t>, and for each £ Adj(v) let K j 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, eccv(u) = ecc v(u) , of all vertices 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 : K. K-eccv(uA = max { max ecc '(«,-) , min ecc J(x) + 1 } (3-3) 3 ifr 3 i £ V ( X . ) and we update eccKv(u) , for all u £ V(KV) , eccKv{u) = max { eccv(u) , eccI<v(u) } (3.4) 44 Clearly, in the last step of the first phase we have eccR(u) = 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) the eccentricity of u in the subgraph of the k-tree G induced by V(K) and the complement of the set of the descendant vertices of K in the reduction process. In the second phase we initially set D — max {ecc(u) : M G V(R) } and ecc^(w) = 0 , for all u G V(K) and K G 96 , and follow the reduction process in the reverse order. A t each step we add a vertex v, compute the exact eccentricity of v in G, ecc(v) , and update D as follows : ecc(u) = max { max ecc 3(v) , min eccv(u) + 1 , ueAdj(v) (3.5) and D = max { D , ecc(u) }. (3.6) We further update other eccentricities in the following manner: min ecc *(x) + 1 } , (3.7) and for j = 1 , ..., k , ecc J\v) = max { min eccv(u) + 1 , uCAdj(v) (3.8) and finally 45 ecc v(u) = max { ecc^(u) , 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) steps and each step requires a constant time, the total time required to compute D is 0(n) . Remark 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 V is associated with a fixed cost, cv , to open a facility at v , and a transportation cost function gv(d(v , . )) which is a nondecreasing function of the distance, d(v, . ) , from node v. Each vertex is viewed as both a potential facility site as well as a customer. The Simple Plant Location (SPL) problem problem, defined with respect to 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 c « veF + X) 9v(d(v,F)) , where d(v,F) = min d(v,f) . For general graphs, the S P L problem is veV known to be NP-hard. However, Kolen and Tamir (1986) developed an 0(n2) time algorithm to solve the S P L problem on tree networks and Hassin and Tamir (1986) constructed an 0 (n 4 ) time algorithm to solve this problem on series-parallel graphs. 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 k , can be done in 0(nk+2) 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 V(K) = { «j , u2 ,• • •, uk } . We wil l denote by h(K, fx , f2 ,• • •, fk) the optimal value of the S P L problem restricted to the subgraph G(D(K) U V(Kj) of G, induced by V(K) and all the descendants of the k-clique K in the reduction process followed by the algorithm, with the stipulation that «f. is served by /,• for i = 47 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 , /t , f2 ,• • •, fk ) : A € V, i = 1 , 2 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 Adj(v) — { « ! , • • • ) « * } and denote by Kj the 'side' k-clique whose vertex set is V(Kj) = Adj(v) U {v} \ {uj} , j = 1 k. Let Kv be the k-clique whose node set is Adj(v) . For any side k-clique K j , which was not previously considered, the algorithm first finds the optimal values h(Kj , fa ,-••,/*) for all /,• € V, i  = 1 ,• • •, k . In fact, if we denote by { h r ' h } t n e n ° d e s e t °f V(K j) > t n e n it is easy to verify that for al l (/j ,• • •, fk) , /,• 6 V , « = 1 k , and side k-clique, K;- , not previously considered ife k k' h(Kj , A fk) = E c/, + E 9SiWiJi)) - E cr'.(^') - !) ' (3-10) «=i «=i i = i ' where f{ is the facility serving jt , { // ,• • •, f'k, } is the set of all distinct /,'s appearing in (A > A? >'••)/*) > and <(//) denotes the number of instances that / / appears in (fr , /2 ,• • •, /j.) . Next, we solve the S P L problem associated with the k-clique Kv . As it wil l be shown, the optimal value of the S P L problem, h(Kv , f\ >•, AO » c a n D e expressed in terms of the optimal values, h(Kj , fa A) i associated with the side k-cliques K;- , j = 1 k. First, we need to introduce some notation. We will say that (Ai'iA) is a facility assigment for vertices 48 { ' i >•••> k } if node lj receives the service from facility f.,j= 1 r . Let F = (A A) be a facility assignment for Adj(v) = { « ! , - • • , } , and let V • = V(K •) fl .Adj(i>) , j = 1 fc. Then, the facility assignment F to Adj(v) induces a facility assignment Fj to Vj , specifying for each node in V(K j) , except node i>, the facility providing service to it. Then, one can verify that for any facility assignment F = (A »"••»/*) to Adj(v) = { "1 «* } , , t A(/f, , A / t) = min j h(Kv , A fk) + £ j , (*i - «)) ~ j=i (k-1) gv(d(v,s)) - d S ^ k - l ) + 62) -j=i «=i A' (3.11) + (l-«4,,-)(*-2))] - ( l - * 3 ) [E (*-l) i=i Mrf(«../.)) + E c/;- (*4,i * + i=i ' (*-!))]:« e (jDiKA U { « } U { / 1 , - , / * } } , i= i where 6X = 1 if s ^ { A' >'"•> } and z e r o otherwise and f52 = 1 if s = / ' G { / / , • • •, fki } and <(/,') = 1 and zero otherwise; 63 = 1 if A(if« , A i ""» /* ) = 0 (i.e . if,, was not previously encountered by the algorithm) and zero otherwise , 64 i = 1 if <(// ) > 1 and zero otherwise, i G {1 , k' } . Further, (F- , s) is the facility assignment to V(Kj) which 49 consists of the facility assignment Fj to V • , induced by the facility assignment F to Adj(v) , and v is supplied from s . The set { {[ , •• •, f^ , } and <(/' ) , i = 1 , • • •, kf have the same meaning as in (3.10), and D(K) denotes the set of descendant vertices of the k-clique K. The algorithm wil l terminate after n — k steps with an optimal value to the S P L problem, h(R) , given by h(R) — min { h(R , f\ , 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(nk+2) elementary operations. Proof: The embedding of a partial k-tree into a k-tree requires 0(nk+2) time. The computation of distances between all pairs of vertices requires 0 (n 2 ) time, using the algorithm developed in Section 3.1. We assume that the computation of gv(d(v,x)) , for a given x , requires constant time. Further, in each step of the algorithm we need, in the worst case, 0(knk) time to compute h(Kj,--- ) , using (3.10), for all side k-cliques that were not previously considered by the algorithm. It takes 0(nk+1) time to compute h(Kv ) using (3.11). Hence, the total time to solve the S P L problem on a partial k-tree is bounded by 0(nk+2) + 0(n2) + (n — k) (0(knk) + 0{nk+l)) = 0(nk+2) . • 50 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, V1, V2, •••, V ' , such that for any pair of vertices i and j , i, j € V* and t = 1 , • • • , / , the cable distance, to be defined below, between i and ; does not exceed R . We will refer to this problem as the R k-cable distance decomposition problem. We develop in this section an 0(n2) time algorithm for 51 finding such a decomposition in the special case when G is a k-tree in which all the edge weights are equal to one. First, we need to introduce some new definitions and notation. The k-cable, C(u,v) , denotes a collection of k vertex-disjoint paths between vertices « and v in a k-connected graph. The length 1 of the k-cable C(u,v) , W(C(u,v)) , is the sum of the distances of the k paths in C(u,v) . The k-cable distance, dc(u,v) , between vertices u and v is the length of a shortest k-cable between these two vertices. That is, dc(u,v) = min { W(C(u, v)) : C(u,v) G C(u,u) } , where C(«,D) is the collection of all k-cables between u and v . Apparently, the notion of a k-path, introduced and studied by Proskurowski (1984), plays a major role in the analysis of our decomposition problem. Definition 4.1.1 (Proskurowski (1984)). A k-path is an alternating sequence, KP , of distinct k and k + 1 complete subgraphs KP = < Qr , T2 , Q2 , T3 , • • •, Tn , Qn > , starting and ending with a k-clique and such that T{ contains exactly two of the distinct k-complete subgraphs Q i l and Q{ . It was shown by Proskurowski (1984) that in a k-tree G , the vertices of the minimal subgraphs separating two nonadjacent vertices induce a k-path. Proposition 4.1.1 The k-cable distance between two nonadjacent vertices u and v in a k-tree G 1 Proskurowski (1984) defined the length of a k-cable, C(u,v) , to be the length of a longest path in 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 in 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 w and v . Moreover, if u and v are not adjacent then dc(u,v) = 2 k + t where t is the number of (k+l)-cliques appearing in the unique k-path between u and v in G . (Observe that the number of (k+l)-cliques in C(u,v) may be zero.) Proof: Let C(u,v) be the k-cable induced by the k-path KP(u,v) , KP(u,v) = < Qi , T2 , Q2 , •• > Tn , Qn > , between u and v , and let C'(u,v) be any other k-cable between u and v . By 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 W(C(u,v)) . The construction of the k-path implies that each one of the (fc-f l)-cliques Tt in KP(u,v) contains exactly one edge that belongs to the k-cable C(u,v) . The remaining edges in C(u,v) are (u,i) , i £ Q1 , and (j,v) , j £ Qn . The proof follows since Qx and Qn are k-cliques. • Next, we wil l present an alternative characterization of a k-path which wil l be used in the sequel. First, we need to introduce some additional notation. Let G = (V, E) be a k-tree and let 3G (resp. , %') denote the collection of all k-cliques (resp., (k+l)-cliques) in G. For a vertex U £ V, Q £ % , Q1 £ %' we let S (U) = max „,„.deCv , v) and 6'Cv) = max , ,dcCv,v), 0V ' vCV(Q) v ' Q' vCV(Q') y ' where V(A) denotes the vertex set of A . For each pair vt , vj £ V we define a partial order on 3G , (3G , < „ . „ . ) as follows : for Q1 and Q2 in 3G , Ql <v.v. Q2 if and only if 6Q (v{) < &Q2(vi) a n ( ^ ^ ( ^ j ) — ^Q2^V3^ > f u r t n e r i Qi <viv- Q-x if Qi <vfvj Qi and at least one of the two inequalities is satisfied as a strict inequality. Similarly, using 6Q(*0 , we define the partial orders (3G' , <»{i;.) for all pairs v{ , Vj £ V. Definition 4.1.2 The extended k-path between vertices vt and «• , KP(vt, v •) = 53 < Tx , Qx , T2 , Q2 , •••, Tn , Qn , T n + 1 > , is the k-path KP(v{,Vj) extended with the two (k-t-l)-cliques 7\ and Tn+1 , where V ^ ) = { » J U V(QX) and V(Tn+1) = {Vj} U V(Qn) . Proposition 4.1.2 The extended k-path KP{vi,vf) = < Tx , Qx , •••, Qn , T n + 1 > between vertices and in the k-tree graph 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 We first show that any (k-f-l)-clique that is not contained in KP^v^vf) is not minimal with respect to (3G' , <«,.«.) • Let M be a (k+l)-clique which is not in KP(vt,Vj) , and let x be a vertex in M such that dc(vi,x) = max^^. y^jd^v^v). Observe that x is not a vertex of any (k+l)-clique in KP(vi,Vj) . Now, if KP(vf,Vj) and KP(v{,x) have no (k+l)-cliques in common then it is easy to see that 7\ <vfVj M. Otherwise, let Tp be the (k+l)-clique in KP(vi,Vj) with the highest index such that Tp is in KP^v^x) . Then, dc(vj,x) > m a x v e v ( T ) ^c(vjiv) ' implying that Tp <vtVj M . Next, we wil l show that every (k+l)-clique T in KP(v{,Vj) is minimal. Assume, on the contrary, that there exists a (k+l)-clique M such that M <vtVj T. By definition, it follows that M cannot be in KP^v^Vj) . Moreover, by the above there exists a (k+l)-clique Tp £ KP(vi,Vj) such that Tp <vtVj M. Since (3G' , <vtVj) is transitive, that would imply Tp <«,«J- T, which is impossible. Next, we wil l show that every k-clique which is not in KP(v{, w •) is not minimal. So, let be a k-clique not contained in KP(vt, vfj , and let vertices x x and x2 in M be such that d c K , Z i ) = ™<MveV(M) dc(v{,v) and dc{vj,x2) = maxveV(M)dc(vj,x) . Now, if KP^v^x^) and KP^v^Vj) have no k-cliques in common then Qx <«ivJ- M. Otherwise, we need to distinguish between two subcases. 54 In subcase 1, xx is not a vertex of any k-clique in KP(v{,Vj) . Then, there exists a k-clique, Qp , not necessarily contained in KP(v{, Vj) but which is a k-clique of some (k-f-l)-clique, Tp , of KP(vt, Vj) , such that Qp is both a u,- — x± separator and Vj — x2 separator. Then, Q P < v i V j M. In subcase 2, x± and, in fact, all vertices of M are vertices of some k-cliques in KP(v{,Vj) . Then, M is a k-clique of some (k+l)-clique, Tp , in KP^^Vj) . Moreover, d^v^x^ = m a x v £ y ( T j rfc(»,-,t;) and dc(vj,x2) — m a x v £ v ( T ) ^e(vj^v) • Then, it is easy to see that Qp <v{Vj M, where Qp = Tp \ { r j . Finally, we show that every Q in KP(v{,Vj) is minimal with respect to (3G,< U | .W .) . Assume that there exists a k-clique M such that M <«,-«J- Q- Clearly, M is not in KP(vt,Vj) . By the above, there exists a k-clique Qp in KP(vt,Vj) such that Qp <v^j M. Then, transitivity of (3G , <«,-«•) implies that Qp <«,-«J- Q , which is impossible. • Let G = (V, E) be a k-tree, q — a positive integer, and for any u,- G V let V. — { v € V : ddv^v) < q}. Further, denote by G(V^) the subgraph of G induced by Vt . Proposition 4.1.3 The subgraphs G(V,) = ( V^E^, v{ G V, are sub-k-trees of G . Proof Choose 1) € Vt such that d c ^ j T T ) = maxv£V d^v^v) = m . Then, there exists a unique k-path KP (vt,v) , KP(vi,'v) = < Q0 , Tx , Q x , T2 , • •, T, , Q, > , between vrf and ¥ which determines a k-cable (7(1^,¥) of length m. Let Q, be the k-clique adjacent to ¥ in the k-path KP(v{,U) . Clearly, u?c(fe,«,) < m for all ve£ Q, and thus the vertex set of Q, is contained in Vt . It is easy to see that any other vertex v adjacent to v , if exist, would have dc(vi,v) > m . Thus, node v is a k-leaf in G(V{) . By 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 G induces a descendancy relation of vertices with respect to k-cliques in G. Such a relation can be extended to a descendancy relation among k-cliques and (k+l)-cliques in G. In general, if Kt and Kj are two k-cliques (resp. (k+l)-cliques) in G , then Kt is said to be a descendant of Kj if every node that is either contained in Ki or 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 G can be used to index all k(n — k) + 1 ^-cliques (resp. n — k (k-f-l)-cliques) in G , such that the index of a k-clique (resp., (k-f-l)-clique) Kt is smaller than the index of a k-clique (resp., (k+l)-clique) Kj if K{ is a descendant of Kj. Now, let G(V{) and G(Vj) be two sub k-trees of G with a corresponding collection of k-cliques (resp., (k+l)-cliques) % t and %j (resp., %[ and ) , respectively. Further, let Kr{ and Krj be the k-cliques (resp., (k+l)-cliques) having the highest indices, rt- and r- , in 3G,-and 3G;- (resp., 9G't- and %'j ) , respectively, and assume that ri < Tj . Then, it is easy to verify that 9G,- n %j ^ 0 (resp., 9&J D %'j ^  0) if and only if KT{ € %j (resp., KIT{ 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 Gx Gm be a collection of sub k-trees of G with an associated collections of k-cliques (resp., (k-fl)-cliques) 3 G 1 , - - - , 3 G m (resp., % 1 I , •••, % f ,) . Let 3G = {%!,•••, 3Gm } and 3G' = { 3G' , • • •, %'m} . Then, 3G and 3G' have the Helly property. That is, if 3G; n 9G;. ^ 0 (resp., %'{ D 9Gj # 0) for all i and j, then 3G4 # 0 (resp. n™;5&( # 0). 56 Proof: Let Kr{ (resp., KT{ ) be the k-clique (resp., (k-fl)-clique) with the highest index in 3G,-(resp. , 3G' ) and assume, without loss of generality, that rx < r • for all j . S (resp., 3C[ n %'j ^ 0) for all j we have Kfl £ %j (resp. , Klrj £ %'j ) for all j . • Theorem 4.1.1 Let G = (V, E) be a k-tree, V = { vx , v2 ,• • •, vn } , n > k +1 , and let be an even integer, R > 2k. For each v{ £ V let G(K, ) be the sub k-tree of G induced by V{ = { v € V : <fe(",f,-) < j + k — 1 } , with an associated collection, 9G,- , of ^-cliques. Then, D -eI%>i 7^ 0 > I Q { 1 > 2 , • • •, n } , if and only if dc(vt, Vj) < R for all pairs t, j £ I. Proof: Suppose that ^-£j^i ¥^ 0 • Then, it follows from Proposition 4.1.2 that for any pair i, j £ I there exists a k-clique Ql in the k-path KP(v{, Vj) which is in 3G; D %j . By definition of G(VA we have that max , , dciv^.v) < § + k — 1 and max , dJv^v) < 4 + k — 1. v " v£V(Qt) v *' ' — * v£V(Ql) v 1 ' — 2 Now, the k-clique Ql separates the cable C(v{, vf) , induced by KP(vt,Vj) , into two components (sides) Cv ^ and Cv , containing vt and Vj , respectively. From Proposition 4.1.1 it follows that W(Cv^Q) < f and W(Cy Q) < § , implying that de(v{,Vj) = W(CV Q) + W(CV Q ) < R , where, for example, W(CV Q^} denotes the total length of the paths in C(v;, vA which are in the component C n . Next, assume that for any pair i, j £ I, dc(vt,Vj) < R . Then, let Qt be a k-clique in KP(v{,Vj) satisfying m a z ^ ^ dc(vt,v) = d(v{,x{) = ^ + k — 1 . If no such k-clique exist then all k-cliques in KP(vt ,Vj) are in 3G,- PI 3C;- . If KP(v{ ,Vj) does not contain a k-clique then vt and Vj are adjacent and the k-clique containing v{ and Vj is in 3G^  n %j . Otherwise, by Proposition 4.1.1, W(CU. Q;) = § • implying that W(CV Q), < § • Therefore, again by Proposition 4.1.1, dc(vj, v) < § + k - 1 for all v £ Q, . Thus, Q, £ %{ CI %j , and by the Helly property of the collections 96^  we have that D -g. 7^  0- E 57 Theorem 4.1.2 Let G = (V,E) be a k-tree, V — { vt , v2 vn } , n > A + 1 , and let R be an odd positive integer, R > 2k — 1 . For each vt G V let G(Vi) be the sub k-tree of G induced by Vt — { v £ V: de(v, v{) < L f J + A- } , where ["J is the largest integer smaller than a , and let 3G- be the collection of (k+1 )-cliques in G(Vj) . Then, n 9Gj ^ 0 , I C { l , - - , n }, if and only if dc(v{ ,Vj) < R for all pairs i , j € I. Proof: Suppose that f~11£.^ 3Gj ^ 0 . Then, it follows from Proposition 4.1.2 that for any pair i, j G I there exists a (k-fl)-clique T, in KP^^Vj) such that T, G 3G' n 3G .^ . Let Q, and Ql+1 be the k-cliques in KP(v{,Vj) that induce T1, . Clearly, dc(vf,v) < [§ \ + k — I for all v G Qi and thus, W(CV^Q) < Lf J • Similarly, <f«;(V , v) < [§ J + k - 1 for all u G Q1+1 , which implies that W f C ^ J < L f J . Thus, dc(vt, „,) = ^ ( C „ . Q ( ) + ^ ( ^ .Q^^ + !<[§] + L f J + i = R-Next, assume that for every pair t, j G I, d^v^Vj) < R. Let T, be a (k-f-l)-clique in KP^^vA satisfying d^v^x^ = max dc(vt,v) = L f j + k. If no such (k+1)-clique exist then all (k+1 )-cliques in KP(vt ,Vj) are in 3G' f l 36'- . If KP(v{,Vj) does not contain a (k+1)-clique then vf and Vj are adjacent and the (k-t-l)-clique containing vf and i> • is in 3G' f l 3G'-. Otherwise, Tl G 3Gj- . Suppose that Tl is induced by the k-cliques Ql and Ql+i in KP(v{, «•) . Then, Q ) = Lf J + 1 • Therefore, W(CV Q ) = R - L f J ~ 1 = L f J + 1 - 1 = [ f J > which implies that dc(vj,v) < [ f J + k — 1 for all t E • Further, dc(v-, v) < [ f J + k for all v G T, , implying that T, G 3G'- . By the Helly property of the collections 3G' we conclude that f~l 3G{ ^  0 . • Observe that in Theorem 4.1.1 and 4.1.2 we restrict R to be at least 2 A — 1 . It can be 58 easily shown that if R < 2 k — 1 then the only decomposition of V for our R k-cable distance decomposition problem coincides with the vertex set 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 R is even (resp., odd) then for each v{ G V let Gk(V{) (resp., Gk+1(Vi) denote the sub k-tree of G induced by V{ = { v G V: dc(v, u.) < f + k -1 } (resp., V{ = { v G V: dc(v, vt) < |_§J + k } ) . Let % t (resp., 3G[) designate the collection of k-cliques (resp., (k-f-l)-cliques) in Gk(Vt) (resp., Gk+1(V^)) , and consider the intersection graph Gk = (V,Ek) (resp., Gk+1 = (V,Ek+1) , induced by the sub k-trees Gk(V{) (resp., Gk+1(Vi)) , v{ G V, where V= { v{ : G V} and (S.-.w )^ G (resp., (B.-.S^) G Ek+1) if 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 Gk and G k + 1 are chordal graphs. By combining Theorem 4.1.1 , 4.1.2 and the fact that Gk and G k + 1 are chordal graphs we can construct an 0(n2) time algorithm for generating an R k-cable distance decomposition of the vertex set of a k-tree. Indeed, Theorem 4.1.3 The R-cable distance decomposition problem can be found in a k-tree G = (V,E) in 0(n2) time . Proof If R is even (resp., odd) we construct the clique-intersection graph Gk (resp., G * + 1 ) . By Theorems 4.1.1 and 4.1.2 , a minimum clique cover in Gk or G k + 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 t , v • ) G G * (resp., ( v { , Vj) G G * + 1 ) if and only if d c ( v { , Vj) < R . Thus, the clique-intersection graphs Gk (resp., G * + 1 ) will be at hand after all cable distances, 59 de(vi, Vj) , for all vt , Vj in V have been found. The k-cable distances from a vertex t>4 to all other vertices v, v £ V, can easily be computed in 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, dc(u,-,u) = m a x ue Adj(v)^c(Vi' u ) ^ ' Thus, the construction of G f c (resp., G * + 1 ) takes 0 (n 2 ) time. Since Gk (resp., G * + 1 ) is a chordal graph, its minimum clique cover can be found in 0(n) time, see, for example, Gavr i l (1972) . Therefore, the complexity of the algorithm is dominated by the construction of G * (resp. G * + 1 ) which takes 0(n2) time. • 4.2 k-Cable Diameter of a k-Tree Let G = (V, E) be a k-tree, \ V\ = n , in which all edge weights are equal to one, and denote by Dc , Dc = ^ ( ^ 2 1 ^ 3 ) — m a x v . V.£V ^c(vi ivj) » ^ n e k-cable diameter of G . In this section we develop a linear time alogrithm for finding a longest k-cable, dc(v2,v3) , and the k-cable diameter, Dc , of a k-tree. Our algorithm is similar to Handler's (1973) algorithm for finding a 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 «t- , «• £ V, the extended k-path, KP(Vi,Vj) , induces a shortest k-cable C(vi,Vj) . Further, any (k+l)-clique Tp (resp., k-clique Qp) contained in KP(vt, Vj) separates C(v{, Vj) into two sides (components), one of which could be possibly empty, CvitTp(.vi>vj) a n d CvjtT,(vi>vj) (res?-' Cvt,Qr(vi>vi) a n d CVj,Qp(vi>vj)) ' not containing V j and V{ , respectively . Theorem 4.2.1 Let v1 be any k-leaf of a k-tree G = (V,E) , and let v2 be any vertex in G 60 such that dc(vx, v2) — max^^vdc(v1,v) . Further, let v3 G V be such that dc(v2,v3) = m a xv £ ydc(v2, v) . Then, Dc = dc(v2,v3) . Proof: Let v4 , v5 be any pair of vertices in V. We wil l show that dc(v4 , v5) < dc(v2,v3). Let Tp and T, be the (k + l)-cliques in KP(vltv2) with the highest indices such that T P is in KP^jV^) and T , is in KP[y^,v^) . We wil l assume, without loss of generality, that p < p' . Further, let T^, be the (k+l)-clique in KP(v1,v2) with the lowest index such that T^„ is in KP(y2, v3) . Note that Tp and T^, exist since v± is a k-leaf and T^,, exists since v2 is a k-leaf. Now, we need to consider two cases. Case 1: p" > pf. By definition of T , and T^,, and since p " > p', we have that T ,, is contained in KP(v2, v4) . Thus, by the construction of v3 we have : ^ ( ^ , T > 2 ^ 3 ) ) > W(C T (v2,v4)) (4.1) and by the construction of v2 we have that : W(C. x ( " i ' "2)) > T > , , v5)). (4.2) Let 1= W(CV T (vltv2))n W(Cv T K . D j ) ) . Then, by (4.1) and (4.2) rfe(»2,t;3) = W(C T (v2,v3)) + W(C T K , * 2 ) ) - / d> p' ' 2' p' ^ ^ . . T . K . ^ ) ) + W(C T Jv2,v4)) - I. (4.3) We further claim that W(C T^V^V,)) + W(C T n(v2,v4)) - I > dc(v4,v5) . (4.4) 61 Indeed, if p < p' then T , is in KP(y2, ^4) and (4.4) is satisfied as equality. Otherwise, p = p'. Then, if T , is not in KP{v4, v5) (4.4) clearly holds, while if T , is in KP(v4, r;5) then T^, is contained in at least one of the two k-paths KP(v2,v4) and KP(v2,v5) . Without loss of generality, we can assume that T , is in KP(v2, v4) , which was shown above to imply (4.4) . We conclude therefore by (4.3) and (4.4) that if p " > p' then dc(v2, v3) > dc(v4, v5) . Case 2 p " < p'. In this case we clearly have that T , is in KP(v2, v3) . Let Q^, be the k-clique in T , such that Q^, is in KP(vx, u 2) and having the highest index among all such k-cliques. By the construction of v3 we have that : W(Cv„Q , ( « 2 . » 3 ) ) > W ( C v n ( ( « 2 , « 4 ) ) • (4-5) Further, by the construction of v2 , (4.2) holds. Now, by (4.2) and (4.5) , dc(v2,v3) = W(C Q (v2,v3)) + W(C T (Vl,v2))) (4.6) ^ > 2^4)) + ^ r ( ^ , 4 4 p o p We claim that ^ C , 4 , 0 f ( W 2 , » 4 ) ) + m C ^ r ( « ! , ! % ) ) > rfe(«4,»6)- (4-7) Indeed, if p < p' , T , is in KP(v2, t>4) and (4.7) is satisfied as equality. If p = p ' and T^, is not in KP(v4 , « 5 ) , then (4.7) is clearly satisfied. Otherwise, p = p' and T , is in KP(v4, v 5) . In this event, similar to the proof in Case 1, we can assume without loss of generality that T , is in 62 KP(v2,v4) , which was shown above to imply (4.7). We conclude that (4.7) holds, which completes the proof. • Now, as explained in the proof of Theorem 4.1.3, d ^ t ^ , ^ ) and dc(v2 ,v3) can be computed in linear time which implies, by Theorem 4.2.1, that Dc = dc(v2,v3) can be computed in linear time. 63 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 V2 satisfying (i) j Vj | < (k/k+\)n , i = 1,2, and (ii) no edge in E connects a vertex in with a vertex in V2 • We prove the existence of a k-separator for partial 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. We 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 k = 2 , 3 . Finally, we develop parallel algorithms for the recognition of partial k-trees when k = 2 ,3 . These algorithms require 0(log2n) time and use, respectively, 0(n3) and 0(n4) processors. For k = 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, 0(n ) and 0(n13) processors for these cases. The chapter is organized as follows. In Section 5.1 we study k-separators of partial k-trees and describe an O(nlogn) algorithm for constructing a balanced binary decomposition tree for k-trees. 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) be a partial k-tree (k > 2) with | V\ = n . A k-separator of G is a set of vertices S, of cardinality | 5 | = k , which induces a partition { V^, V2} of V \ S satisfying \Vt\ < n , i = 1,2, (5.1) and no edge in E connects a vertex in Vx with a vertex in V2 (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 Tamir (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: Since any k-separator of a k-tree G — (V, E) is also a k-separator of every partial graph of 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 v for which the corresponding set of descendant vertices, D(KV) , of the k-clique Kv induced by Adj(v) , contains 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 V(KV) = Adj(v) = { «1( uk } and V(Kj) = Adj (v) U {v} \ {«,}, j = where V(A) denotes the vertex set of a graph A. Then, update D(KV) , the set of descendant nodes of Kv , and |D(i(\,) | as follows: k D(KV) = (U IKKJ)) U D(KV) U W (5.3) k \D(KV)\ = £ |Z)(tf,.)l + \D{KV)\ + 1. i=l (5.4) 66 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 wil l 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. Case 1 J2\D(Kj)\ + 1 > g»-j=l Let Vj = D(Kj) , j = I , - , *, and Vk+1 = V \ { ( U * = 1 VA U Adj(v) U > } } , and let 7, be such that | V. j = max. , , J K , - | . We wil l prove that the set of vertices J = l , • ••,k+l J s, ( Adj(v) if 1= k+l S= \ _ [_ V(K,) otherwise is the required k-separator. Further, {Vlt V2} where V \ = V, and V2 = V \ (Vt U 5) is the required partition of V \ S satisfying (5.1) - (5.2) . Indeed, by assumption, Y<)=1 \ Vj\ = Y?l=1\D(K j)\ > i» ~ !> w h i c h coupled with £ + 1 E y - i I ^ j l = n — (^+1) implies that Vk+1\ < n - ( i + 1) - ( § n - 1) < \ n . (5.5) Moreover, since v is the first node encountered by the reduction process for which l-D^u)! 67 > I n , we have that 3 Thus, by (5.5) and (5.6) 1101 < h , j= k. (5.6) \V,\ = <§»<E£I > * > 2 . (5-7) Furthermore, j t?"x| = | K , | > - — ^ , which implies that \ V 2 \ < n - k - n — I ^ < j ^ n . (5.8) By the definition of , V2 and 5 we also have that V1nV2 = <D,V1\JV2=V\ S , and there is no edge in E with endpoints in V1 and V2 • Thus, 5 is the required It-separator. Case 2 J \D(Kj)\ + 1 < | n . i=i We wil l prove that if Case 2 holds then S = Adj(v) is the required k-separator. Let D(KV) denote the set of descendant nodes of K„ just before it was updated by (5.3), which resulted with |D(iir„)| > | n , and construct the new sets Vx = li'j-x D(Kj) U {v} and V2 = D(KV) . By assumption, \V1\ < | n . Further, \V2\ < | n , since otherwise Step 1 would have terminated earlier. Now, let Vx = V± if | ^ | > | V21 and Vl = V2 otherwise, and let V2 — V\ (V1 U S) , where 5 = Adj(v) . Since | V{\ < § n, i = 1,2, we have that 68 Moreover, by (5.4) 1^1 + \V2\ = \D(KV)\ > § n , which implies that I ^ J = mar ( | Vx \, | V 2 | ) > \ n . Since | + \ V2\ = n — k we derive | V " 2 | < n - J t - i n < j | - j n , k > 2 . Again, by the definition of V\ , V2 and 5 we also have that ^ U V2 = V \ S , V \ fl V" 2 = 0 and there is no edge with endpoints in V\ and V2 . The above algorithm will produce a k-separator for a k-tree in linear time since Step 1 wil l 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 G = ( V, E) be a k-tree and S a k-separator of G which induces a partition of V \ S into { K i , ^ } that satisfies (1) and (2) . Then, the subgraphs G ^ U 5 ) and G(V2Uff) induced, respectively, by V\ U S and V2 U 5 are also k-trees which can be similarly decomposed. We can proceed in this manner to decompose G recursively until we end up with k-cliques. That entire decomposition can be represented by a balanced binary decomposition tree, T, which is a rooted binary tree in which the root v represents the graph G , and if some vertex q is a parent of ?! and q2 in T then qx and q2 are sub-k-trees of q obtained by the above decomposition of q . Corollary 5.1.1 Let G = (V,E) beak-tree. Then, a balanced binary decomposition tree, T, of G can be constructed in O(nlogn) time. 69 Proof: Let L denote the subset of vertices in T such that the path from the root of T to a vertex in L has / edges. The leaves of T are 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 0(log n) deep, i.e. the path from the root of T to any of its leafs contains at most 0(log n) edges. 5.2 SOME SEPARATION PROPERTIES OF PARTIAL k-TREES We derive in this section some separation properties of partial k-trees into k-trees which wil l be used later to develop N C algorithms for the recognition and embedding of partial k-trees into k-trees when k = 2 and 3 . Lemma 5.2.1 Let G = (V, E) be a graph and S a separator of G which induces a partition of V\S into {V1, V2} such that 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(V1 Li S) and G 2 = G( V2 U S) induced, respectively, by Vx U S and V2 U S are partial k-trees. Proof: If G is a partial k-tree then since G± and G 2 are subgraphs of G they are also partial k-trees. On the other hand, assume that G x and G 2 are partial k-trees and let G x = (V1 U S , E-i) and G 2 = (V2 U S , E2), respectively, be their embeddings into k-trees. Clearly, G(S) is a subgraph of G t and G 2 . Therefore, there exist fc-cliques Kx and K2 contained, respectively, 70 in Gl and G 2 and such that both Kx and K2 contain the /-clique G(S) . Let vl+l, vk and i • • • ) denote the nodes in l ^ i ^ ) and K(iif 2 ) , respectively, that are not in S, and consider the graph G obtained from G = (V, E1 \J E2) after the addition of the edges («,-,«•) , i = / + 1 Jfc , j — I + 1 , •••, k and j > i. Then, it is easy to see that G is a k-tree, and since G is a partial graph of G , it follows that G is a partial k-tree. (Note that in the degenerate case, when / = 0, we simply choose for Kx and K2 in the above proof any two k-cliques which are contained in Gx and G2.) • We wil l use in the sequel the following notation. For a graph G — (V, E) and subsets Sx, S2 such that Sx C S2 C V we wil l denote by G(S2 ; K^S^) the subgraph of G induced by S2 which is augmented with all arcs between pairs of nodes of Sx if they are missing in G . Lemma 5.2.2 Let G = (V, E) be a two-connected graph and S , S — {s j , s2} , a separator of G which induces the partition of V \ S into { Vx, V2 } such that V{ ^ 0 and | V{ U 5 | > k, i = 1 ,2 . Then, G is a partial k-tree if and only if the subgraphs Gx = G( Vx U S ; K({ sx, s 2 })) and G2 = G(V2 U S; K({sx,s2})) are partial k-trees. Proof: If G(Kj U 5 ; ^({^I,*2})) , i = 1,2, are partial k-trees then, by using Lemma 5.2.1 we can conclude that G is a partial k-tree. Thus, suppose that G is a partial k-tree. Since Vx ^ 0 and G is two-connected, there exists a vertex vx 6 Vx and two disjoint paths, p(*>i,Si) and p ( v 1 , s 2 ) , joining vx with Sj and s2, respectively, in the subgraph G( U S). Therefore, v{v\isi) and p(^i,s2) form a simple path, p(si,S2)' between sx and 5 2 in G(V1 U S), and contracting the edges along p(si, s2) would yield a 2-clique with a vertex set S = {si,^}-Thus, G is contractible to G(V2 U S; , s 2 » ) , " which implies that G ( K 2 U S; ^ ({s j , s 2 }) ) 71 is a partial k-tree. Analogously, we obtain that G(V1 U S; K({si,s2})) is a partial k-tree as well. • Lemma 5.2.3 Let G = (V,E) be a triconnected simple graph and S, S = { ux , «2 , u3 } , a separator of G inducing a partition of V \ S into { V1 , V2} such that | Vj \ > 2 , i = 1 , 2 , and | Vj U 5| > Jfc, « = 1 , 2 . Then, G 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 G is a partial k-tree and let v1 , v2 be in V x . By the triconnectivity of G , there exist at least three vertex disjoint paths between vx and v2 in G , and since 5 is a separator and | S\ = 3 , at least two of these paths are contained in G( Vx U S) . Therefore, since G is assumed to be a simple graph, these two paths form a cycle C in G( V1 U S) with at least 3 vertices. By the triconnectivity of G there exist 3 vertices, say ~s1 , S 2 and T 3 , in C and vertex disjoint paths , "sO , ?2(s2 > "* 2) > Ps( s3 > ^ 3) ( s o m e possibly degenerated to a single vertex) in G(V1 U S) , such that p , ( S j , T j ) i = 1 , 2 , 3 , intersect with C only in nodes T j , i 1 . 2 , '.\ , respectively. Clearly, if we contract edges in the paths Pi(st , Tf) , i — 1 , 2 , 3, and identify st with "s t , for i = 1 , 2 , 3 , respectively, we create a cycle C' that contains s1 , s2 , s 3 . Again, appropriate contractions of edges in C' will create a 3-clique K(S) . Thus, G is contractible to G( V 2 U S ; #(5)) and we conclude that G( V 2 U S ; if(5)) is a partial k-tree. Analogously, we can show that G(V1 U S ; K(S)) 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) G into a 2-tree (resp., 3-tree). The root, r , of T is the graph G, and i f qx and q2 are sons of r in T then qx (resp., g 2) is the graph G(V1 U 5 ; K(S)) (resp., G ( l ^ U S; i^(5))) , where 5 is a two-separator (resp. 3-separator of 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(Vr U S; K(S)) and G(V2 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) 2-trees (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., three-connected partial 3-tree) graphs 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 otherwise. Further, i f a = 1 73 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, if | Vj < 9 (resp., 20) check in constant time whether G is a partial 2-tree (resp., 3-tree). If yes, find an embedding, 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 = { s i i S 2 } (resp., S = {s\,s2,s3}) of V, in parallel, find all the connected components of G (V \ S) and denote their vertex sets by Vj : j = 1, ••• , rg for some r^ > 1. (2.1) If \ Vf\ > l\V\ (resp., |V/| > ||V|) for some ; = 1, ••• , r s reject 5. If all the pairs (resp., triples) S were rejected set a = 0 and exit. (2.2) Else, if l\V\ < \Vf\ < \\V\ (resp., \\V\ < \Vf\ < \\V\) for some 5 and for some j, 1 < j < rg , set Mx = Vf U S and M2 = (V \ Vf). (2.3) Else, for an unrejected S compute q, = Ylj<i l ^ / l > ' = ^» ' rs • a n d a P P ^ v a binary search to find n for which \\V\ < qn < \\V\ (resp., \\V\ < qn < \\V\). Set Mx = u j = 1 Vf U S and M 2 = (V\Mj) U S. (2.4) Ca l l in parallel BBD(G(Ml ; K(S)),ax , Lt) and BBD(G(M2; K(S)),a2,L2). If either ax = 0 or a2 = 0 set a = 0 and exit. Else, set L = Lx U L2 . E x i t . 74 Theorem 5.3.1 Algorithm 5.1 recognizes whether a two-connected (resp., three-connected) simple graph 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(hg2n) time using 0(n3) (resp., 0 (n 4 ) ) processors. Proof: 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). Thus, by Lemma 5.2.2 (resp., Lemma 5.2.3) we can conclude that G is not a partial 2-tree (resp., 3-tree). The biconnectivity (resp., triconnectivity) of G 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 is a partial 2-tree (resp., 3-tree) if and only if all the minors G(Mi ; K(S)), i = l , 2 , created in Step 2 are partial 2-trees (resp., 3-trees). Next, we wil l show that Algorithm 5.1 requires 0(log2n) time and 0(n3) (resp., 0(n4)) processors. 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., 3-trees) of Wald and Colbourn (1983) (resp., Arnborg and Proskurowski (1986)). A l l connected 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) processors, where m = \E\ . Note that in our case m = 0(n) . Since there are 0(n2) (resp., 0(n3)) pairs (resp., triples) to be considered simultaneously, Step 2 requires 0(n3) (resp., 0(n 4 ) ) processors. Further, in Step 2, (2.3) takes O(logn) time using 75 0(n ) processors in order to compute partial sums, qt, and to perform a binary search on them. Since in (2.2) and (2.3), \M{\ < §|V| (resp., \M{\ < \\V\), i = 1,2, Algorithm 5.1 will terminate after performing at most O(logn) nested calls of Procedure BBD(G,a, L). Thus, our algorithm recognizes whether a two-connected (resp., three-connected) graph G is a partial 2-tree (resp., 3-tree) and delivers in L an embedding of G into a 2-tree (resp., 3-tree) in 0(log2n) time using 0(.n 3) (resp., 0(n4)) processors. • 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) time with 0(n) processors. 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. By Lemma 5.2.1, G is a partial 2-tree i f and only if al l biconnected components of G are partial 2-trees. Clearly, the modified algorithm requires 0(log2n) time and 0(n3) 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 0(log2n) time and <3(n4) processors. 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 x = Pi(v,si) and Vi — P 2 ( u > s 2 ) m G = (V,E), having only the vertex v in common, the path p = p(k, 1) will be called a bridge path between p± and p2 if p originates at some node k in py, k ^ v, and terminates at vertex I in p2 , I ^ v, but p is otherwise vertex disjoint with p t and p 2 . Lemma 5.4.1 Let S = {s1,s2, s3} be a separator of G = ( V , E) inducing a partition { Vy, V2) of V \ S such that no edge in E connects a vertex in K x with a vertex of V2 . Assume that for i = 1,2 there exists a vertex vt 6 Vt and three disjoint paths p ( t ) i , s J ) , j = 1 ,2 ,3 , joining v{ with Sj, j = 1,2,3. If for i = 1 and 2 there exists a bridge path between a pair of paths among the paths p(vt,Sj), j= 1 ,2 ,3 , which is contained in G ( V , U 5 ) , then G is a partial k-tree if and only if G( Vr U 5 ; K(S)) and G( V2 U S ; K(S)) are partial k-trees. Proof: The existence of a bridge path between some pair of the paths p ( v i , s J ) , j= 1 ,2 ,3 , for i = 1 and 2 imply that G is contractible to G( Vx U S; K(S)) and G( V2 U S ; #(5)) . Thus, if G is a partial k-tree, so are G ( ^ U 5 ; ^(5)) , i = 1 , 2 . On the other hand, Lemma 5.2.1 implies that if G( Vt U S ; K(S)) , i — 1,2, are partial k-trees then G must also be a partial k-tree. 0 Lemma 5.4.2 Let S = { s : , s2 , s 3 } be a 3-separator of a 2-connected simple graph G = ( V, E) 77 which induces a partition {Vx, V2} of V \ 5 such that 2 < | | < | | V | , t = 1,2, and no edge in E connects a vertex in Vy with a vertex in V2 . Assume that for i = 1,2 there exist vertices v{ G V,- and three disjoint paths p(vt,Sj) , j = 1 ,2 ,3 , joining vt 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 in G(Vi U S) then for some j G {1,2 ,3} and i G {1,2} , {vt, Sj} is a separator of G which induces a partition {V[, V2 } of 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 p(v1,Sj),j= 1,2,3. Since G is connected, for any v E Vx there exists a node s(v), s(v) G S, and a path from v to s(v), p(v,s(v)), in G which does not pass through nodes in S \ {s(v)}. Now, any node v, v € Vx and v ^ vx , must be in some connected component of G(V\ {«(*>), %}) which does not contain S \ {s(v)}. Indeed, otherwise there must exist a path, p(v,~s(v)), in G from v to a node ~s(v) , ~s(v) G S \ {«(*>)} , which does not pass through either or s(v) . But, the paths p(v,s(v)) and p(v,J(v)) in G induce a bridge path in G(V1 U S) between p(vx,s(v)) and p(vx,~s(v)), which is a contradiction. Next, for < = 1,2,3 let Ci denote, respectively, the union of all connected components of G(V\ {*>i,S(}) which do not contain any node in S\ {st} . We claim that the sets Ct , t G { 1 , 2 , 3 } , are mutually exclusive. Indeed, from the 2-connectivity of G and the definition of the sets Ct it follows that if v G C,- , i G { 1 , 2 , 3 } , and v 9^  vx , then there exists a path s^ ) , st G 5, which does not pass through {v^} U S \ {s,} . Thus, if v G C,- D Cj , ij G {1,2,3} and i ^ j, the paths p(v,s{) and p(v,Sj) in G would induce a bridge path between p(fli,S;) and p(v!,Sj), which is a contradiction. Thus, we have that ^ ^ = 1 1 V^C*)! = 1 ^ 1 - 1 , where V(Ct) denotes the set of nodes in Ct . Let \V(Cj)\ = max{ \ V(Ct)\ : t = 1,2,3 } , and 78 set V[ = V(Cj) and V'2 = V\ (F 1 , U{t ) 1 , sA) . Since 5 is a 3-separator, | V \ | > \\V\ - 3 and thus, \V[\ > - 2 . Clearly, V(Ct) C ^ , t = 1 , 2 , 3 , and thus \V[\ < • We use the above separation results to construct an NC-algorithm for recognizing a partial 3-tree. Algorithm 5.2 Procedure REC{ G, a) Input A simple graph G = (V, E). Output a — 1 if G is a partial 3-tree and a = O otherwise . Step 1 Find all biconnected components of G . If G has no biconnected components, set a = 1 and exit. Otherwise, perform in parallel procedure RECl(Gi, a,) for all biconnected components G^ = ( V ^ , ^ ) of G . If any at = 0 set a = 0 and exit. Procedure REC\(G, a) Input A simple biconnected graph G = (V,E). Output a = 1 if G is a partial 3-tree and a = 0 otherwise . Step 0 a = 1. Step 1 79 (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 Else, for each triple of distinct vertices S — { s i , s 2 , « 3 } °f V, in parallel, find all connected components of G(V \ S) and denote their vertex sets by Vf, j = , rs , for some rg > 1. (2.1) If\Vf\> l\V\ for some j =!,••• , rg , reject 5. If all triples S are rejected, set a = 0 and exit. (2.2) Else, if \\V\ < \Vf\ < f | V | for some S and for some j, 1 < j < r$ , set Mi = Vf U S a n d Af 2 = ( V \ V?). (2.3) Else, for an unrejected S and for all j = 1, • • • , rs , compute qt = ^><jl ^ ' ' = ^ ' " ' r 5 ' a n d a P P i v a binary search to find an n for which \ \ V\ < 817 < II V| . Set ¥ 1 = 5 U (U Vf :j< n) and M 2 = (V \ Mx) U 5 . Step 3 Find, in parallel, connected components of G(Mt \ {*,-,*j}) which do not contain S \ { S J , S J } for t = 1,2, z ^  j , z , j € {1,2,3} . Denote by C] j the union of all such connected components, and let C^j = C)^ U C 2 ^ for all {i,j} € {1,2 ,3} , i ^ j • (3.1) If C 1 ) 2 # 0 , C 2 ) 3 # 0 and C 1 ) 3 ^ 0 let Gt = G(MX ; #(5)) and G2 = G(M2 ; K(S)). (3.2) Else, if there exist at least two distinct pairs {i,j} and {p,q },{i,j} U {Pi ?} = {1)2,3} such that Ctj = 0 and CP,q ^0 proceed as follows: 80 (a) If inCi, 2 ) | + \ V(C2,3)\ + inCi,3)l < \MAS\ and | K ( C ? , 2 ) | + |KCS > 3)I + 1^ (^ 1,3)1 < \ 5"|, where V\C\j) is the vertex set of component G ^ - , then let G x = G(M1 ; K{S)) and G 2 = G(M2 ; Jf(S)) . (b) Else, if for some t G {1 ,2} , |V(C* 1 > a ) | + |V(C2,s)l + I K ^ s ) ! = l^ t \ S\ find I V(C*,i)l = m a * { | V ( C * , 2 ) | , | K ( C i , 3 ) | , | V ( C J ) 3 ) | } and let G x = G(7(C£, , ) U { 5 f c ) S , } ; tf({st,S,})) and G 2 = G{{V\ V(Ck>l)) U K , s , } ; K({sk, ,,})). (3.3) Else, if C 1 ) 2 = 0 , G 2 ) 3 = 0 and C 1 3 = 0 find, in parallel, connected components of G( K \ {s t , «}), for all t € {1,2,3} and v G K, and denote their vertex sets by Vj(v, st) , j — 1, ••• , m(u,s ( ) , for some m(u,s t ) > 1. If |V;-(«,Sj)| > Q\V\ for some j, j € {I, ••• , m(u,s t )} , reject the pair { f , s t } . (o) If all pairs {f,St }, t G { 1,2,3} and v G V , were rejected let G x = G(Mj ; K(S)) and G 2 = G(Af 2 ; K(S)) . (6) Else, if - 2 < | 1^ (v , s t ) | for some G {1, ••• , m(v, st))}, set Af^ = Vj (v,st) U { v, st } and M>2 = V \ Vj (v, st) and let G x = G(Af' 1 ; tf({t;,sj)) and G 2 = ; tf({i/,6-,})) . (c) Else, for an unrejected pair {v,st} compute q, = ^ t < J | V , - (v, st)\, I = l , - - - , m(v,st) , and apply a binary search to find n for which ^ | V\ -2 < < | | V | . Set M1! = {*;,«,} U ( U l A (»,*,) : j < 1;) , Ml2 = ( V VH\) U {v,st} , G x = GiM1, ; /£-({!),«,})) and G2 = G(MI2 ;K({v,st})) . (3.4) Ca l l in parallel RECl^, ax) and REC1(G2, a2). If either ax = 0 or a 2 = 0 set a = 0. Exit . 81 Theorem 5.4.1 Algorithm 5.2 recognizes whether a simple graph G = (V ,E) with | V | = n is a partial 3-tree in 0(log2 n) time using 0 (n 4 ) processes. Proof: We wil l first prove the validity of Algorithm 6.1. If, in Procedure REC(G,a), G is found not to contain biconnected components, then it could be decomposed by zero or one separators into subgraphs of cardinality at most 4. Since every graph on 4 nodes is a partial 3-tree, Lemma 5.2.1 implies that G is a partial 3-tree. The validity of Step 1 in REC1(G, a) was explained in Algorithm 5.1. If all triples were rejected in Step 2, G does not contain a 3-separator and by Theorem 3.1, G is not a partial 3-tree. Otherwise, in Step 2 algorithm 5.2 finds a 3-separator. In Step 3, if Ct j ^ 0 for some i ^ j, then { S J , S J } is a separator of G, and by the biconnectivity of G and Lemma 5.2.2 it follows that G is a partial 3-tree if and only if G augmented with edge (st,Sj) is a partial 3-tree. Thus, by Lemma 5.2.3, if (3.1) holds, then G is a partial 3-tree if and only if G{MX ; K(S)) and G(M2 ; K(S)) are partial 3-trees. If (3.2) holds then, by Lemma 5.2.2, we can augment G with edge (p,q). Therefore, if 3.2a) is valid, there must exist vertices vt, vt G Mt \ S , i = l , 2 , and three disjoint paths from v{ to all s G S in G(Mi) , i = l , 2 . Thus, by Lemma 5.4.1, since (p,q ) is a bridge path both in G(M1) and G(M2), G is a partial 3-tree if and only if G(M1 ; K(S)) and G(M2 ; K(S)) are partial 3-trees. On the other hand, if 3.2b) holds then, by Lemma 5.2.2, G is a partial 3-tree if and only if G(V(Ci,,) U { sk, s, } ; A'({ sk, s,})) and G((V\ 1 ^ , , ) ) U ; K({sk,s,})) are partial 3-trees. If (3.3) holds, then for each i = 1,2 and for each v G M{ there exist three disjoint paths in G(M{) from v to all nodes in S . Therefore, by Lemma 5.4.2, if all pairs are rejected in 3.3a), there must exist a bridge path both in GiMy) and G(M2) satisfying the stipulations in Lemma 82 5.4.2 . Then, by Lemma 5.4.1, G is a partial 3-tree if and only if G(MX ; K(S)) and G ( M 2 ; K(S)) are partial 3-trees. Otherwise, by Lemma 5.2.2, G is a partial 3-tree if and only if G(MI1 ; K({ v, st })) and G(Af*2 5 ^({v,st})) a r e partial 3-trees. Next, we wil l show that algorithm 5.2 requires 0(log2n) time using 0 (n 4 ) processors. A l l 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 O(logn) time with 0(n + m) processors. Since there are 0(n3) triples S to be considered simultaneously, Step 2 requires O(logn) time and 0 (n 4 ) processors. It takes O(logn) time using 0(n2) processors to compute, in Step 2.3, partial sums q1 and perform a binary search on them. In Step 3, connected components of G(Mt \ {s;,Sj}) which do not contain 5\{s,- ,s^} can be found in O(logn) time using O(n) processors. Similarly, connected components of G (V\ {st, v}) can be found in O(logn) time using 0(n) processors, and since there are 0(n) pairs {st, v) to be considered simultaneously, Step (3.3) requires O(logn) time and 0(n 2 ) processors. Further, 3.3c) takes O(logn) time using 0(n2) processors. Finally, observe that in (2.2) | V ? | > | | F | , in (2.3) q„ > \\V\ and, since S is a 3-separator, in Step 3.2b) | K (CXjf)| > Further, in Step 3.3, \ Vj{v, st)\ > ±\V\ - 2 and q^ > V\ — 2 . Therefore, we can have at most O(logn) nested calls of RECl(G,a), and algorithm 5.2 would terminate in 0(log2 n) time using 0(n4) processors. • 83 Bibliography A . V . Aho, J.E. Hopcroft and J.D. Ullman, "The Design and Analysis of Computer Algorithms," Addison- Wesley, Reading, 1974 S. Arnborg, "Reduced State Enumeration: Another Algorithm for Reliability Evaluation,'" IEEE Transactions on Reliability 27 (1978), 101-105. 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 Problems on Graphs with Bounded Decomposability - A Survey," BIT 25 (1985), 2-33. 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," Congressus Numerantium, 47 (1985), 69-75 S. Arnborg and A . Proskurowski, "Characterization and Recognition of Partial 3-trees," SIAM Journal on Algebraic and Discrete Methods 7 (1986), 305-314. 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 n d revised edition Amsterdam, North Holland Publishing Company, NY, NY, USA, 1985. 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 Wi th Bounded Tree-Width," RUU-CS-86-22, Rijksuniversiteit Utrecht, The Netherlands, November 1986. H . L . Bodlaender, "NC-Algori thms 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. Int. Conf. Automata, Languages, Programming, Springer-Verlag L N C S 172 (1984), 128-136. 84 D . G . Corneil and J . M . Kei 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.Pe r l , "Clustering and Domination in Perfect Graphs," Discrete Applied Mathematics 9 (1984), 27-39 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 in Matrix Computation," Ph .D. Thesis at Cornell University, Ithaca, N Y , July 1985. 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 University Press, Princeton N.J. 1962. S. Fortune and J . Wyll ie , "Parallelism in Random Access Machines," Proceedings of the 10th Annual ACM Symposium on Theory of Computing, (1978) 114-118. M . C . Golumbic, "Algorithmic Graph Theory and Perfect Graphs," Academic Press, New York, 1980. M . R . Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco (1979). F. Gavr i l , "Algorithms for Min imum Coloring, Maximum Clique, Minimum Coloring by Cliques and Maximum Independent Set of a Chordal Graph," SIAM Journal on Computing 1 (1972) 180-187. D. Granot, " A Generalized Linear Production Model: A Unifying Model," Mathematical Programming 34 (1986), 212-223. 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 Programming 21 (1981) 1-18. 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 Location of a Facility in an Undirected Tree Graph," Transp. Sc. 7 (1973), 287-293. F . Harary, "Graph Theory," Addison Wesley, Reading, Mass., 1969. R. Hassin and A . Tamir, "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 6 (1985), 434-451. 85 A . Kolen and A . Tamir, "Covering Problems" Chapter 6. in Discrete Location Theory, L . R . Francis and D . B . Mirchandani, eds., John Wiley, New York (forthcoming). S.C. Littlechild, " A Simple Expression for the Nucleolus in a Special Case", International Journal on Game Theory 3 (1974), 21-29. 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 of Computer Science (1979), 307-311. 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 Caterpillars," Discrete Mathematics 49 (1984), 275-285. 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, "Graph Minors II: Algorithmic Aspects of Tree Width ," Journal of Algorithms 7 (1986), 309-322. N . Robertson and P . D . Seymour, "Disjoint paths - A survey," SIAM Journal on Algebraic and Discrete Methods 6 (1985), 300-305. D. J . Rose, " O n Simple Characterizations of k-Trees," Discrete Mathematics 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 Algor i thm," Journal of Algorithms 3 (1982), 57-67. 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 Algor i thm," SIAM Journal on Computing 14 (1985), 862-874. 86 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 Journal on Computing 11 (1982), 298-313. U . Viskin, "Implementation of Simultaneous-Memory Access in Models That Forbid It," Journal of Algorithms 4, (1983), 45-50 A . Wald and C . J . Colbourn, "Steiner Trees, Partial 2-trees, and Minimum IFI Networks," Networks 13 (1983), 159-167. 87 

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

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>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.831.1-0098333/manifest

Comment

Related Items