Tag Archives: Minimum Test Set

Fault Detection With Test Points

Leave a reply

This is it! The end of the appendix!

The problem: Fault Detection with Test Points.  This is problem MS19 in the appendix.

The description: Given a directed acyclic graph G=(V,A) with one “source” vertex s with indegree 0, and one “destination” vertex t with outdegree 0, and an integer K, can we find a subset A’ of A of size K or less that induces a “test set” T:

T = \Bigl( \{s\} \cup \{u_1:(u_1,u_2) \in A'\}\Bigr) \times \Bigl( \{t\} \cup \{u_2:(u_1,u_2) \in A'\}\Bigr)

Where T has the property that for all pairs of vertices v, w \in V-{s,t}, there is some pair (u_1,u_2) \in T such that v is on a path from u_1 to u_2, but there is no path from u_1 to u_2 containing w.

What that description means:  Can I mark K or less edges so that we can use marked edges to “test” all pairs of vertices?  We “test” a pair of vertices by sending an electric signal along a path between those edges.  If a test fails (or passes), we know that something along that path has failed (or passed).  We want to be able to distinguish 2 vertices v and w by seeing if there is a test that includes v but not w (or vice versa) so that if that test fails, we can tell whether the problem is v or w, and eliminate the other possibility.

Example: It’s a little weird to create an example, because you are marking edges, and you need a path between vertices that touch marked edges.  But that path is allowed to be a single edge.  Suppose we have:

Suppose we put test points on all edges going from s, and all edges entering t.  Then we can distinguish points using these edges.  For example:

  • 1 and 2 are distinguished using the s->1 edge as a path.  (The path from s->1 includes 1 but not 2)
  • 1 and 5 are distinguished using the s->2->5->t path (the s->2 and 5->t edges).
  • 3 and 6 are distinguished using the s->3 edge as a path.

Reduction: I think this is P1 from the paper by Ibaraki, Kameda, and Toida.  They reduce from Minimum Test Set, (called “Set Distinguishibility” in the paper which is very close to what we need.

So we are given a set S of elements, and a collection C of subsets of elements.  We then build a graph.  Here it is from the paper:

A and B hold one vertex for each set in C.  C has one vertex for each element in S. The big dark arrows mean that all possible connections between those sets exist.  The big white arrow means that there is an edge from ai to cj if element j is in set i.

We will need a way to distinguish all C vertices, and can do that by placing test points on some of the edges between VI and the A vertices.  (We will be placing them on the edges that connect to vertices that will be the sets that solve the Minimum Test Set problem).

We also need to distinguish the elements of B from each other.  We’ll need new test points for that, and we can place them on the edges between the A and B vertices.

The little arrows in the picture show which edges we are putting in the test set, going into and coming out of the vertices.

Difficulty: 8  Like the last problem, I’m not sure if this is the right problem.  I also wonder why we need the B vertices at all- they don’t seem necessary for us to connect the C vertices and solve the Test Set problem.    Maybe I’m missing something?

Fault Detection in Directed Graphs

Leave a reply

Let’s see if I can finish out these last few problems.

The problem: Fault Detection in Directed Graphs. This is problem MS18 in the appendix

The description: Given a directed, acyclic graph G=(V,A).  We denote the set I as the set of vertices with indegree 0, and the set O as the set of vertices of outdegree 0.  Given an integer K, can we find a set of K or less paths starting at a vertex in I, and ending at a vertex in O, where every vertex in V is on at least one of those paths?

Example: It took me a long time to wrap my head around this, and I’m still not 100% convinced the version in the paper is this problem.  But here is an example that I think is helpful:

Notice that each of the middle vertices is on a separate path from an I vertex to an O vertex.  So, we will need all 9 combinations (from every I vertex to every O vertex) to ensure that all middle vertices are covered.

But now, suppose we add one more edge from 9 to O2:

Now we don’t need a separate start and end from I3 to O3, since there is a path  from I3 to 02, choosing that pair as a start/end combination will give us paths that cover both vertex 8 and vertex 9.

Reduction: The paper by Ibaraki, Kameda, and Toida write the problem a bit differently, and they have a lot of different problems in their paper, and to be honest, I’m not sure which one is for this problem.  (I think it’s P3?  But their reduction seems to have extra stuff that we don’t need).

So, I’m going to try to do the reduction myself from X3C, like G&J suggest in the appendix, but take inspiration for how the structure is built from the paper.

To do this, I really want a version of this problem where we only care about paths through internal nodes (vertices not in I or O).  So, it’s possible that a vertex in I or O is not in a path, but every vertex not in I or O is in some path.  We can reduce this to the real version by creating extra “dummy” vertices that are internal:  For each vertex ij ∈ I, create a vertex aj, and an edge ij → aj, and replace all other edges exiting ij with corresponding edges leaving aj instead.  We can do the same thing with O by placing vertices “before” the O vertices.  That way the only way to have a path through those new internal vertices is to have a path through all I and O vertices as well.

For our real reduction, we start with an X3C instance- a set of elements X (|X| = 3q, for some positive q), and a collection C of 3-element subsets of X.  Both our I set and our O set will have one vertex for each element of C (so 2 copies of all elements total).  In between, we will create a set of vertices X, one vertex for each element of X.  We will have edges from each I vertex (a subset)  to the 3 X (element) vertices it is a part of, and from each X vertex to the O vertices it is a part of.  Set K’ = K.

If we have an X3C instance, then choosing the sets in the solution as the I and O elements, and making them pairs, will give us a cover of all of the X elements in the middle.

If we have a cover of size K, then if we have the same sets in both the I and the O sets (so both “sides” agree on what sets to use), we clearly have an X3C solution.  It’s possible, though, that there is some pair (Ia, Ob) where a != b.  However, we know that:

  • Each element in X is along some path from an I vertex to an O vertex
  • We need K pairs of elements to make the cover, and we have 3K elements to cover.overall, and so each element in X is a member of exactly one path from an I vertex to an O vertex.
  • So, each element in X occurs in exactly one I vertex in some pair in the solution.  (And, each I vertex occurs at most once in some pair)
  • Thus, just taking all of the sets corresponding to the I vertices gives us an X3C solution
  • (And, relatedly, we can shift the O vertices to be the corresponding sets to the I vertices and remain a cover of the internal vertices).

Difficulty: 7.  I’m still not entirely sure I am talking about the right problem from the paper.  It also took me a lot of time to come up with the reduction, because X3C wants us to choose some, but not all, of the sets in the collection, but the whole point of this problem is that we can leave things out.  I played with an idea where all of the vertices connected to each other 3 times, but couldn’t make it work.  Hopefully this version makes more sense.