Sequential diagnosability is co-NP complete

584

IEEE TRANSACTIONS ON COMPUTERS, VOL. 40, NO 5, MAY 1991

Sequential Diagnosability is CO-NP Complete Vijay Raghavan, Member, IEEE, and Anand Tripathi, Member, IEEE

Abstract-The question of determining the sequential diagnosability number of system in the PMC model has remained open since it was first formulated two decades ago. We show that this problem is CO-NPcomplete. The problem is also shown to be coNP complete even when restricted to planar graphs both in the weighted and the BGM models. Zndex Terms- Fault diagnosis, NP-completeness, PMC and BGM models for system diagnosability, sequential diagnosability. I.

INTRODUCTION

A

PAPER by Preparata, Metze, and Chien [19] introduced a graph-theoretical model for fault diagnosis. In the two decades since the introduction of the PMC model, significant progress has been made in the theory associated with the model and its offshoots [6]. Notwithstanding this success, several questions raised in the seminal paper have not been resolved satisfactorily. Perhaps the largest number of unresolved issues are related to sequential diagnosis, a concept introduced mainly to avoid the excessive testing necessary to support one-step diagnosis. (See [2], [4], [5], [7], [13]-[16], [20], [22], and [18] for more details on sequential diagnosis. In the sections to follow, we formalize the notion of sequential diagnosability. We settle the question central to this issue, viz., that of determining the sequential diagnosability number of a system by showing that the appropriate decision problem is CO-NPcomplete. The same problem in the related BGM model [2] is also shown to be CO-NPcomplete. (Note that the one-step diagnosability number can be determined in polynomial time in both models [17], [21], [26].) 11. THE PMC AND BGM MODELS, FORMALCONCEPTS AND DEFINITIONS A self-diagnosing system is one in which the units are capable of testing a subset of the other units. We concern ourselves neither with the precise nature of these tests nor with how and when they are actually administered, beyond insisting that they be complete, i.e., a fault-free unit should always correctly identify the units it tests as being faulty or fault-free. The outcome of the tests may be classified simply as “pass” or “fail,” indicating that the testing unit evaluates the tested unit as being fault-free or faulty, respectively. We assume that the evaluation is meaningful only if the testing unit itself is faultfree, otherwise the outcome is unreliable. This assumption is known as the symmetric invalidation assumption and forms the Manuscript received June 15, 1988; revised September 10, 1990. V. Raghavan is with the Department of Computer Science, Vanderbilt University, Nashville, TN 37235. A. Tripathi is with the Department of Computer Science, University of Minnesota, Minneapolis, MN 55455. IEEE Log Number 9143277.

basis of the PMC model. The alternative, used in the BGM model, is the asymmetric invalidation assumption, wherein a ‘‘passjj necessarily implies that the tested unit if fault free, but a “fail” outcome only implies that either the tested unit or the testing unit or both are faulty. The rationale behind this latter assumption [2], [12] is that a complete test in systems composed of complex units entails the checking of a large number of responses from the tested units. Therefore, it is extremely unlikely that the faults in the units performing the test would completely cancel the faults in the unit under test, causing a test to pass when it should have failed. This assumption is the only difference between the PMC and the BGM models. The test system is modeled as a directed graph G(V,E ) , with the units represented by vertices in the graph and the tests by directed edges. Thus, if (i, j ) is a directed edge from unit U, to unit u3, the unit U,tests the unit u3. This directed graph is called the connection assignment of the system. Weights are assigned to edges depending on the test outcomes: the weight uZ3associated with the edge (2, j ) is defined as follows: 0 if U, tests u3with outcome puss “3 = 1 if U, tests ujwith outcome fud.

I

Note that if uZJ is 1, at least one of U, and uj must be faulty; if aZ3is 0, the interpretation of this test result depends on the model used: in the PMC model, if u3is faulty, then so is ut, whereas in the BGM or asymmetric invalidation model, aZ3being 0 necessarily implies that uJ is nonfaulty. The set of test outcomes is called the syndrome of the system. There are 21EI possible syndromes for any connection assignment. Several diagnosability measures have been proposed for both models. We shall concern ourselves with only the following intuitive definition, formalized later. Definition 1 [19]: A system of n units is sequentially t-diagnosable if at least one faulty unit can be identified without replacement provided the number of faulty units present does not exceed t. The example below illustrates the method used to prove that a given system is sequentially t-diagnosable. Example: Consider a system composed of 5 units ul, uz,’ . . ,us whose connection assignment is a loop. A syndrome for this system can be represented as a 5-bit vector ( ~ 1 2 a23, , u 3 4 , u45, ~ 5 1 ) .Refer to Fig. 1. This system is sequentially 2-diagnosable in the PMC model as we now show. Every 2-fault situation must have two adjacent fault-free units. So there will be some edges with weight 0, say, u12. If either a34 or a45 is 1, then u2 must be faulty-free (otherwise there will be at least 3 faulty units). If both a34 and a45 are 0, then u5 must be fault-free. So we can

0018-9340/91/0500-0584$01.00 0 1991 IEEE

585

RAGHAVAN AND TRIPATHI: SEQUENTIAL DIAGNOSABILITY IS CO-NP COMPLETE

Definition 3: F C V is a consistent fault set for the syndrome U in the BGM model iff neither a) nor b) below holds: a) a(u,w) = 0 where w E F b) U ( U , V ) = 1 where U , w E V - F . We follow the terminology used in [7] to define a class of fault sets consistent for a syndrome a. Definition 4: F, = { F : F is a consistent fault set for a } . Definition 5: F,,t = { F : F E F , & IF1 5 t } , where

w

Fig. 1. A single loop system.

identify one fault-free unit in either case. We then follow the edges around the loop, starting with the fault-free unit, until we come to an edge with a weight of 1. The unit “pointed-to” must be faulty. That this same system is sequentially 2-diagnosable in the BGM model also is easy to see. As before, in any 2-fault situation there must be at least one edge with weight 0, say a12. This would necessarily imply that uz is fault-free in the BGM model. Just following the edges around the loop until we come to one with a weight of 1 would suffice to find a faulty unit. Note that in both models 2 is the limit of attainable sequential diagnosability. 0 Using an elegant generalization of the technique presented in the example above, it has been shown that a single loop system has a diagnosability of t provided that the number 1 in the PMC model, at of units is at least least 2t 1 in the BGM mo el [2], [19]. Not surprisingly, it turns out [23] that any strongly connected directed graph has at least the amount of diagnosability of a single loop system with the same number of units. Determining the exact diagnosability for arbitrary connection assignments is altogether a different matter. The technique used in single loop systems is completely inadequate for more complex systems. To complicate matters further, despite the apparent similarity of the two models, polynomial time algorithms or intractability proofs used in one model do not easily carry over to the other. For example, the approaches used to determine the one-step diagnosability number in the two models [17], [21], [26] are vastly different. A problem CO-NPcomplete in the BGM model but solvable in polynomial time in the PMC model can be found in [24] and [25]. The intuitive notions of syndromes and consistent fault sets presented in the example are now refined. Let G(V,E) be a directed graph. A function a : E + (0, 1) is said to be a syndrome for G. If ( U , w ) E E, we prefer to write a(u, v ) rather than a((u, w)). Definition 2: F & V is a consistent fault set for the syndrome U in the PMC model iff neither a) nor b) below holds: a) ~ ( u , w = ) 0 where u E V - F & w E F b) a(u,w) = 1 where u,w E V - F .

