вход по аккаунту


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.
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
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
( 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:
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
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;
!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
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
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
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
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).
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
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.
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 *
P, is an independent set in G with N ( I ) =
ct .
Since G satisfies T A we
, must have
/ R ( S )u P, u. . U P,
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
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.
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.
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,
k(N(A’)I I
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.
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.
[ 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
Без категории
Размер файла
492 Кб
simple, shortest, problems, intervaly, pairs, graph, algorithms, path
Пожаловаться на содержимое документа