# A simpleO(n2) algorithm for the all-pairs shortest path problem on an interval graph

код для вставкиСкачатьStar-Factors and k-Bounded Total Domination Georg Gunther Sir Wilfred Grenfell College, Cornerbrook, Newfoundland, Canada A2H 6P9 Bert Hartnell Saint Mary’s University, Halifax, Nova Scotia, Canada B3H 3C3 Douglas Rall Furman University, Greenville, South Carolina 29613 In this paper, we consider a variation of total domination in which we limit the ability of a vertex to dominate its neighbors in one of two ways: (a) Every vertex in the dominating set dominates exactly k of its neighbors. Graphs that have such dominating sets are characterized and a recognition algorithm for trees is described. (b) Every vertex in the dominating set dominates no more than k of its neighbors. It is shown that the existence of such a dominating set is equivalent to the existence in the graph of a star-factor (which is a m I k). It is further shown that the existence of such a partition of the vertex set into rn-stars where 1 I star-factor is equivalent to a Tutte-like condition which requires that k I N ( I )I 2 I I I for every independent set I of vertices in G. When this last result is interpreted in the case when G is bipartite, a generalization of the Marriage Theorem emerges. 0 7996 John Wiley & Sons, Inc. 1. INTRODUCTION As in [I], consider the following variation on domination: Assume that we have a network consisting of n components (each represented by a vertex), each of whish is subject to failure. Since we cannot trust a component that has failed to reliably inform us of that fact, we wish to monitor each component from a neighbor. In general, we may wish to install monitoring devices on a subset of the components where each device monitors no more than k neighboring components and each component is monitored exactly once. We can model this situation by having an edge directed from a monitor to the vertex being monitored. Hence, each vertex in the monitoring set has no more than k edges directed away from it, and every vertex in the graph has exactly one edge directed toward it. Note that an edge in the graph may have no direction assigned to it (it is not used in the monitoring), may be directed in one direction, or may, in fact, be directed in both directions (representing the situation where each end is monitoring the other). With these possibilities for directing edges, we make the following definitions: We call a set D of vertices of a graph G a k , exact 1-.. total dominating set if it is possible to find a spanning subgraph of G all of whose edges can be directed to form a directed graph G + in such a manner that every vertex in D has outdegree at least 1 and at most k , and every vertex in G + has indegree exactly 1. In forming the directed graph G + , we are allowing each undirected edge { x,y } in the spanning subgraph to be replaced with either one or both of the directed edges xy or yx. To simplify the notation, we shall refer to D as a ( k , I]-total dominating set or simply as a ( k , 11-set. If every vertex in D has outdegree exactly k , we call D an exact k , exact 1-total dominating set and refer to it as a [ k , 11-set. In G + , we say that a vertex x dominates a vertex y if G + contains the directed edge xy. Note that in the case where k = 1 a set D is a ( 1 , 11-set if and only if it is a [ I , I]-set. NETWORKS, Vol. 27 (1996) 197-201 0 1996 John Wiley & Sons,Inc. CCC 0028-3045/96/030197-05 197 198 GUNTHER, HARTNELL, AND RALL If we consider the case when k = 1, then, as in [ 11, we observe the following: For any vertex x in G + , suppose that the unique edge directed away from x leads to J]. Either the unique edge directed away from y leads back to .Y or it is directed toward a third vertex, say z.In the latter case, either the unique edge directed away from z leads back to x or to still another vertex w. Eventually, we must complete the cycle and be led back to x . Thus, any graph G which has a [ I , I] -set must have the property that it contains a spanning subgraph which is the vertex disjoint union of edges and cycles. (In the corresponding directed graph G + , the isolated edges are directed both ways while the cycle edges are directed in one consistent direction.) This type of subgraph was called a q-factor by Tutte [ 51. Conversely, if G has a spanning subgraph which is a q-factor, then the entire vertex set V ( G )is a [ l , 11-set. We simply direct the isolated edges of the q-factor in both directions and assign an arbitrarily chosen orientation to each of the cycles. Tutte, in fact, gave a necessary and sufficient condition for a graph G to have a q-factor. We summarize this discussion and his condition [part ( 3 ) ] in the following theorem (Theorem 2.4 of [ 11). Here, N ( S ) refers to the set of neighbors of a set S of vertices. Theorem 1.1. Let G be a graph. The.following conditions are equivalent: 1. V ( G )is a [ l , 11-totuldominatingset cfG. 2. G has a spanning subgraph which is a vertex disjoint union of edges and cycles ( a q-factor). 3. For every independent set I in V ( G ) , ” ( 1 ) I 2 1 1 1 ( Tutte’s condition). 2. THE [ k , 13 CASE Let k 2 2 and consider the case where G has a [ k , I]-set D . For convenience, we will consider the vertices of D in the directed graph G+ to be colored blue and the other vertices to be colored white. Each blue vertex thus has outdegree k , and G must have precisely kl DI vertices. Observe that exactly 1 / k of the vertices are blue and that no blue vertex dominates more than k leaves. Leaves must be colored white. Furthermore, since every white vertex is dominated by a blue vertex and every vertex of G + has indegree one, it follows that no pair of white vertices are joined by an edge in G+. If any blue vertex, say s, dominates exactly k leaves, we form a smaller directed graph by removing those k leaves and recoloring s white. This new directed graph still has exactly 1 / k of its vertices blue and inherits the original solution. We repeat this procedure until no blue vertex dominates exactly k leaves. In the resulting directed graph, every blue vertex dominates at most k - 1 leaves. Since 1 / k of the vertices are blue, each blue vertex must dominate exactly k - 1 leaves. We now observe that if all the leaves were deleted leaving the directed graph H + induced by the set of blue vertices, then V ( EI’) is a [ 1, I]-set, i.e., the set of vertices of H + induces a q-factor. Conversely, to construct a graph with a [ k , 11-set, start with a q-factor and color these vertices blue. Attach k - 1 white leaves to each blue vertex. Repeat the following step as often as desired: Select a white vertex s and attach k white leaves to it and then recolor s blue. Finally, arbitrarily add any set of (nonessential) edges to the graph. We summarize the preceding discussion in the following theorem: Theorem 2.1. Every graph G with a [ k , 11-set can be constructed from a qfactor by using the procedure described above. In the case of trees, the following polynomial algorithm can be used to recognize whether or not a given tree has a [ k , 1]-set. Within the algorithm, a vertex x has no color ( c ( x )= NC) assigned to it until it has been dominated at which point it is colored red ( c ( x )= R).An integervalued variable n ( x ) is maintained for each vertex x to indicate the number of other vertices x has been forced to dominate. If n ( x )= m , then x has dominated k - rn other vertices. Algorithm 2.2. Tree Recognition. Input: A tree T and a positive integer k > 1. Output: Answer to the question, “Does T have a [ k , 11set?” 1. For every vertex v in T, let n ( V ) = k and let c( V 2. Answer + YES. 3. While I TI > 1 and Answer = YES: )= NC. Choose a leaf x of T and its neighbor s; [ f n ( x )4: { 0, 1, k } , then Answer + NO; J f n ( x ) E{ 0 , 1, k } , c(x) = N C a n d n ( s ) = 0 , then Answer + NO: If‘n(x)E ( 0 , k } , c(x) = NC and n ( s ) 2 1 , then n ( s ) + n ( s ) - 1 and T + T - x; J f n ( x )= 1 , c ( x ) = NC and c(s) = R, then Answer NO; Z f n ( x ) = 1, c ( x ) = NC, c ( s ) = N C a n d n ( s ) 2 1 , then c(s) + R, n ( s ) + n ( s ) - 1 , and T + T - - X,’ Zfc(x) = R and n ( x )E { 0, k } , then T + T - x; I f c ( x ) = R, n ( x ) = 1 a n d c ( s ) = R, then Answer +NO; STAR-FACTORS AND k-BOUNDED TOTAL DOMINATION !f’c(x) = R,n ( x ) = 1 a n d c ( s ) = NC, then c(s) + R, T + T - X ; End While 4. IfAnswer = YES and T = { w} such that c( w ) = NC or n( w) 4 { 0, k}, then Answer + NO. Note that for a given tree T if m is the maximum number of leaves adjacent to any vertex in T then T can have a [ k , I]-set only if m I k I m 1. Hence, one can recognize trees which have a [ k, I]-set for some value of k by determining m initially and then applying the algorithm twice, once with k = m and then with k = m + 1, i.e., only the tree itself is required as input to the algorithm. + 3. k-BOUNDED TOTAL DOMINATION Suppose that we are given a graph G and an integer k 2 1. In this section, we are interested in whether or not G has a ( k , I]-set. We will need the following definition and notation: A k-bounded star packing of G is a subgraph of G consisting of vertex-disjoint components where each component is a star having at least one but no more than k edges. If S is such a k-bounded star packing of G, then we let S, be the set of i-stars in S , where an i-star is one with exactly i edges. Thus, we get the disjoint union S = S, U S2Us - U S,. Let R ( S ) = { x E V ( G ) ( xdoes not belong to any S, ), let t(S) = I R ( S ) I , and set t = min { t ( S ) 1 S is a k-bounded star packing of G} . We call S an optimal k-bounded star packing of G if t ( S ) = t. If t ( S ) = 0, then S will be called perfect. A perfect kbounded star packing is thus a spanning forest of nonempty stars, none of which contains more than k edges. Spanning subgraphs are commonly called factors, and so in this case, we use the more descriptive term k-bounded star-factor. As an illustration, K2,3 has a 2-bounded star-factor whereas K2,5does not. An optimal 2-bounded star packing of K2,5would omit a single vertex. A graph has a 1-bounded star-factor precisely when it has a perfect matching. We shall say that a graph G has the Tk-property if for every independent set Z of vertices it follows that k I N ( I ) I 2 I 11. Observe that when k = 1 the TI-property is the Tutte condition of Theorem 1.1. We first establish the equivalence of this generalized Tutte condition and the existence of a k-bounded starfactor for values of k at least 2. Note that k must be larger than 1 since C, has the TI-property but does not possess a 1-bounded star-factor (i.e., a perfect matching). - 199 Theorem 3.1. Let k 2 2 , and let G be a connected graph. G has a k-bounded star-factor if and only ifG has the Tkproperty. Proof 1. Assume that G has a k-bounded star-factor S consisting of stars H I , H 2 , . . . , H,. Let I be an independent set in G. Let I, = I n H, and N, be the set of neighbors of I, that lie in H,. Note that N, c N ( I , ) and SO k I NJ 1 Ik 1 N( I,) 1. Since each H, is an m-star with 1 Im I k, we must have klN,( 2 141. Note that U N/ E N ( I ) and Z = U I, (both are disjoint unions). Thus, This implies that G satisfies Tk.Observe that the condition of connectivity is not required for the proof of this part of the theorem. 2. Now assume that G has the Tk-property. We wish to show that every optimal k-bounded star packing of G is, in fact, perfect. Let S be an optimal k-bounded star packing in G and, as before, let S, denote the set of istars in S. Let C be the set of vertices which are the centers of the stars in S k , and let P be the vertices of the k-stars which are not in C . First observe that we may assume without loss of generality that the set P i s independent except possibly in the case k = 2 when the 2-stars may induce triangles. For suppose there exists an edge joining two vertices w1 and w 2 of P . If wI and w2 belong to two distinct kstars H I and H,, respectively, then by adding the edge wlw2 to the set of 1-stars and by deleting wI and w2 from H I and H, [thereby replacing two k-stars with two ( k - 1 )-stars] the number of edges joining vertices of P can be reduced. Similarly, if w1 and w2 belong to the same k-star H , with k 2 3 , then by adding the edge w1wZ to the set of 1-stars and replacing H , by the ( k - 2)-star which is obtained by removing wI and w2 from H I the number of edges induced by P can be reduced. Thus, we assume that when k 2 3 , S is an optimal k-bounded star packing of G in which P , the set of leaves of the k-stars, forms an independent set. If this S is not perfect, then let r E R(S ) . Note that r cannot be joined to another vertex in R ( S )or else another 1-star could be added to S , contradicting the optimality of S . The optimality of S also guarantees that r is not adjacent to any vertex in a l-star. If r were adjacent to a vertex x which is a leaf in a star in S, with 2 I iI k, then the i-star could be replaced by an ( i - 1 )-star (remove x from the i-star) and the l-star r x . Finally, r could not be joined to the center of any m-star with m < k; otherwise, r could be added to form an ( m 1)-star. Hence, vertices of R ( S ) can only be adjacent to members of C. + 200 GUNTHER, HARTNELL, AND RALL Let C1be the set of vertices in C which are joined to at least one vertex in R ( S ) ,and let PI be the set of leaves of the k-stars whose centers belong to CI. AS noted abo$e, no member of PI czn be adjacent to a vertex in R(S ) . But consider, for some r E R ( S ) , a vertex u , E C1for which there is an edge from r to u1 and the set of vertices, say P', E P I , which are the leaves of the k-star H of which u1 is the center. No vertex of P f I ,say z1, can be joined to a vertex of a 1 star in S1 or else that 1-star could be replaced by a 2star (obtained by adding z,to the I-star) and the kstar formed from H by deieting z , and adding the leaf r . This would contradict the optimality of S . Similarly, z1 cannot be adjacent to any leaf, say z2, of an m-star, M , with 2 I m Ik . For if this were the case, then, again, the optimality of S is contradicted by adding the I-star zIz2, replacing A4 by A4 - z2, and replacing H by the k-star formed by deleting zIand adding leaf r . Finally, it is clear that z,cannot be adjacent to the center of an m-star with m < k. Hence, the only possible vertices which can be adjacent to members of P I are centers of k-stars in S,. Let C2 denote those centers of k-stars which are not in C, but which are adjacent to at least one vertex of PI. Let P2 be the set of leaves of the k-stars whose centers belong to C,. As above, it is readily seen that vertices in P2 can only have additional edges to centers of k-stars in S, . Let those centers which are not in C1 U C2,but to which vertices of P2are adjacent, be denoted by C, . By repeating this analysis, we must have, at some stage, a set C, of centers of k-stars with the set of adjacent leaves P, such that no vertex in P, is adjacent to a vertex outside U:, I C, ;i.e., Z = R ( S )U PI U * U P, is an independent set in G with N ( I ) = .- ct . Since G satisfies T A we , must have klN(Z)I 2 I ZI = - / R ( S )u P, u. . U P, = IR(S)I + IP1 1 But by the way they were chosen from the set of kstars,itfollowsthat IP1U . . . U P , I = k l C , U - - - U C, 1 . Thus: I R ( S ) I = 0 and so S is perfect. C5 shows that a graph can have a ( I , I]-set and yet have no 1-bounded star-factor. But if G has a I-bounded star-factor ( a perfect matching), then G has a q-factor, and, hence, by Theorem 1.1, G has a [ 1, 11-set. The following theorem shows that it is only in the case where k = 1 that these two concepts differ: Theorem 3.2. Let k 2 2 . A graph G has a (k, I]-set if and only if G has a k-bounded star-factor. Proof: Assume that G has a k-bounded star-factor S . Let D be the set of vertices consisting of the center and exactly one leaf from each star in S . Since S is a spanning subgraph, D is a ( k , I]-set for G. We prove the converse by induction on the order of the graph G. The truth of the statement for graphs of order less than 4 is easily checked. We thus assume that n 2 4 is an integer and that any graph of order at most n which has a ( k , I]-set also has a k-bounded star-factor. Now let G be a graph with n 1 vertices which has a ( k , I]-set D . As before, denote the resulting directed graph G + . If G is not connected, then apply induction to the individual components of G. The union of the resulting star-factors will be a k-bounded star-factor for G. If G + has bidirected edges, replace each one by two edges, one in each direction. Since each vertex of G+ is dominated exactly once, G+ must have precisely n 1 edges. It follows that G +has exactly one (directed) cycle, say C. Let B be the set of vertices not on C which are adjacent to at least one leaf. If B is not empty, then select a vertex x in B such that no vertex in B is at a greater distance from C. The vertex x and all the leaves it dominates form a star H of size at most k. Apply induction to obtain a k-bounded star-factor of the smaller graph G - H . This together with H is a k-bounded star-factor of G . Thus, assume that B is empty. It follows that all stems (vertices adjacent to a leaf) of G must be on C. If G has no stems, then G = C , and so it has a 2-bounded starfactor. Otherwise, let v be a stem and let u be a vertex on C which dominates v. If u is also a stem, then delete the star F consisting of u and the leaves it dominates from G and add a new (directed) edge w v where M' is a leaf in G dominated by v. The star F together with the k-bounded star-factor obtained by applying the induction hypothesis to the smaller graph yields a k-bounded star-factor of G. If u is not a stem and y on C dominates u , then delete the star F consisting of u , y and any leaves dominated by y . Add the new edge w v and proceed by induction as in the above case. + + + 4. THE BIPARTITE CASE As we observed in the previous section, Theorem 3.1 is not valid for general graphs when k = 1. We do know, however, that if G = G ( A , B ) is a bipartite graph which satisfies T I ,then G does possess a perfect matching; this is precisely the Marriage Theorem. Just as the building blocks in a perfect matching are vertex-disjoint edges, which could be thought of as 1-stars, so the building blocks of a k-bounded star packing are vertex-disjoint stars. While, in general, these stars need not be of uniform size, the following theorem gives a generalization of the Marriage Theorem. STAR-FACTORS AND k-BOUNDED TOTAL DOMINATION 201 Theorem 4.1. Let G = G ( A ,B ) be a connected bipartite graph in which k I B 1 = I A I, where k 2 I . If G satisfies the Tk-property, then G has a k-bounded star-factor in which all the stars are of size k. Proof.’ When k = 1, the statement is just the Marriage Theorem. Assume that k 2 2 and assume that G is a graph satisfying Th. By Theorem 3.1, G has a k-bounded starfactor S . We first observe that all the stars in S must have their centers in B. Assume that one of these m-stars, 1 5 rn 2 k , has its center in A . Deleting this star would yield a smaller bipartite graph H(A’,B’) which still has a k-bounded star-factor. By Theorem 3.1, H ( A ’ ,B’) satisfies l k . But I A’I = J A )- 1, (B‘I = IBI - m a n d N ( A ’ ) c B’. Hence, klB’I k(N(A’)I I = klB( - krn This contradicts the Th-property. Thus, all stars in the packing must have their centers in B.There must therefore be exactly 1 BI stars in S , and each star must include exactly k vertices from A since every vertex in G belongs to exactly one star in S . It now follows that all the stars in S must, in fact, be k-stars and the result is established. rn While it is omitted here, it is straightforward to show that in the bipartite case singled out in Theorem 4.1, where k I B 1 = I A I, G satisfying the Tk-property is equivalent to I N ( J ) ) 2 klJl for every subset J of the smaller color class B. But then IN(J)I 2 I J ( for every J G B and by the theorem of Hall [ 2 ] there must be a matching of B into A . Thus, one could apply a bipartite matching algorithm (see p. 15 of [ 4 ] , e.g.) to remove a maximum matching from G as a j r s t step toward finding the uniform size, k-bounded star-factor guaranteed by Theorem 4.1. If the hypothesis of Hall’s Theorem held at each successive step, then k applications of this simpler algorithm would yield the star-factor of G. To see that this is not necessarily the case, consider the graph of Figure 1 . G satisfies T 2 .If the bipartite matching algorithm first selects the edges aw, bx, g y , and hz and removes them from the graph along with the set of vertices { a , b , g , h ) which must necessarily be leaves in any 2-bounded star-factor of G , then the remaining graph does not satisfy Hall’s condition. However, assume that G = G ( A ,B) satisfies the hypothesis of Theorem 4.1 and let G‘(A, B’) be the bipartite graph obtained from G by replacing each x E B with a set of k vertices x,,x2,. . . , q ,where each x,has the same neighbors in G‘ as x has in G. Since G has the Tk-property,it can be shown that I N,!(J) I 2 1 JI for every subset J of B‘. The bipartite matching algorithm can now be applied to obtain a perfect matching of the graph G‘. This perfect matching then gives a k-bounded star-factor of G by using the k-star with edge set Fig. 1. A graph G where repeated application of maximum matching algorithm may fail. { x u , ,xu2, . . . , xah} where x E B and where the edges x l a l , x2a2,. . . , x& belong to the perfect matching of G‘. In the case where k JBI = IA 1, these results allow the following interpretation: Suppose that B is a set of n committees and A is a set of kn individuals. When k = 1, construct the bipartite graph G ( A , B) in which individual x E A is adjacent to committee y E B when x is qualified to serve as chairperson of y . In this case, Tutte’s condition is necessary and sufficient to guarantee that each committee will end up with a competent chair, with no individual chairing more than one committee (Mamage Theorem). When k > 1, construct the bipartite graph G ( A , B) in which x E A is made adjacent to y E B when x i s qualified to serve on committee y . Now the problem can be viewed as selecting exactly k members for each of the n committees with no member serving on more than one committee. Thus, we see that in this case Theorem 4.1 is a generalization of the Marriage Theorem. REFERENCES [I] [ 21 [ 31 [ 41 [ 51 G . Gunther, B. Hartnell, and D. Rall, A restricted domination problem. Congress. Num. 94 ( 1993) 215-222. P. Hall, On representatives of subsets. J. Lond. Math. Soc. 10 (1935) 26-30. S. Hedetniemi and R. Laskar, Topics on domination. Ann. Discr. Math. 48 ( 1991 ). L. Lovkz and M. Plummer, Matching theory. Ann. Discr. Math. 29 (1986) 15. W. Tutte, The 1-factors of oriented graphs. Proc. Am. Math. SOC.4 ( 1953) 922-931. Received January 26, 1994 Accepted September 12, 1995

1/--страниц