+

I( y)l+

t

E

z+.

The definition of F,,t allows the following precise definitions of a “t-fault sitatuation” and sequential diagnosability, which formalize Definition 1. Definition 6: A syndrome U occurs in a t-fault situation iff F,,t contains at least one nonempty set. Definition 7: G(V,E ) is sequentially t-diagnosable iff for F # 0. every syndrome a for G in a t-fault situation, nFEF,,{ Definition 8: The sequential diagnosability number of G(V,E) is the largest integer t, for which G is sequentially t-diagnosable. We introduce a new concept in this paper to provide a technique for examining sequential diagnosability. We note that if G(V,E) is not sequentially t-diagnosable, then there must be a syndrome U and consistent faults sets F1, F z , . * ,F, of size 5 t such that n L I F i = 0. As a matter of fact, there could be many such syndromes. We are interested in a particular syndrome which minimizes the number r of consistent fault sets of size 5 t whose intersection is empty. This motivates the following. Definition 9: A syndrome U for G is t-critical iff, among all the syndromes U’ that satisfy nFEF,,,{F = 0, the syndrome a has the minimum number T of consistent fault sets F1, F z , . . ., F, of size 5 t such that n:==,Fi = 0. The sets F1, Fz, . . . ,F, are called a minimum t-certificate for U .

111. CO-NP COMPLETENESS OF SEQUENTIAL IN THE PMC MODEL DIAGNOSABILITY Determining the sequential diagnosability number of a system is an intriguing graph-theoretical problem. Earlier attempts (see, for example, [4], [13]) have concentrated on some kind of exhaustive search or obtaining a “conditional diagnosability number,” a lower bound on the actual sequential diagnosability number. Although no effective algorithm is presented to obtain the conditional diagnosability number for general systems, it is interesting to note that it can indeed be obtained by modifying Sullivan’s one-step diagnosability algorithm [26]. We omit the details since the conditional diagnosability number is too generous a lower bound in many cases. The following four lemmas provide the intuition behind the construction used in the proof of the main theorem in this section. For all four lemmas, assume that G(V,E) is a strongly connected directed graph which is not sequentially t-diagnosable and that 0 is a t-critical syndrome (which occurs in a t-fault situation) with a minimum certificate of the T sets F1, Fz, ,F,. Furthermore, denote by Yj, 1 5 j 5 T , the intersection of the (T - 1) fault sets e . .

Fl , Fz , . . . ,Fj- 1 , Fj+l, .. . ,F,.

IEEE TRANSACTIONS ON COMPUTERS, VOL. 40, NO. 5, MAY 1991

586

Lemma I : Every vertex U E V is in at least one of the fault sets F1, F2,...,F,.. Proof: Suppose to the contrary, that U is a vertex which does not belong to any of F1, F2,. . . , F,., i.e., v is nonfaulty as far as F l , F2, . . . , F,. are concerned. By the definition of a t-fault situation, at least one of F1, F2, ’ . . , F,., say F I , is nonempty. Since G is strongly connected, there is a path v + v1 + v2 + . . . + W k , where w, VI, v2,”.,vk-1 are not in F1 but w k is. Therefore, o(v,w1) = ~ ( w 1 , v 2= ) ... = U ( V k - 2 , W k - 1 ) = 0 and U ( V k - 2 , V k ) = 1 and 7Jk E n;=’=,F,, by the definition of consistency of the fault sets F1, F2, . . . , F,. This is a contradiction since n;=’=,F; is supposed to be empty.0 Lemma 2: None of Y1,Y2,’ . . , Y, is empty. Proof: Ifsome?, 1 5 j t. Proof: Without loss of generality, consider the two sets F1 and F2. (The proof for any other pair follows along the same lines.) Let F = FI U F2 - (Y1 U Y2). See Fig. 2 Suppose, contrary to the lemma, that IF( 5 t. Consider a new syndrome a’ defined (over all ( x , y ) E E ) by

a’(x,y) =

{;

if x,y E Y1 U Y2 if y E F & x E Y1 U Y 2 ~ ( xy), otherwise.

Fig. 2. The structure of sets used to construct

d.

is Y1 U Y2, and u’(x, y ) is defined to be 0 if both x and y are in Y1 U Y2. If iv), then d ( x ,y) = ~ ( xy),= 0 (else x,y are in Y1 U Y2, and therefore belong to V - F.) Again, we may assume that x E F1 U F2 - F , since anything else would imply that at least one of F1, F2 is not consistent for U . But F1 U F2 - F is Y1 U Y2, and d(x,y) is defined to be 1 if x is in Y1 U Y2 and y is in F. Proof of 2):

nq-p

i=3

\

It can now be proved (see below) that 1) F, F3, F4,. ” , F, E F , I , ~and ,

2) n1==,Fin F = 0. However, this is a contradiction since U was supposed to be t-critical and F1, F2, . . . , F, a minimum t-certificate for U and yet 0’ has a smaller t-certificate. Proof of I ) : By supposition, IF1 5 t; and all of F3, F4, . . . , F,. have sizes 5 t since they are in F , , t . It remains to be shown that F3, F4, . . , F, and F are all consistent for U ’ . Suppose one of F3, F4, . . . , F,., say F’, is not a consistent fault set for U ’ . Then there must be distinct vertices 5 , y such that either i) x , y E V - F’ & a’(x,y) = 1, or ii) x E V - F’, y E F’ & a’(x,y) = 0. If i), then o’(xly) = 1 # o(xly), else F’ was not a consistent fault set even for a. Consequently, 5 E Yl U Y2, but then x must be in F’, a contradiction. If ii), then d(x,y) = 0 # ~ ( xy)., By the definition of d, both x and y belong to Y1 U Y2, and therefore to F’, again a contradiction. Now suppose F is not a consistent fault set for U ’ . Then there must be distinct vertices x,y such that iii) x , y E V - F & a’(z,y) = 1, or iv) x E V - F , y E F & ~ ‘ ( x , y = ) 0. If iii), then a’(x,y) = a ( x , y ) = 1 (else y E F ) . By supposition, x and y are not in F , but we may assume that x,y belong to Fl U F2 - F , since anything else would imply that at least one of F I ,F2 is not consistent for U . But Fl U F2 - F +

0 Lemma 4: If v E V is a vertex which has an edge directed to every other vertex in the graph, i.e., V u E V U # U 3 (w,U ) E E , then v belongs to exactly one of the sets Yl,Y2,. . . , Yr. Proof: The sets Y1,Y2,. . . , Y,. are all disjoint since n;=‘=,Fi = 0. Therefore, ‘U belongs to at most one of Yl , y 2 . . . , YT. Suppose v is not in any of Yl,Y2, . . . , Yr.Then there are at least two fault sets, say F1 and F2, to which U does not belong. Since F1 and F2 are distinct fault sets (by the minimality of r), one of F1 - F2 or F2 - FI is nonempty. Without loss of generality, suppose F1 - F2 is nonempty. Let U E F1 - F2. Since v has an edge directed to every other vertex in the graph, (w,u) E E. Now, if O ( V , U ) = 0, then F1 is not a consistent fault set, and if a ( v , u ) = 1, then F2 is not a consistent fault set. Since we get a contradiction in either case, our supposition that w belongs to less than ( r - 1) fault sets 0 must be false. In what follows, we assumed some knowledge of “NPcompleteness in the strong sense” and “pseudo-polynomial” transformations. These concepts were introduced in [9] and are further detailed in [lo]. The following restricted version of 3-Partition is shown to be NP-complete in the strong sense in the Appendix. We use this fact to prove the CO-NPcompleteness of sequential diagnosability. 5

587

RAGHAVAN AND TRIPATHI: SEQUENTIAL DIAGNOSABILITY IS CO-NP COMPLETE

NAME: 3-Partition with Restrictions. INSTANCE: Set A of 3m elements, a bound B E Z+, and a size s(a) E Z+ for each a E A such that f < s ( a ) < $ and such that C a E A s ( a = ) mB. RESTRICTIONS: a) m 2 4. b) B 2 mod 3. QUESTION: Can A be partitioned into m disjoint sets A I , A2, A 3 , . . . ,A , such that for 1 5 i 5 m CaEA, s(a) =

B? The problem of determining the sequential diagnosability number can be recast as a decision problem in the following manner. NAME: Sequential diagnosability in the PMC model (SEQPMC) INSTANCE: Directed graph G(V,E), and t E Z+ QUESTION: Is G sequentially t-diagnosable?

The proof of the co-NP completeness of SEQPMC is complicated and uses some delicate constructions. Therefore, we first provide a broad outline of the entire proof. Hopefully, this will supply the reader with the necessary intuition behind the techniques used and motivate a clear understanding of all the details. We use three well-recognized and standard elements in our proof of the CO-NPcompleteness of SEQPMC, much in the style of all such proofs. First, we demonstrate that SEQPMC is a member of the class CO-NP. This is straightforward and indeed trivial. Second, we take as input, an arbitrary instance of a known NP-complete problem-in our case, the problem is 3-Partition with Restrictions. We then show how the input instance can be transformed into an instance of the target problem, SEQPMC. In doing so, we must ensure that the transformation can be achieved in time bounded by a polynomial in the length of input instance. This is a subtle requirement, designed to prevent “cheating,” and it is only because 3-partition with restrictions is NP-complete in the strong sense that we meet this requirement. Let us explain why this is so. Notice that a compact encoding of the input instance will take O(m log B) bits only. However, our transformation to SEQPMC will construct a graph on N = (6mB + 3m) vertices. Specifying this graph would take space polynomial in N and hence the transformation itself will take time polynomial in N . Now if B is exponential in m, we see that we cannot bound N by any polynomial in m log B, the length of the input instance. However, because of NP-completeness in the strong sense, 3-partition with restrictions remains NP-complete even when B is no more than a polynomial in m. Therefore, our transformation is valid because we can then bound N by a polynomial in the length of the input instance. A transformation which uses this subtlety is called a “pseudopolynomial” transformation and four requirements for a legal pseudo-polynomial transformation are laid out in [ l o ,p. 1011.l ‘Normally, pseudo-polynomial transformations are used to show that “number” problems are NP-complete in the strong sense. However, we use a pseudo-polynomial transformation here to show the intractability of SEQPMC,

The third element of our CO-NPcompleteness proof is the demonstration that the transformed instance of SEQPMC is not sequentially t-diagnosable if and only if the input instance has a 3-partition. The “if” part of the proof is quite easy: we simply suppose that a 3-partition exists in the input instance and use that to construct a syndrome and consistent fault sets for the syndrome which show that the target instance is not sequentially t-diagnosable. A reader familiar with these techniques should find the proof up to this point fairly straightforward. The “only-if” part of the proof is surprisingly more difficult. Indeed, it is only this part of the proof which vindicates all the delicate constructions used, including the restriction of B being congruent to 2 mod 3. We now give a “bird’s eye-view” of the modus operandi used in this part of the proof, designed to make the reading and verification easier. What we must achieve in the “only-if’’ part of the proof is a clear demonstration that the graph in the target instance of SEQPMC is not sequentially t-diagnosable only if the input instance has a 3-partition. Stated in other words, we must show that whenever the graph is not sequentially t-diagnosable, a 3-partition exists in the input instance. Herein lies a fundamental difficulty, which is a result of not having a good characterization of graphs that are not sequentially t-diagnosable. We are forced to discover some structure that exists in such graphs, working only with the knowledge that there is some syndrome o and some consistent fault sets F I ,F2, . . . ,F, in Fu, such that n;=.=, Fi is empty. We use the key concept of a t-critical syndrome as a basic tool at this point. We consider a t-critical syndrome (T for our graph and show that it forces a structure on the seemingly arbitrary nature of the fault sets F1, F2, . . ,F,. Part of this general structure enforced by such a syndrome is clarified in Lemmas 1-4, but there is more. The specific details of the constructions we have chosen in our transformation to SEQPMC enable us to conclude in a crucial intermediate claim that the T intersections of the sets F1, F z , . . ,F, taken (T - 1) at a time have an essentially simple structure. Finally, a simple pigeonholing argument using the fact that B is congruent to 2 mod 3 shows that the T - 1 wise intersections actually contain an encoding of the desired 3-partition. We are now ready to prove the main result of this paper. Theorem I: Sequential diagnostability in the PMC model is CO-NP complete. Proof: If G is not sequentially t-diagnosable, then there exists a syndrome (T in a t-fault situation, such that nFEF,,tF = 0. This means that V TJ E V, there exists at least one fault set F, E Fu,t such that v $! F,. Thus, given the syndrome 0 , and at most [VI fault sets, we can verify that the intersection of the fault sets is empty, and that each of the fault sets is in Fu, t . To verify that a fault set F is in Fu,t , we have to check 1) that IF1 5 t, 2 ) that there is no edge (u,v) E E with ( T ( U , T J )= 1 and u,u both in V - F , and +

a problem devoid of large numbers. This is surprising, but not unprecedented. The short proof of SUBFOREST ISOMORPHISM in [lo, p. 1051 shares the spirit of our co-NP completeness proof. We suggest that it be read first.

IEEE TRANSACTIONS ON COMPUTERS, VOL. 40, NO. 5, MAY 1991

588

c,

JT

...

c3

c2

-- -- - --- --

Fig. 3. The syndrome generated from a 3-Partition.

3) that there is no edge ( u , w )E E with U in V - F and w in F and o(u,w) = 0. Clearly, all the above can be done in time polynomial in IVI.Therefore, there is a polynomial certificate for G not being sequentially t-diagnosable, and SEQPMC is in CO-NP. To show that SEQPMC is CO-NP complete, we use a pseudo-polynomial transformation to reduce 3-partition with restrictions to the complement of SEQPMC. s : A + Z+, and B E Z+ Let A = {al,a2,a3,...,~3,,,}, define an instance of 3-partition with restrictions. Thus, all of the following are true: a) B 2 mod 3 b) Vu E A : < s ( a ) < c) C a E A s ( a = ) mB where m 2 4. Note that the least value of B that can satisfy a) and c) is 14. We use this later. A directed graph G(V,E ) is constructed from this instance of 3-partition as follows: V = C U D , where C = C1 U C2 U C, U . . .C,,,, D=D1UDzUD3U...D3_,andVZi,1 3m

+

+ 3 m B + 3m

r >m.

or

Claim 5: At most 2 C-vertices belong to ( r - 1) of the r fault sets F1, F2,. . . , F,. Proof of Claim 5: Let c be the number of C-vertices which belong to ( r - 1) of the r fault sets F1, F2, . . . , F,. Then

rt = 3 r ( m B + 1 ) 2

r

IF,I 2=1

To prove that X I is a consistent fault set for n, suppose, to the contrary, that it is not. Then either i) n(u,u)= 1 and U,U E V - X1 or ii) CJ(U,V)= 0 and U E V - X Z ,U E X1 must hold. Now, i) cannot hold since if D ( U , V ) = 1, then X1 must contain either U or U by the definition of X Z and CJ. If CJ(U, v) = 0 and v E X I , then U # Xl implies that U is not in I$ (otherwise D(U,U)= 1). Also, U # C - (C;U Cj U Ck) (since (T(u,v) = 1 in this case also). So we get a contradiction in both cases. Therefore, X I is a consistent fault set for CJ. Proofof2): Any D-vertex v is in exactly one of Y1,Y2,...,Ym,say l’i. By the definition of I$, U # X1 and therefore v cannot belong to n L l X l . Also, if U is a C-vertex it belongs to exactly one of X I ,X2, ,X,; since m 2 4, there are at least 3 of X I ,X2,. . . ,X , to which v does not belong. Therefore, nFEF,,tF G nLlXl = 0. So G(V,E ) is not sequentially t-diagnosable. +:Suppose G(V,E ) is not sequentially t-diagnosable. We must now show that a 3-partition exists in the input problem instance. Since G is not sequentially t-diagnosable, there exists a t-critical syndrome (T for G and a minimum t-certificate F1, F2, . . . ,F, for CJ.We first use a few immediate claims to expose the structure of the sets F1, F2, . . ,F,, from which the 3-partition can be demonstrated. The choice of CJ enables us to use Lemmas 1-4 to conclude: Claim 1: Every vertex v E V belongs to at least one of F1, F2, . . . ,F,. (This follows directly from Lemma 1 since G(V,E ) is strongly connected.) As in Lemmas 1-4, we define Yj, 1 5 j 5 r , to be the intersection of the (r - 1) fault sets F l , F2,. . . Fj-l, Fj+l . . . , F,. We will show that this definition of Yj is, in fact, identical to the definition used in the “e:” part of the proof, thus making the 3-partition clear. Claim 2: Every D-vertex occurs in exactly one of the r sets Y1,Y2,. . . ,Yr.(This follows from Lemma 4, since a D-vertex has an edge directed to every other vertex in our graph.) Claim 3: None of the r disjoint sets Y1,Y2,. . . ,Y, is empty. (By Lemma 2.) Claim4: r 2 m 2 4.

by Claims 1 and 2

2 ( r - 1)1D1+ IC1 = 3(r - 1 ) m B

1x21 = lGl+ lCjl+ ICkl+ ID1- ( P i 1 + Pjl+I D k l ) = 2 B - 3s(ai)

+ 1) 2

r

2

(T

- 1)1D1+ ( r - 1).

= 3(r - 1 ) m B

3r 2

(T

- 2)c

+ (r

-

+

IC1 - c 1)c + ( 3 m B

+ 3m. m > 4, which

+ 3m - c)

By Claim 4, r 2 implies that ( r - 2) is positive. If c 3, then 3r 2 ( r - 2)c 3 m 2 ( r - 2) ’ 3 3 . 3 = 3r 3 > 3r, a contradiction. We need to know one more fact about the structure of Y1,Y2,. . * ,Y, to expose the 3-partition. We use Claim 6 below to prove that the D-vertices which belong to any particular D,, 1 5 z 5 3m, must all belong to the same YJ for some 1 5 j r. Furthermore, we use Claim 6 to prove that if there is any C-vertex at all in the sets Y ~ , Y ~ ,,Y,, - Sthen . such a C-vertex must necessarily belong to the same YJ as do the corresponding D-vertices. More precisely, we have the following claim. Claim 6: Let U,v be any two distinct vertices of C, U D, which belong to Y = U,T=1y3, for any arbitrary 2, 1 5 i 5 3m. Then both U and v belong to the same I$ for some 1, 1 < 1 5 r . Proof of Claim 6: Since all the K’s are disjoint, U belongs to exactly one of Y1,Y2,. . . ,Y, and v belong to exactly one of YI, Y2, . ,Yr. Suppose, contrary to the claim, that U and U belong to distinct YL sets, say Y1 and Y2, respectively. We now show that IF1 U F2 - (YIU Y2)l < t directly contradicting Lemma 3. To do this, we first establish the following subclaim: Subclaim: If U and v are distinct vertices of C, U D, in YI and Y2, respectively, then the C- and D-vertices of C, U D, not in Y1 U Y2 must be in Fl n F2. In other words, (Ci U 0%) - (Yi U Y2) G (Fi n F2). Proof of subclaim: Let w E (C, U 0 %-)(Y1 U Y2).See Fig. 4. Then, by the construction of E , we have a 2-cycle between each pair of the three vertices U ,v,w.Now, if x and y are any two vertices which have a 2-cycle between them in G, then a ( z , y ) = a ( y , z ) must hold. (Otherwise, if for example, ~ ( zy), = 0 and ~ ( yz) , = 1, then z must definitely be faulty, and therefore belong to every consistent fault set for (T, violating the fact that n;=‘=,F, = 0.) Now U E Y1. Therefore, D(W,U) cannot be 0, otherwise w must be in every fault set containing U, i.e., every fault

+

<

>

+

+

IEEE TRANSACTIONS ON COMPUTERS, VOL. 40, NO. 5, MAY 1991

590

mi = 3 for all i, 1 5 i 5 r . Moreover, if c > 0, then at most can contain exactly m;B vertices. one Before we prove Claim 7 it is convenient to show that it actually leads to the desired 3-partition. First note that if c > 0, Claim 7 would imply

x

r

~~B+~=IYI=CIY,I i=l

c T

2

miB

+ ( r - 1)= 3mB + ( r - 1).

i=l

<

Now since r 2 4, and c 2, the above inequality cannot be satisfied. Therefore, we must conclude that c = 0. But then Claim 7 implies that

Fig. 4. Illustrating Claim 6.

set except Fl but we know that w $Z Y1 and w certainly T r does not appear in all fault sets. Consequently, both o(w,u) 3mB = J Y ( = 2 X m i B = 3mB. (12) and o ( u , w ) are 1. Similarly, both o(w,'u) and o('u,w) are i=l i=l 1. Therefore, U E Y1 U $Z F1 w E F1. Also, The above inequality can only be met with exact equality and U E YZ=+ U $Z FZ =-+ w E F2. Consequently, w E F1 n Fz. then only if = miB for all i. Using Claim 7 again, we Let F = F1 U Fz - (Y1 U Y2).Observe that can then infer that mi = 3 for all i (i.e., each Yi contains IF1= IF11 IF21 - IF1 n Fz1 - IYl U YZI exactly 3 D-regions and no other vertices) and that [Y,I = 3B. Consequently, r = m. Finally, note that if Y , contains the I 2t - (IF1 n Fzl lyi U Yzl). regions Dj, Dk, and DI, then Now using the facts that ui=3Yk C F1 f l FZ and that 3B = = lDjl+ (Ci U Di) - (Y; U Yz) Fl nFz, we can rewrite the above as IDIJ = 3 ( s ( a j ) s(ak) s ( a l ) ) . IF1 5 2t- C; U Di U Yk . Therefore, s ( a j ) + S(ak) s ( a ~ = ) B for each such block and k=l Z1,Z2, . . . ,ZT as defined above is the desired 3-partition. By Claim 2, D C Ui=,Yk. Therefore, J F J5 2t-(lCil + ID]). Only the following remains. Since 1DJ = 3mB and t = 3mB + 3, it follows that Proof of Claim 7: Consider the following inequality inIF1 5 t 3 - [Cil. Finally, recalling that (C;l = 2B - 3s(a,) volving the cardinality of each Fi, 1 5 i r . 1, s ( a i ) < f , and that B 2 14, we can conclude that t = 3(mB 1) 2 (Fil IF1 < t.

1x1

*

1x1

+

+

1x1

1

+

(J

1

+

+

+

<

+

This ends the proof of Claim 6. Let us pause to identify the structure of the sets YI, Y z ,. . . ,Y, that has been identified thus far and to map out the further course of the proof which will lead to identifying the existence of the 3-partition in the input instance. By Claim 6, each of the D;-regions is completely contained in some Yj, 1 5 j 5 r . Also, by Claim 5 , at most two C-vertices are in the sets Y1,Y2, . . . , YT.Again, by Claim 3, none of the sets Y1,Yz,. . . , Y, can be empty and if a set Yj contains a Ci-vertex at all, it must also contain the corresponding Di set completely. Therefore, we can conclude that each of the sets Yl,Yz,. . . ,Yr contains at least one Di-region completely and the following definitions are wellfounded. mi = I&\,

+

1 5 i 5 r , where Zi = {aj E A : Dj E Y,}.

That is, m; is the number of Dj-regions contained in and Zi is the set of those elements aj in the 3-partition instance which correspond to each Dj-region in Y,. Our goal is to show that r = m and that 2 1 , Z 2 ,. . . , 2, defines a 3-partition in the input instance. To this end, we define c to be the number of and use the following fact. C-vertices in Y = U;=.=,Yi Claim 7: Each Y;, 1 5 i 5 r contains at least miB vertices. If all the Yi's contain exactly m;B vertices then c = 0 and

2 ( l Y ( - (XI)+ (2Bmi - 1x1+ m i ) .

This inequality follows directly from the following observations. a) Y - Yi C_ F;, by definition. contains mi regions of D and for each such region b) Dj, 1 5 j 5 3m, all the vertices of Cj not in Y , must be in Fi. (This is because there is a 2-cycle between each vertex of Cj and each vertex of Dj by construction. If U is a vertex of Cj not in Yi and U is a vertex in Dj and consequently Y,, then o ( u , u ) = u ( u , u ) = 1. Since U is not in Fi, v must be in Fi by the consistency of F;.) Also recall that lCjl = 2B - (Djl 1. Therefore,

+

3(mB

+ 1) 2 (IY 1 - lY,I) + (2Bm;- 1x1+ mi) 2 (ID1 + c - lKl) + 2Bm; - 1x1+ m i .

Using ID( = 3mB and rearranging the above, we get 21Y,I 2 2Bmi +mi + c - 3.

(1)

Now observe that 1) If mi 2 4, then 2 miB + 1 (since both sides of (1) are integers). 2) If mi 2 3, then JY,l 2 miB with equality only if c = 0.

1x1

591

RAGHAVAN AND TRIPATHI: SEQUENTIAL DIAGNOSABILITY IS CO-” COMPLETE

1x1

3) If mi L 2, then 2 m;B + 1 when c = 2. If c = 1, 1 mod 3 then by. (I), . . . 2 2B. However, since 2B and 1 mod 3 only if the single C-vertex is present in Y,, at most one Y , can satisfy = miB when m; = 2 and c = 1. Finally, if c = 0, then by (I), 2lxl 2 4B - 1. Obviously, equality cannot hold here since one side is odd and the other even; moreover, 0 cannot equal 2B since 2B 1 mod 3 but mod 3 when c = 0. To summarize, if m, = 2 then 2 m,B 1 except if c = 1 and then = m,B only if Y , contains the lone C-vertex in Y. 4) If m, = 1, then (I) reduces to

1x1

1x1

1x1

1x1

1x1

1x1

1x1

21x1 2 2B

+c

-

+

2.

(11)

Now if c is 0 or 1, parity and modularity (congruent to 3) of both sides of (11) would again force us to conclude > B. If c = 2, (11) can be written as 2B that but since B 2 mod 3 and can be congruent to 2 mod 3 only if it contains 2 C-vertices in addition to the one D-region that it contains, we can conclude that: If m, = 1 then 2 m,B+1 except if c = 2 and then = m,B only if Y , does contain both the C-vertices in Y. The claim follows. 0 This ends the proof of the CO-NPcompleteness of SEQPMC. Note that the graph constructed in the above proof is very dense. (The number of edges is 0(lVl2).) The whole point of diagnosis with repair is, of course, to reduce the number of tests necessary to attain a certain value of diagnosability. One might justifiably wonder if sequential diagnosability can be estimated more efficiently, i.e., in polynomial time, in the more “practical” case of sparse graphs. We suspect that the problem remains CO-NP complete even when restricted to strongly connected graphs with O(lV1) edges. This is certainly the case for weighted sequential diagnosability, as we demonstrate below. The weighted model, introduced by Maheshwari and Hakimi [15] is a natural generalization of the PMC model. We formalize it as follows. Definition 10: A weighted diagraph < G(V,E ) ,w > is a directed graph G with a weight function w : V +. R+. The weight of a vertex w E V is w(w). The weight function is extended, in the most obvious manner, to subsets X of V , by the definition w(X) = CvEX ~(w). Sequential diagnosability in the weighted model is also a natural extension. Definition 11: A system of n units is (weighted) sequentially t-diagnosable if at least one unit can be identified without replacement provided the set of faulty units present has a weight which does not exceed t. The formalization of this definition can be done as a generalization of the definition of ordinary sequential diagnosability. We skip the details. Note that the CO-NPcompleteness of SEQPMC implies the CO-NP completeness of weighted sequential diagnosability even when all vertex weights are restricted to being just 1. The following theorem proves the CO-NP completeness of weighted sequential diagnosability

1x1

1x1

1x1

1x1

1x1

for sparse graphs, a result not immediately attainable from Theorem 2. NAME: Weighted sequential diagnosability for sparse graphs INSTANCE: Directed graph G(V,E) with 1El I 41V(, w : V +. R+, and t E R+ QUESTION: Is G weighted sequentially t-diagnosable?

Theorem 3: Weighted sequential diagnosability for sparse graphs is CO-NPcomplete. Proof: Clearly, the problem is in CO-NP. If G is not weighted sequentially t-diagnosable, then a syndrome c : E +. {0,1} and at most IVI fault sets are needed to demonstrate the fact. We can verify in polynomial time that: a) Each of the fault sets is consistent for the given syndrome 0. b) Each of the fault sets has a weight no greater than t. To prove that the problem is CO-NPcomplete we reduce SUBSET SUM to its complement. NAME: SUBSET SUM INSTANCE: Finite set A, size s(u) E Z+ for each U E A, a positive integer B . QUESTION: Is there a subset A’ g A such that the sum of the sizes of the elements in A’ is exactly B? (SUBSET SUM was shown to be NP-complete in [ll].)

We transform any arbitrary instance of SUBSET SUM to an instance of weighted sequential diagnosability as follows. If Catqs ( a ) < B , then no SUBSET SUM exists for A. Then specifying any sparse graph with appropriate values of w and t will provide the transformation that G is not sequentially t-diagnosable if and only if there is a SUBSET SUM for A. (For example, the weighted digraph defined by V = {w1,w2,w3}, w(wl) = w(’u2) = w(w3) = t = 1, and edges E = ((211, w2), (w2,03), (213, V I ) } will work.) Otherwise, let a) V = A U {w1,02}, and b) E = {(U, w) : U # w & at least one of U, w is w1 or 212) c) The weight function 20 : V +. Z+ is specified by i. Vu E A, w(a) = s ( a ) ii. w(w1) = CaEA .(U) - B iii. w(w2) = B

+ 1.

+ 1 = w(A) - B + 1 +

Finally, let t = w(A) + 1. Note that /El = 4(lVl - 2 ) 2 < 41VI. In fact, the graph is planar, as the embedding in the figure shows. Clearly this is a polynomial transformation. We claim that there is a SUBSET SUM for A if and only if G is not weighted sequentially t-diagnosable. a:Suppose there exists a subset A‘ A such that CaEA, s(u) = B. Then let F1 = A’ U (01) and F 2 = ( A - A’) U ( ~ 2 ) = V - F1. Let c : E +. {0,1} be defined by c(u,w)= 1 H

(U

E Fl & w E F2)

or

(w E

F1

&

U

E

8’2).

IEEE TRANSACTIONS ON COMPUTERS, VOL. 40, NO. 5 , MAY 1991

592

v2

Fig. 5. Weighted digraph constructed from SUBSET SUM.

Clearly, F l , Fz are consistent fault sets for this syndrome and F1 n F2 = 0. Moreover,

=

s(a)

+ 1 = t.

IV. CO-NP COMPLETENESS OF SEQUENTIAL IN THE BGM MODEL DIAGNOSABILITY

aEA

We will show that sequential diagnosability in the BGM model is CO-NP complete even for planar graphs G ( V , E ) for which IEl < 31VI. In the remainder of this section we use the term “sequential diagnosability” to mean “sequential diagnosability in the BGM model.” The problem can be stated as follows.

Also,

+ aEA’ s ( a ) + 1 = t.

w(F2) =

S(U)

S(U)

(aCA

=

)+

B

+1

aEA

Therefore, G is not weighted sequentially t-diagnosable. e:Suppose G is not sequentially t-diagnosable. Let (T be a syndrome which demonstrates it, and F1, F z , . . . ,F, be the least number of fault sets in Fo, whose intersection is empty. Then, as in Theorem 2, a) The strong connectivity of G implies that every vertex belongs to at least one fault set among F1, F z , . . . , F,. b) Since v1 and v2 have edges directed to every other vertex in the graph, both v1 and vz must belong to T - 1 fault sets. (a) 2 = t 1 > t. Therec) w(v1) w(v2) = C a EsA fore, v1 and 212 cannot belong to the same fault sets. Observations b) and c) together imply that T = 2. Therefore, F1 n FZ = 0, and a) implies that Fl U F2 = V . Without loss of generality, let v1 E F1 and IJZ E F2. Then we have

+

+

+

w(F1 - { V l } ) 5 t - w(v1) =

w(F2 - ( 2 1 2 ) ) 5 t - ~

( ~ 1= 2 )

aEA

But we also have

So neither (IV) nor (V) can be a strict inequality, and A’ = 0 F1 - { V I } is the required subset.

S(U) - B .

(V)

NAME: Sequential diagnosability for sparse planar graphs (SEQBGM) INSTANCE: Directed planar graph G(V,E ) , t E Z+ in which \El < 3(VI. QUESTION: Is G sequentially t-diagnosable?

Theorem 4: Sequential diagnosability for sparse planar graphs is CO-NPcomplete. Proof: Membership in CO-NPfollows (as in the earlier proofs on sequential diagnosability) merely from the fact that if G is not sequentially t-diagnosable, then a syndrome (T : E --+ (0, l}, and at most IVI fault sets consistent for (T and with cardinality 5 t are necessary to verify it. We use the following decision problem, shown to be NRcomplete in [8], to prove that SEQBGM is CO-NPcomplete. NAME: Planar degree constrained vertex cover INSTANCE: Undirected graph G(V ,E ) which is planar and connected, and in which the degree of every vertex U E V is no greater than 3, and a number k, 1 5 k 5 IVI. QUESTION: Does there exist a vertex cover of size k or 5 k such that less for G, i.e., a subset X C V with for each undirected edge { u , v } E E at least one of U and U belongs to X?

1x1

Given any arbitrary instance of the above, we build an instance of SEQBGM as follows.

593

RAGHAVAN AND TRIPATHI: SEQUENTIAL DIAGNOSABILITY IS CO-IW COMPLETE

Fig. 6. SEOBGM instance constructed from planar vertex cover.

Let t = k specified by

+ 4,

and the directed graph G’(V‘, E‘) be

F,, = ( X - { U } ) U ( N ( v )n (V - X ) )U {v4, v5}. Then, since IN(v) n (w - X ) l is at most 3, it follows that IF,( 5 k - 1 3 2 = t and there is still no edge (w, y) E E’ such that neither w nor y is in F,. +: Suppose G’( V’, E’) is not sequentially t-diagnosable. Then for some syndrome o : E’ + {0,1} there exist fault sets F, for each v E V’ such that v # F, and F, E F,,t. We claim that for all the directed edges e E E’, a ( e ) must be 1. To prove this, suppose, to the contrary, that for some directed edge ( U , v) E E’, a(u,w) = 0. By the definition of a syndrome in the BGM model v must then be fault-free. Since the graph is strongly connected, and since o occurs in a t-fault situation we can then find at least one path v + q + 02 -+ ..- + vk, where O ( W , W I ) = o ( v 1 , v ~ )= ... = u(wk-2,~k-l) = 0 and a(vk-1,vk) = 1. But then w k must definitely be faulty and therefore belong to every consistent fault set of a,violating the assumption that nFEF,,*F = 0. Now consider any fault set F in F,,,t to which v5 does not belong. It is easy to see that {v1,v2,v3, v4} g F. Let X = F - {q,v2,v3,w4}. Then 5 t - 4 = k. Finally, note that X must be a vertex cover of G(V, E ) since if there exists an undirected edge {y, w} E E such that neither y nor w belongs to X,then F cannot be a consistent fault set for 0.0

+ +

V t = V U { v 1 , ~ 2 , . . . , v 5 } , E ’ = ElUEzUE3 where

’

El ={(vI,v5), (vZ,v5), (v37v5), (v47v5)) U {(v5,vl), (v5,v2), (O57 O3), (U57 v4)}7 EE ( u , v ) E E2 8~ ( v , u ) E E2

*

{U,V}

and for some arbitrary but fixed vertex 2 E V,E3 = ((214, 21, (5,214)). Obviously, this is a polynomial transformation and G’(V’, E’) is planar and strongly connected. Also, IE’I = 21E( 10 5 31VI +10 < 3lV’l. We now show that there exists a vertex cover of size 5 k for G if and only if G’(V’, E’) is not sequentially t-diagnosable. +: Suppose there is a vertex cover X V such that 5 k. Let a : E’ + {0,1} be specified simply by

+

1x1

V e E E’

1x1

a ( e ) = 1.

For each vertex v E V’, we exhibit a fault set F, such that F, E F,,, t & F, and conclude therefore that G‘(V’, E’) is not sequentially t-diagnosable. a) If v E V’ - (X U {v4,v5}), the fault set F, = X U (214, v5} works, since v is not in F, and IF,I 5 k 2 < t and there is no edge (w, y) E E‘ such that neither w nor y is in F,. (This last condition follows from the fact that X is a vertex cover of G.) b) If v = v4, let F, = (215,~)UX. Then (F,I 5 k 2 < t , v f! F, and there is no edge (w, y) E E’ such that neither w nor y is in F,. c) If v = v5, then let F, = X U {v1,v2,v3,v4}. Now IF,I 5 k 4 < t , v f! F, and there is no edge (w, y) E E’ such that neither w nor y is in F,. d) If v E X, let N ( v ) be the neighboring set of vertices of v in G, i.e., the set {w : w E V & {v, w} E E}. Let

+

+

+

V. CONCLUSIONS We have shown that the sequential diagnosability problem is CO-NPcomplete in both PMC and BGM models. Several problems related to sequential diagnosis still remain unresolved. This paper leaves open the possibility of polynomial time algorithms to determine the sequential diagnosability number in the PMC model for sparse graphs. It is easy to extend the co-NP completeness proof for the BGM model to the comparison model of Malek [l]. However, the sequential diagnosability problem is open in Chwa and Hakimi’s comparison model [3]. Also open, since the time it was formulated 20 years ago, is the synthesis problem, i.e.,

594

IEEE TRANSACTIONS ON COMPUTERS, VOL. 40, NO. 5, MAY 1991

to design, given a system of n units and a positive integer t such that n 2 2t 1, an interconnection of the n units using the minimum number of edges that will guarantee that the system is sequentially t-diagnosable. For published work on this subject see [4], [15], and [13].

+

Theorem 1 : 3-Partition with Restrictions is NP-complete in the strong sense. Proof: Membership in NP follows from the fact that a 3-partition, if one exists, provides an easily verifiable certificate. To show that 3-Partition with Restrictions is NP-complete in the strong sense, we reduce NUMERICAL THREEDIMENSIONAL MATCHING to it. NAME: NUMERICAL THREE-DIMENSIONAL MATCHING INSTANCE: Disjoint sets W, X , and Y, each containing m elements, a size s ( a ) E Ztfor each element a E WUXUY, and a bound B E Z+. QUESTION: Can W U X UY be partitioned into m disjoint sets AI, A2, A3, . . . , A, such that each A, contains exactly one element from each of W, X , and Y, and such that, for 1 5 i 5 mCaEA, s ( a ) = B?

(That NUMERICAL THREE-DIMENSIONAL MATCHING is NP-complete in the strong sense was proved in [lo].) Let (W, X , Y ,B , s), as indicated above, define an arbitrary instance of NUMERICAL THREE-DIMENSIONAL MATCHING. Consider the following two specifications of 3-Partition with Restrictions: a) B’ = 14;

xaEW +

$’(a) =

{

B’ = 32:

s’(a1) = 15;

s’(a2) =

s’(a3) = s’(aq) = s’(ug) = S ’ ( U 6 ) = 9 s ’ ( u ~= ) 10; s ’ ( u ~= ) 12; s ’ ( u ~ = ) 14.

+ +

5

<

+

+

~ ’ ( a=) 36B2+ 12 a€.%

+ +5

~ ’ ( a+) 1 2 aEA,

= 36B2

b)

+ +

1 2 ( B 2 s ( a ) ) 1 if a E W 1 2 ( B 2 s ( a ) ) 2 if a E X 12(B2 + s ( u ) ) + 5 if a E Y.

It can be verified that all element sizes in A satisfy < ~ ’ ( a B - 2 or if CaEIv s ( a ) CaEX s ( a ) CaEY .(a) # mB. We therefore prove it for the only remaining case. +: Suppose there exists a three-dimensional matching AI, A2, A3,. . . , A,, with each of the At’s containing exactly one element from each of W , X , and Y, and such that for 1 5 i 5 mCaEA, .(a) = B. Then our 3-partition consists of precisely the same sets. This is a valid 3-partition since if A, = {w,, z,, y,} is any set of A l , A 2 , A Y 3 . . . , A m then ,

s’(a1) = s’(a2) = s’(a3) = 4

s’(a4) = s’(ag) = s’(afj)= s’(u7) = s’(ag) = s’(ag) = 5

m’ = 3;

+

+

APPENDIX

m’ = 3;

If m 2 4 and there exists at least one element of W U X UY whose size s ( a ) > B - 2 or if s ( a ) CaEX s(a) CaEY s ( a ) # mB, then there cannot be a matching and we let the 3-partition instance be b). Otherwise, we create an instance of 3-partition with restrictions as follows: A = W U X U Y , B’ = 36B2+ 12B 8 and the size function s‘ is defined by

+ 12B + 8 = B’.

e: Now suppose that there exists a 3-partition of A, A 1 , A 2 , A 3 , . . . , A m. Since V a E A 5 < s’(a) < there must be exactly three elements in each A, 1 5 z 5 m. Also, since B’ 8 mod 12, the only way to get three elements of A, to add up to 8 mod 12 is to pick one element from each of W,

g,

E,, 4, .‘(a) - 36B2- 8 The first specification has a 3-partition and the second one s(a) = 12 does not (because 15 cannot be matched to any other pair). X , and Y. But then B . Therefore Al. A2, As, . . . . A,, is also a numerical threeThe restrictions on the values of the element sizes and the 0 dimensional matching. bound B’ required in the problem statement are met in both cases. We use these two specifications to map “easy” instances ACKNOWLEDGMENT Of NUMERICAL THREE-DIMENSIONAL MATCHING to one or the other in such a way that our claim that there is We thank Dr. Ghanta for going through the many versions a 3-partition in the target instance if and only if there is a of the proofs patiently and offering several suggestions for numerical matching in the input instance will be met. improvement. We also thank D. Crick and referees A and Let W = {w~,w~,w~,...,w,}, X = ( x 1 , x 2 , x 3 , ~ . ~D, for their detailed criticism, which improved the quality of presentation significantly. z}, and Y = { v l , v 2 . ~ 3 , ... Y ,}. If m 5 3 in the NUMERICAL THREE-DIMENSIONAL MATCHING instance, then we need to check only a constant REFERENCES number of all the possible three-dimensional matchings to see [ l ] M. Malek, “A comparison connection assignment for diagnosis of if one satisfies the numerical requirement. If one does, let the multiprocessor systems,” in Proc. 7th Symp. Comput. Architecture, May 3-partiton instance be a), otherwise let it be b). 1980, pp. 31-35. !

RAGHAVAN AND TRIPATHI: SEQUENTIAL DIAGNOSABILITY IS CO-”

COMPLETE

F. Barsi, F. Grandoni, and P. Maestrini, “A theory of diagnosability of digital systems,” IEEE Trans. Comput., vol. C-25, pp. 585-593, June 1976. K.-Y. Chwa and S. L. Hakimi, “Schemes for fault-tolerantcomputing: a comparison of modularly redundant and ?-diagnosable systems,”Inform. Contr., vol. 49, pp. 212-238, 1981. P. Ciompi and L. Simoncini, “The boundary graphs: An approach to the diagnosability with repair of digital systems,” in Proc. Third Texas Con) Compu?. Sys?., Nov. 1974, pp. 931-939. -, “Analysis and optimal design of self-diagnosable systems with repair,” IEEE Trans. Compu?., vol. C-28, pp. 362-365, May 1979. A. T. Dahbura, “System-level diagnosis: A perspective for the third decade,” in Proc. Princeton Workshopon Algorithms, Architectures, and Technological Issues for Models of Concurrent Computation, 1987. H. Fujiwara and K. Kinoshita, “On the computational complexity of system diagnosis,” IEEE Trans. Compu?., vol. C-27, pp. 881-885, Oct. 1978. M. R. Garey and D. S . Johnson, “The rectilinear Steiner tree problem is NP-complete,” S W J. Appl. Math., pp. 826-834, 1977. -, “Strong NP-completeness results: Motivation, examples, and implications,” J. ACM, pp. 499-508, 1978. -, Computers andlntracrability ACM, San Francisco, C A Freeman, 1979. R. M. Karp, “Reductabilityamong combinatorialproblems,” Complexity of Computer Computations. New York: Plenum, 1972, pp. 85-103. C. R. Kime, C. S. Holt, J.A. McPherson, and J. E. Smith, “Fault diagnosis of distributed systems,” Compsac, pp. 355-364, 1980. T. Kohda, “On sequentially diagnosable systems containing at most r faulty units,” Syst., Comput., Controls, vol. 9, pp. 38-44, 1978. P. Maestrini, “Complexity aspects of system diagnosis,” in Proc. 17rh Annu. Allerton Con) Commun., Contr., Compu?., Allerton House, Monticello, IL, Oct. 1979, pp. 329-338. S. N. Maheshwari and S. L. Hakimi, “Onmodels for diagnosablesystems and probabilistic fault diagnosis,” IEEE Trans. Compu?., vol. C-25, pp. 228-236, Mar. 1976. U. Manber, “System diagnosis with repair,” IEEE Trans. Comput., vol. C-29, pp. 934-937, Oct. 1980. J. Narasimhan and K. Nakajima, “An algorithm for determiningthe fault diagnosability of a system,” IEEE Trans. Comput., vol. C-35, no. 11, pp. 1004-1008, NOV.1986. D. K. Pradhan, Fault Tolerant Computing: Theory and Techniques. Englewood Cliffs, NJ: Prentice-Hall, 1986. F. P. Preparata, G. Metze, and R. T. Chien, “On the connection assignment problem of diagnosable systems,” IEEE Trans.Electron. Comput., vol. EC-16, pp. 848-854, Dec. 1967. -, “Some results on sequentially diagnosable systems,” in Proc. Hawaii In?. Con) Syst., 1968, pp. 623-626. V. Raghavan and A. Tripathi, “Improved diagnosability algorithms,” IEEE Trans. Comput., vol. 40, pp. 143-153, Feb. 1991. V. Raghavan, S. Dong, and A. Tripathi, “A characterizationof sequentialand t/s-diagnosable systems,: Univ. of Minnesota Tech. Rep. TR 86-49, Oct. 1986.

595

[23] J. D. Russell and C. R. W e , “System fault diagnosis: Closure and diagnosability with repair,” IEEE Trans. Comput., vol. C-24, pp. 1078- 1089, Nov. 1975. 1241 A. Somani, D. Avis, and V. Aganval, “On the complexity of single fault set diagnosability and diagnosis problems,” IEEE Trans. Comput., pp. 195-201, Feb. 1989. [25] J. Stephens and V. Raghavan, “On single fault diagnosability in the PMC model,” IEEE Trans. Comput., submitted for publication. [26] G. F. Sullivan, “A polynomial time algorithm for fault diagnosability,” in Proc. 25th Annu. Symp. Foundations Comput. Sci., IEEE Computer Society, Oct. 1984, pp. 148-156.

Vuay Raghavan (SY88-M’89),received the B.Tech degree in electrical engineering from the Indian Institute of Technology, New Delhi, and the M.S. and Ph.D. degrees in computer science from the University of Minnesota, Minneapolis. Presently he is an Assistant Professor of Computer Science at Vanderbilt University, Nashville, TN. His research interests include fault-tolerant systems, distributed computing, graph theory, and algorithms. Dr. Raghavan is a member of the IEEE Computer Society and the Association for Computing Machinery.

h a n d ’hipathi (S’76-M’81), received the B.Tech degree in electrical engineering from the Indian Institute of Technology, Bombay, in 1972, the M.S. and Ph.D. degrees in electrical engineering from the University of Texas at Austin in 1978 and 1980, respectively. From 1972 to 1975 he worked as a Research Scientist at Bhabha Atomic Research a n t e r , Bombay, India. From 1981 to 1984 he was a Senior Principal Research Scientist At Honeywell Computer Sciences Center, Bloomington, MN. Presently he is an Associate Professor of Computer Science at theuniversity of Minnesota. His research interests include distributed computing, fault-tolerant systems, parallel processing, and object-oriented programming. Dr. Tripathi is a member of the IEEE Computer Society and the Association for Computing Machinery.