Keywords: Electrical networks, Spectral graph theory, Information theory, Fault detection, Combinatorial optimization

1 Introduction↩︎

Diagnosing faults in electrical circuits and wiring is an important problem with applications in power systems, very large scale integration (VLSI), chip design, circuit board systems, to name a few. The literature is vast; the reader is referred to the survey [1], a sample of more recent work [2], [3] and the references therein. There are a variety of approaches that are adopted in practice and new methods are regularly being invented even to the present. In this paper, we consider a particular formalization of this problem which, to the best of our knowledge, has not been studied rigorously in prior work. Nevertheless, we believe the model we study is natural, of practical relevance, and worth studying from a mathematical perspective. It is related to and inspired by work in detecting faults and structures in continuous conducting media; see the textbooks [4], [5] and [6] for a more recent survey. Our problem can be seen as a discrete analogue of this problem from the literature on continuous media and related inverse problems. The resulting optimization problem is rich in its scope, spanning topics from combinatorial and spectral graph theory, integer and combinatorial optimization, information theory, and electrical network theory. Let us formally introduce the problem.

The problem we wish to study is to detect whether all the resistance connections in the network are working as expected, or whether one of them has been damaged. To do this, we are allowed to probe the network by making current value measurements (or equivalently, effective resistance values) across pairs of terminals (vertices) and use these values to determine if any edge is faulty and if so, which one.

One could allow for the possibility that no edge has been altered. Then, one has to detect if any edge has been altered and if so, identify which one. We give a short argument below that the number of measurements in this version of the problem is at most one more than the version in Definition 2 where a single, unknown edge has been altered. Consequently, we will focus on the version in Definition 2 for the remainder of the paper.

Let \(\mathcal{A} \in \mathbb{R^{|T|\times|E|}}\) be the matrix where each row corresponds to a measurement \(t \in T\) and each column corresponds to an edge \(e \in E\) that has been altered. Each entry in \(\mathcal{A}\) contains the effective resistance value for a given pair of source and sink terminals and a given altered edge. Consider the submatrix \(\mathcal{A}_S \in \mathbb{R^{|S|\times|E|}}\) of values corresponding to measurements \(S \subseteq T\) and all edges \(E\). If all columns in \(\mathcal{A}_S\) are different from one another, then the provided measurements \(S\) satisfy the version of our problem given in Definition 2. On the other hand, if there are at least two columns that are the same, then the set \(S\) of measurements will not distinguish between these two edges. Hence, an equivalent formulation of the problem is to find the smallest set \(S\subseteq T\) of measurements such that \(\mathcal{A}_S\) has distinct columns.

Suppose now we include a new column \(c\) in \(\overline{\mathcal{A}} = [\mathcal{A}|c]\) which contains the effective resistance values when no edge in \(G\) has been altered. Consider any set \(S\) of measurements such that \(\mathcal{A}_S\) has distinct columns (i.e., \(S\) is a set of measurements that can identify a faulty edge assuming one exists). If all columns of the updated submatrix \(\overline{\mathcal{A}}_S\) are different from one another, then the measurements \(S\) solve the problem including the possibility that no edge has been altered. Otherwise, there is one column in \(\overline{\mathcal{A}}_S\) that is the same as column \(c\) restricted to \(\overline{\mathcal{A}}_S\) (there can be at most one such column since \(\mathcal{A}_S\) has distinct columns). Let \(e^*\in E\) be the edge corresponding to this column. If there is no measurement in \(T\) such that the column corresponding to \(e^*\) has a different entry compared to column \(c\) in \(\overline{\mathcal{A}}\), then the problem cannot be solved using measurements in \(T\). In other words, no measurement is able to distinguish between the possibility that \(e^*\) has been altered and the possibility that no edge has been altered. Thus, we may assume there exists a measurement \(s^* \in T\) such that the corresponding entry of column of \(c\) will be different from that associated with \(e^*\). As a result, \(S^* = S \cup \{s^*\}\) is a set of measurements that will solve the problem with the additional possibility that no edge has been altered. Since \(|S^*| = |S| + 1\), at most one additional measurement is required if the possibility of no edge being altered is included in the problem.

We also note that in Definition 2, the measurements \(S\subseteq T\) are made non-adaptively, i.e., the result of a measurement is not used to decide what the next measurement is. One must decide on the set \(S\) of measurements up front and then the observed measurement values must be used to identify the faulty edge. Our results below apply to this non-adaptive setting. The analysis of adaptive measurement strategies is left for future work.

1.1 Our contributions↩︎

We provide tight upper and lower bounds on the smallest number of measurements for the fault detection problem in various families of electrical networks. In particular, we are able to fully resolve the problem for complete graphs and complete \(k\)-partite graphs for \(k\geq 2\). The formal statements are in Section 2 and their proofs are provided in Section 3. The proof techniques draw upon combinatorial and spectral graph theory, electrical network theory, and ideas from information theory. We note briefly that each effective resistance measurement provides a real number; thus, a single measurement potentially provides infinitely many bits of information. For this reason, classical information theoretic lower bound arguments based on bits of information do not immediately apply. While our final results are mathematically precise and rigorous, our search for the best measurement strategy in each of these cases involved modeling the problem as a set covering/integer programming problem and using computational experiments to guide us towards the optimal strategy for measurements. Thus, the problem involves a nice interplay between rigorous mathematical analysis and computer-aided search using discrete optimization techniques. More broadly, we believe that the fault detection problem we set up in Definition 2 is a new, challenging combinatorial optimization problem that is rich in its mathematical structure and is motivated by a fundamental problem in fault diagnosis in electrical networks, which has diverse applications. We close the paper in Section 4 with some future directions, including some concrete open questions, that we hope can spawn new and interesting research avenues for the discrete mathematics and optimization community.

1.2 Related literature↩︎

As mentioned before, the formalization of fault detection given in Definition 2 does not seem to have received a great deal of attention in terms of obtaining provable bounds on the smallest number of measurements. Nevertheless, there are several very related strands of work on fault detection in electrical networks that we review next, which place our work in the broader context of fault diagnosis in electrical systems.

The closest line of work is the investigation in [7], which is motivated by a fault detection problem in VLSI systems. In this paper, the authors consider the problem of testing whether all edges in a tree network are working properly; thus, the problem is called the tree testing problem. In the language of Definition 2, the graph \(G\) is a tree, all edge weights are \(1\), and the goal is to simply detect if any edge has been altered or not, without necessarily pinpointing which one if a fault is indeed detected. A very closely related line of work originates in the literature on inverse problems, especially in the so-called Calderón problem. The discrete version of the Calderón problem is to recover the values of all resistors in a resistive network given a possible set of measurements that one can make. While there is no adversary altering the resistances as in Definition 2, obviously if one can determine all the resistance values, then one can simply check if any one of them differs from the original value. Thus, the discrete Calderón problem requires one to deduce much more information from the measurements, compared to the faulty edge detection problem in Definition 2 (and therefore may require a much larger number of measurements). A good introduction to the discrete Calderón problem is the book [8], which also surveys relevant prior work.  [9] is a recent paper that surveys work in the past couple of decades and provides some new mathematical foundations for the problem. The original Calderón problem is defined for a continuous conducting medium as opposed to a discrete electrical network modeled by a graph. One is allowed to make current and voltage measurements on the boundary of a connected domain \(\Omega \subseteq \mathbb{R}^d\) and from this one has to infer the electrical properties in the interior of \(\Omega\). The problem forms the mathematical foundation for Electrical Impedance Tomography (EIT) [4], [6], [10], which has numerous applications ranging from computational medicine, geophysics, to testing for structural defects in solids. Much of the literature uses the terms EIT and Calderón problem interchangeably. The tools and techniques are quite different from the discrete setting (and especially the techniques we use in this paper), drawing upon methods from PDEs and classical inverse problems. A continuous version of the problem we study in this paper (Definition 2) has been studied, arising out of the work on the continuous Calderón problem. Here, one considers a fracture or a crack in the conducting medium, modeled by a curve that is perfectly insulating. The goal is to, again, use boundary measurements to determine the location/shape of the curve. The problem was introduced in a seminal paper by Friedman and Vogelius [11], with several follow up works; see [12]–[16] for a sample and the textbook [5] for more details.

In [17], [18], the authors consider the problem of detecting faults in wiring networks. They build on prior work which can be traced back to a seminal paper by Kautz [19]. Here, the vertices of a graph model different logical units (often called nets) in a circuit board and each edge denotes a possible site of a “fault”. One is allowed to probe the logical units and use the responses to detect these faults, if any. The mathematical formalization is the following: given a (simple) graph \(G = (V,E)\), one can query a subset \(U \subseteq V\) and the response is a subset \(Q(U)\) which is the set of all vertices that can be reached by a path from a vertex in \(U\). The goal is to find the smallest set of queries to identify all the connected components of \(G\) (the vertices in the connected components of size two or more correspond to the logical units that are connected by faulty edges). A group testing [20] approach to this problem was considered in [21] and is discussed in the papers [17], [18] cited above, along with other relevant work on this problem.

2 Statement of results↩︎

We consider the fault detection problem in Definition 2 where all the unaltered weights are \(1\), i.e., the network is made of unit resistance (conductance) edges; we use \(\mathbf{1}\) to denote the vector of all ones. Moreover, we allow all possible measurements, i.e., \(T = V \times V\) (see Definition 2). We present upper and lower bounds when the electrical network’s underlying graph is a complete graph or a complete \(k\)-partite graph.

2.0.0.1 Complete graphs

The following theorem gives the number of measurements
needed for complete graphs (i.e., graphs that have an edge between every pair of vertices).

2.0.0.2 Complete \(k\)-partite graphs

A complete \(k\)-partite graph is one where the set of vertices can be partitioned into \(k\) independent sets and there is an edge between every pair of vertices in different partitions. We first state exact bounds for the bipartite (\(k=2\)) and tripartite (\(k=3\)) cases, and then state a generalization for arbitrary \(k \geq 2\).

We now state our result for \(k\)-partite graphs for arbitrary \(k\geq 2\).

3 Proofs of results↩︎

In this section, we give complete proofs of Theorems 1,  2,  3, and  4. First, we provide the proofs for the complete graphs, complete bipartite graphs, and complete tripartite graphs, which illustrate the general proof techniques for establishing upper and lower bounds on the smallest number of measurements needed for the faulty edge detection problem. The most technically involved proof is Theorem 4 that analyzes \(k\)-partite graphs for arbitrary \(k\geq 2\). Its proof is a much more intricate implementation of the general proof ideas illustrated in this section for the complete graph, complete bipartite, and complete tripartite cases. The high level idea in the proofs for the upper and lower bounds is to precisely quantify the amount of information one gains with any given measurement. Given any proposed measurement in an electrical network, two edges can be considered information theoretically equivalent if the effective resistance values are the same when they are altered. In other words, this measurement will not be able to distinguish two equivalent edges. Therefore, one seeks to find the smallest set of measurements such that for every pair of edges, there exists a measurement that puts them in different equivalence classes. Consequently, it becomes important to understand the equivalence classes of the edges of the graph for any measurement. This is done for complete graphs in Appendix 6 and for complete \(k\)-partite graphs in Appendix 7.

A conceptual tool that we use for our lower bound proofs is the idea of a measurement graph.

Note that the edges in the measurement graph \(G' = (V, \mathcal{M})\) are not necessarily edges in the underlying graph \(G = (V,E)\) for the electrical network.

Many of our measurement strategies are based on the following type of measurement.

We now describe four types of butterfly wing measurements used in the strategies for \(k\)-partite graphs.

3.1 Complete Graphs↩︎

The characterization of the edge equivalence classes for any measurement given in Lemma 1 from Appendix 6 will be an important tool below. In particular, the altered resistance values in Table 3 will be referred to many times.

3.1.1 Upper Bound in Theorem 1↩︎

Let the vertices of the complete graph be labeled as \(v_1, \ldots, v_n\). We first prove that \(\left\lceil \frac{2n}{3}\right\rceil\) measurements suffice and then establish a matching lower bound.

3.1.1.1 Strategy

Partition the vertices into groups of three: \(v_1, v_2, v_3\) and \(v_4, v_5, v_6\) and so forth, and depending on the value of \(n\), we will have zero, one or two vertices left over that cannot be grouped. We use butterfly wing measurements (Definition 5) on all the groups of size three (with \(v_2, v_5, v_8, \ldots\) as the center nodes). If we have one or two vertices left over that were not grouped, then we add measurements with source equal to \(v_2\) (the center node in the first group of three) and sink equal to the left over vertices. We claim that these measurements suffice.

3.1.1.2 Measurement Counts

The number of measurements is \(\frac{2n}{3}\) if \(n \equiv 0 \mod{3}\), \(\frac{2(n-1)}{3} + 1 = \frac{2n}{3} + \frac{1}{3}\) if \(n \equiv 1 \mod{3}\), or \(\frac{2(n-2)}{3} + 2 = \frac{2n}{3} + \frac{2}{3}\) if \(n \equiv 2 \mod{3}\). We observe that these numbers are equal to \(\left\lceil \frac{2n}{3} \right\rceil\) (in the respective cases).

3.1.1.3 Correctness

Consider two edges \(e, e' \in E\). We have to show there exists a measurement which gives different effective resistance values when these two edges are altered. First, observe that at least one of the edges, say \(e\) without loss of generality, must have an endpoint in some group of size three. This is because we have at most two vertices in the graph that are not included in some group of size three. We now do some case analysis.

Case 1: \(e\) has both endpoints in the same group of size three.

If \(e'\) does not have an endpoint in this group of size three, then any measurement in the butterfly wing will distinguish these two edges by Lemma 1. If \(e'\) has both endpoints in this group of size three, then there must be a measurement in the butterfly wing in this group of size three whose the endpoints coincide with either \(e\) or \(e'\), but not both. This measurement will distinguish these two edges by Lemma 1. Finally, consider the possibility that \(e'\) has exactly one endpoint in this group of size three. If the other endpoint of \(e'\) is in a different group of size three, then the measurement from the butterfly wing on this other group that shares an endpoint with \(e'\) will distinguish \(e,e'\) by Lemma 1. Else, the other endpoint \(u\) of \(e'\) is one of the left over vertices that were not grouped into groups of size three. If the butterfly wing in the group containing \(e\) has a measurement that coincides with \(e\), then that measurement will distinguish \(e,e'\) by Lemma 1. So now suppose the butterfly wing in the group containing \(e\) is such that the wing nodes are the endpoints of \(e\). If \(e'\) also has one of these wing nodes as its endpoint, then the measurement with the other wing node will distinguish \(e,e'\) by Lemma 1. Otherwise, we are in the case where \(e'\) has the center node \(v\) of this butterfly wing as one of its endpoints. In this case, Lemma 1 implies that the measurement using \(u\) and \(v_2\) will distinguish \(e,e'\). This holds in the case when \(v = v_2\), i.e., \(v\) is the center node of the first butterfly, and also when \(v\) is the center node of a different butterfly.

Case 2: The two endpoints of \(e\) are in different groups of size three.

If \(e'\) has both endpoints in the same group of size three, then this is symmetrical to Case 1. Thus, we assume \(e'\) does not have endpoints in the same group of size three. Suppose \(e\) and \(e'\) do not share an endpoint. Consider any one of the groups containing an endpoint of \(e\). At least one of the measurements in this butterfly wing will share an endpoint with \(e\) but not \(e'\), or vice versa. This measurement will distinguish \(e,e'\) by Lemma 1. Suppose now that \(e\) and \(e'\) do share an endpoint. Consider the group of three containing the other endpoint of \(e\). There must be a measurement in the butterfly wing in this group that shares an endpoint with \(e\) or \(e'\) but not both. This measurement will distinguish \(e,e'\) by Lemma 1.

Case 3: One endpoint of \(e\) is in a group of size three and the other one is not.

We may assume that one endpoint of \(e'\) is in a group of size three and the other one is not. Otherwise, we are in symmetrical cases to Case 1 and Case 2. Thus, both \(e\) and \(e'\) have endpoints \(u\) and \(u'\) that were not grouped into the groups of size three. Suppose \(u\neq u'\). If \(v_2\) is the endpoint of either \(e\) or \(e'\), we can use the measurement corresponding to that edge which will distinguish it from the other edge, by Lemma 1. Otherwise, \(v_2\) is not the other endpoint of \(e\) or \(e'\); then the measurement with source \(v_2\) and sink \(u\) will distinguish the edges, by Lemma 1. Suppose now \(u=u'\). If the other endpoints of \(e\) and \(e'\) are in different groups of size three, then any measurement from the butterfly wing in the group containing an endpoint of \(e\) will distinguish \(e,e'\) by Lemma 1. Finally, consider the case when the other endpoints of \(e\) and \(e'\) are in the same group of size three. Then one of the measurements in the butterfly wing on this group of size three shares an endpoint with \(e\) or \(e'\) but not both, which will distinguish \(e,e'\) by Lemma 1.

Case 4: Neither endpoint of \(e\) is in a group of size three.

This means both endpoints \(u_1\) and \(u_2\) of \(e\) are left over vertices from the grouping into size three groups. One of these vertices, say \(u_1\) without loss of generality, is not an endpoint of \(e'\). If \(v_2\) is not an endpoint of \(e'\) then the measurement with source \(v_2\) and sink \(u_1\) will distinguish \(e,e'\) by Lemma 1. Thus, assume \(v_2\) is an endpoint of \(e'\). Then, the measurement with source \(v_1\) and sink \(v_2\) (i.e., a measurement from the first group of size three) will distinguish \(e,e'\) by Lemma 1.

3.1.2 Lower Bound in Theorem 1↩︎

Let \(\mathcal{M}\) be any set of measurements that solves the faulty edge detection problem for the complete graph on \(n\) vertices and consider the measurement graph \(G' = (V, \mathcal{M})\) from Definition 4. We first observe that there can be no connected component of size two in \(G'\). If we had a component of size two \(C_1 = \{r,s\}\), then for any vertex \(d \in V\setminus\{r,s\}\) (which exists since \(n\geq 6\)), we will not be able to distinguish edge \((r,d)\) from \((s,d)\) by Lemma 1. We now consider two cases:

Case 1: \(G'\) has an isolated vertex.

First, there can be at most one isolated vertex in \(G'\). Indeed, suppose \(u\) and \(w\) are both isolated vertices in \(G'\), then for any vertex \(v \in V\setminus \{u,w\}\), no measurement will distinguish the edges \((u,v)\) and \((w,v)\) by Lemma 1. Moreover, since we have no size two components in \(G'\) by the observation before, all other connected components are of size three or more. We now claim that all size three connected components of \(G'\) must be triangles, i.e., all the edges must be measurements in \(\mathcal{M}\). Otherwise, suppose we have a size three component with vertices \(a,b,c\) and edges \((a,b)\) and \((a,c)\). Let the isolated vertex in \(G'\) be \(v\). Then no measurement can distinguish the edges \((v,a)\) and \((b,c)\) by Lemma 1. Let \(q\) be the number of size three components in \(G'\). Every component of size \(s\geq 4\) must have at least \(s - 1 \geq 3s/4\) edges. Thus, the number of measurements in \(\mathcal{M}\) is at least \[3q + \frac{3(n - 3q - 1)}{4} = \frac{3n}{4} + \frac{3q}{4} - \frac{3}{4} \geq \frac{3n}{4} - \frac{3}{4}.\] Since the number of measurements is an integer, we have a lower bound of \(\left\lceil \frac{3n}{4} - \frac{3}{4} \right\rceil\) which is at least \(\left \lceil \frac{2n}{3}\right \rceil\) for all \(n \geq 6\).

Case 2: \(G'\) has no isolated vertices.

In this case, each component of \(G'\) has at least three vertices, and any such component of size \(s \geq 3\) must have at least \(s-1 \geq \frac{2s}{3}\) edges. Thus, overall, \(G'\) must have at least \(\frac{2n}{3}\) edges and we have our lower bound of \(\left \lceil \frac{2n}{3}\right \rceil\) since the number of measurements must be an integer.

3.2 Bipartite Graphs↩︎

The characterization of the edge equivalence classes for any measurement in a complete \(k\)-partite graph, for \(k\geq 2\), given in Lemma 2 from Appendix 7 will be an important tool below. In particular, the altered resistance values in Tables 8 and 9 will be referred to many times. In these two tables, we use the convention that for any measurement \((r,s)\), we use \(p_r\) and \(p_s\) to denote the partitions containing \(r\) and \(s\), respectively.

3.2.1 Upper Bound in Theorem 2↩︎

Let \(B\) be a bipartite graph comprised of partitions \(p_\beta,p_\gamma\) such that \(|p_\beta| \leq |p_\gamma|\). We first prove that \(\left\lfloor{\frac{2}{3}|p_\gamma| + \frac{1}{3}|p_\beta|}\right\rfloor\) measurements suffice when \(|p_\beta| < |p_\gamma|\) and \(\left\lfloor{\frac{2n}{3}}\right\rfloor\) measurements suffice when \(|p_\beta| = |p_\gamma|\).

3.2.1.1 Strategy

We have two variants of the strategy to deal with the cases when the partitions are different sizes and when they have the same size.

3.2.1.2 Measurement Counts

It can be verified that the strategies in Definitions 10 and 11 give the stated measurement counts in Theorem 2.

3.2.1.3 Correctness

The following is the proof of correctness for the strategy outlined in Definition 10 for bipartite graphs with different sizes. The proof of the correctness of the strategy outlined in Definition 11 is provided in Case 9 of the proof of correctness for \(k\)-partite graphs (Section 3.4.2).

Recall we label the partitions \(p_\beta\) and \(p_\gamma\) with \(|p_\beta| < |p_\gamma|\). Consider two edges \((a,b)\) and \((a',b')\) with \(a, a' \in p_\beta\) and \(b,b' \in p_\gamma\). Since \(e \neq e'\), either \(a \neq a'\) or \(b\neq b'\). Recall that \(p_\beta\) and \(p_\gamma\) each contain at most one designated node not involved in any measurement. Further, we recognize that measurements that are within butterfly wing measurements are contained within \(p_\gamma\). Now we consider two cases.

Case 1: \(a \neq a'\). Since \(a \neq a'\), there must exist a measurement \((r,s)\) in the strategy from Definition 10 that involves exactly one of \(a\) or \(a'\); without loss of generality, let \(a\) be this vertex with \(a = r\). Suppose first that \(b = b'\). If \(b=s\), when \(e\) is altered, the effective resistance value comes from column I in Table 8, and for \(e'\), the value comes from column III as \(a' \in p_r, a' \neq r\) and \(b' = s\). If \(b \neq s\), then the effective resistance value comes from column II when \(e\) is altered and, since \(a' \in p_r, a' \neq r\) and \(b' \in p_s, b' \neq s\), for \(e'\), the effective resistance value comes from column IV. Next, suppose \(b \neq b'\). If \(b=s\), when \(e\) is altered, the effective resistance value comes from column I in Table 8, and for \(e'\), the value comes from column IV as \(a' \in p_r, a' \neq r\) and \(b' \neq s\). If \(b' = s\), then the effective resistance value when \(e\) is altered comes from column II in Table 8 since \(a = r\) and \(b \in p_s, b\neq s\), and when \(e'\) is altered, the value comes from column III since \(a' \in p_r, a' \neq r\) and \(b' = s\). Note that \(|p_r| \neq |p_s|\) because the bipartite graph has partitions of different sizes. Thus, the value in column II is different from the value in column III. Finally, if \(s\) is not equal to \(b\) or \(b'\), then the effective resistance value when \(e\) is altered comes from II and, since \(a' \in p_r, a' \neq r\) and \(b' \in p_s, b' \neq s\), for \(e'\), the effective resistance value comes from column IV.

Case 2: \(a' = a\). This implies \(b \neq b'\). Observe that there must exist a measurement \((r,s)\) in the strategy from Definition 10 that involves \(b\) or \(b'\) but not both; without loss of generality, let \(b\) be this vertex with \(b = s\). If the measurement endpoints are in different partitions, i.e., \(s \notin p_r\), when \(e\) is altered, the effective resistance value comes from column I in Table 8 if \(a=r\) and \(b=s\), and for \(e'\), the value comes from column II as \(a' = r\) and \(b' \in p_s, b' \neq s\). Another possibility is that \(a \in p_r, a\neq r\) and \(b = s\), meaning that when \(e\) is altered the effective resistance value comes from III, and for \(e'\), the value comes from IV as \(a' \in p_r, a' \neq r\) and \(b' \in p_s, b' \neq s\). Now, suppose the measurement endpoints are in the same partition, i.e. \(s \in p_r\). When \(e\) is altered, the effective resistance value comes from column X in Table 9 as \(a \notin p_r\) and \(b = s\) and, since \(a' \notin p_r\) and \(b' \in p_s, b' \neq s\), for \(e'\) the value comes from column XI (the endpoint labels on edges \((a,b)\) and \((a',b')\) should be switched to match with the convention in Table 9).

3.2.2 Lower Bound in Theorem 2↩︎

Let \(\mathcal{M}\) be any set of measurements that solves the faulty edge detection problem for the bipartite graph and consider the measurement graph \(G' = (V,\mathcal{M})\) from Definition 4.

We first discuss the lower bound achieved when \(|p_\beta| < |p_\gamma|\). We observe that we can have at most one isolated vertex in each partition in \(G'\). Otherwise, let \(a,a'\) be two isolated vertices in the same partition \(p_a\) and \(b \in p_b\) be any vertex in \(G\) with \(p_a \neq p_b\). Since \(a, a'\) are in the same partition and they are not the endpoint of any measurement, for both edges \((a,b)\) and \((a',b)\), the effective resistance value will come from the same column in Tables 8 and 9 when they are altered. Similarly, a component of size two in \(G'\) cannot be formed using two vertices in the same partition since two edges with these as endpoints and any other vertex in the other partition as the other endpoint cannot be distinguished by any measurement. Let \(q_2\) be the number of size two components in \(\mathcal{M}\). Since there can only be components of size two with endpoints in different partitions, the number of components of size two components is at most \(|p_\beta|\). The remaining components of size \(s \geq 3\) must have at least \(2s/3\) edges. Therefore, the number of measurements in \(\mathcal{M}\) is at least \[\begin{array}{rcl} q_2 + \frac{2(n-2-2q_2)}{3} & = &\frac{2n}{3} - \frac{q_2}{3} - \frac{4}{3} \\ & \geq &\frac{2n}{3} - \frac{|p_\beta|}{3} - \frac{4}{3} \\ & = & \frac{2|p_\gamma|}{3} + \frac{|p_\beta|}{3} - \frac{4}{3} \end{array}\]

Since the number of measurements is an integer, this gives at least \(\left\lfloor\frac{2|p_\gamma|}{3} + \frac{|p_\beta|}{3}\right\rfloor - 1\) measurements. This argument can be sharpened when \(|p_\gamma| - |p_\beta| \equiv 1\mod{3}\) or \(|p_\gamma| - |p_\beta| \equiv 2\mod{3}\). Note that in this case, if we have an isolated vertex in both partitions, then \(q_2 \leq |p_\beta| - 1\). If \(q_2 \leq |p_\beta| - 2\), then the right hand side of the second inequality above becomes \(\frac{2n}{3} - \frac{|p_\beta| - 2}{3} - \frac{4}{3} = \frac{2}{3}(|p_\gamma| - |p_\beta|) + |p_\beta| -\frac{2}{3}\). Since \(|p_\gamma| - |p_\beta| \equiv 1\mod{3}\) or \(|p_\gamma| - |p_\beta| \equiv 2\mod{3}\), \(\frac{2}{3}(|p_\gamma| - |p_\beta|) + |p_\beta| -\frac{2}{3} \geq \left\lfloor\frac{2|p_\gamma|}{3} + \frac{|p_\beta|}{3}\right\rfloor.\) If \(q_2 = |p_\beta| - 1\), then observe that we have components of size at least three on the remaining \(|p_\gamma| - |p_\beta|\) vertices in the \(p_\gamma\) component. In other words, we have at least \(\left\lceil \frac{2(|p_\gamma| - |p_\beta|)}{3} \right\rceil\) edges, and therefore, in total, \(\left\lceil \frac{2(|p_\gamma| - |p_\beta|)}{3} \right\rceil + |p_\beta| - 1\) edges. Since \(|p_\gamma| - |p_\beta| \not\equiv 0\mod{3}\), \(\left\lceil \frac{2(|p_\gamma| - |p_\beta|)}{3} \right\rceil + |p_\beta| - 1 \geq \left\lfloor \frac{2(|p_\gamma| - |p_\beta|)}{3} \right\rfloor + 1 + |p_\beta| - 1 = \left\lfloor\frac{2|p_\gamma|}{3} + \frac{|p_\beta|}{3}\right\rfloor\).

We now consider the case where \(|p_\beta| = |p_\gamma|\). As before, we can have at most 2 isolated vertices in \(G'\), and components of size two must have endpoints in both partitions. Moreover, we can have at most one component of size two. Indeed, if \(r,s\) and \(r',s'\) are two such measurements with \(r, r'\) in the same partition, then no measurement can distinguish the edges \((r,s')\) and \((r',s)\) since the sizes of the partitions are the same. Moreover, if one has 2 isolated vertices in \(G'\), then one cannot have a component of size two in \(G'\): Let \(u,u'\) be the isolated vertices and let \((v,v')\) be the single edge, with \(u,v\) in the same partition and \(u',v'\) in the same partition. Then no measurement in \(G'\) can distinguish between the edges \((u,v')\) and \((u',v)\). Indeed, when looking at \((v,v')\) as a measurement, the effective resistance values of the edges \((u,v')\) and \((u',v)\) will be the same as they come from columns II and III in Table 8 with \(|p_r| = |p_s|\). When looking at any other measurement in \(G'\), the values will come from column IV in Table 8 when the measurement endpoints are in different partitions and from columns XI in Table 9 when the measurement endpoints are in the same partition. Therefore, the number of measurements is at least \(\min\left\{\frac{2(n-2)}{3}, 1+\frac{2(n-3)}{3}\right\} \geq \frac{2n}{3} - \frac{4}{3}.\) Since the number of measurements must be an integer, this means we must have at least \(\left\lceil{\frac{2n}{3} - \frac{4}{3}}\right\rceil\) measurements. We now observe that when \(|p_\beta| \equiv 0\mod{3}\) or \(|p_\beta| \equiv 1\mod{3}\), i.e., \(n \equiv 0\mod{3}\) or \(n \equiv 2\mod{3}\), \(\left\lceil\frac{2n}{3} - \frac{4}{3}\right\rceil \geq \left\lfloor\frac{2n}{3}\right\rfloor - 1\), and when \(|p_\beta| \equiv 2\mod{3}\), i.e., \(n \equiv 1\mod{3}\), \(\left\lceil\frac{2n}{3} - \frac{4}{3}\right\rceil = \left\lceil\left\lfloor\frac{2n}{3}\right\rfloor + \frac{2}{3} - \frac{4}{3}\right\rceil = \left\lfloor\frac{2n}{3}\right\rfloor + \left\lceil\frac{2}{3} - \frac{4}{3}\right\rceil = \left\lfloor\frac{2n}{3}\right\rfloor\).

3.3 Complete tripartite graphs↩︎

Using the same notational conventions and similar techniques used in the proof of Theorem 2 in Section 3.2, we present the proof for complete tripartite graphs.

3.3.1 Upper Bound in Theorem 3↩︎

3.3.1.1 Strategy

For the case that \(|p_\alpha| = |p_\beta| = |p_\gamma|\), the strategy is to maintain three designated vertices, one in each partition, and to place tripartite butterfly wing measurements (Definition 6) on the remaining vertices.

For the case that \(|p_\alpha| < |p_\beta| < |p_\gamma|\), the strategy is to maintain three designated vertices, one in each partition. If \(n\) is odd, there exists a perfect matching on the remaining \(n-3\) vertices and we use the measurements that coincide with this matching. If \(n\) is even, place a tripartite butterfly wing measurement (Definition 6) and the remaining vertices will have a proper matching that will dictate which measurements should be selected.

For the case that \(|p_\alpha| = |p_\beta| < |p_\gamma|\), the strategy is again to maintain three designated vertices \(v_\alpha, v_\beta, v_\gamma\), one in each partition, and then place as many matching measurements as possible from vertices in \(p_\alpha/\{v_\alpha\}\) to vertices in \(p_\gamma/\{v_\gamma\}\), and then as many as possible from vertices in \(p_\beta/\{v_\beta\}\) to vertices in \(p_\gamma/\{v_\gamma\}\). If any vertices remain in \(p_\beta/\{v_\beta\}\) or \(p_\gamma/\{v_\gamma\}\) (note that we cannot have vertices left over in both \(p_\beta/\{v_\beta\}\) and \(p_\gamma/\{v_\gamma\}\)), place as many disjoint partition butterfly wing measurements (Definition 9) as possible, on the vertices that are left over. If there is one vertex \(v\) left over, which is not the designated vertex in this partition, and it is not involved in any measurement so far, place a measurement from \(v\) to any previously used vertex in that partition. If there are two vertices left over, place a partition butterfly measurement involving these two and the designated vertex in this partition.

For the case that \(|p_\alpha| < |p_\beta| = |p_\gamma|\), the strategy is again to maintain three designated vertices \(v_\alpha, v_\beta, v_\gamma\), one in each partition, and then place as many matching measurements as possible from \(p_\alpha/\{v_\alpha\}\) to \(p_\beta/\{v_\beta\}\). Next, we place as many disjoint partition butterfly wing measurements (Definition 9) as possible, on the vertices that are left over in \(p_\beta/\{v_\beta\}\) and \(p_\gamma/\{v_\gamma\}\). Now, for both partitions \(p_\beta\) and \(p_\gamma\), we do the following. If there is one vertex left over, which is not the designated vertex in that partition, and it is not involved in any measurement so far, place a measurement from that vertex to any previously used vertex in that partition. If there are two vertices left over, place a partition butterfly measurement involving these two and the designated vertex in that partition.

3.3.1.2 Measurement Counts

We provide the bounds for the four cases in Table 1 under the column titled “Upper Bound”.

3.3.1.3 Correctness

We leave the proofs of correctness to the reader. However, the proofs follow a similar argument to that provided in Case 2 of the proof of correctness for \(k\)-partite graphs.

3.3.2 Lower Bound in Theorem 3↩︎

The proof of this lower bound is similar to that of the lower bound proof of Theorem 4 in Section 3.4.1. Let \(\mathcal{M}\) be any set of measurements that solves the faulty edge detection problem for the tripartite graph and consider the measurement graph \(G' = (V,\mathcal{M})\) from Definition 4. As in Section 3.4.1, we recognize that there can be at most one isolated vertex in each partition in \(G'\). Otherwise, let \(a,a'\) be two isolated vertices in the same partition and let \(b\) be any vertex in a different partition of \(G'\). Consider a measurement \((r,s)\). Because \(a\) and \(a'\) are in the same partition and they are not an endpoint of any measurements, when \((a,b)\) or \((a',b)\) are altered, they will have the same effective resistance value coming from columns III,IV,VI,VII or VIII in Table 8 if \(s \not\in p_r\), and from columns X, XI or XII in Table 9 if \(s \in p_r\). Thus, there are at least \(n-3\) vertices with degree at least 1 in \(G'\), meaning the sum of the degrees in \(G'\) is at least \(n-3\). By the Handshaking Lemma, there must be at least \(\frac{n-3}{2}\) edges in \(G'\) and since the number of edges must be an integer, there are at least \(\left\lceil\frac{n-3}{2}\right\rceil\) edges in \(G'\).

The two provided claims give the lower bounds in the first and last rows of Table 1. The cases where two of the partitions are the same size and the third one is different (smaller or larger) can be handled in the same way, yielding the lower bounds in the second and third rows of Table 1.

3.4 Complete \(k\)-partite Graphs↩︎

We prove Theorem 4 in this section. Lemma 2 in Appendix 7 will provide the edge equivalence classes for a given measurement. The proof will utilize altered resistance values listed in Tables 8 and 9. As mentioned above in Section 3.2, we use the convention in these two tables that for any measurement \((r,s)\), we use \(p_r\) and \(p_s\) to denote the partitions containing \(r\) and \(s\), respectively. We prove the stated lower bound below, and then establish the stated upper bound.

3.4.1 Lower Bound in Theorem 4↩︎

Let \(\mathcal{M}\) be any set of measurements that solves the faulty edge detection problem for the complete \(k\)-partite graph with \(k\geq 2\) and consider the measurement graph \(G' = (V,\mathcal{M})\) from Definition 4. We first observe that we can have at most one isolated vertex in each partition in \(G'\). Otherwise, let \(a,a'\) be two isolated vertices in the same partition \(p_a\) and let \(b \in p_b\) be any vertex in \(G\) with \(p_a \neq p_b\). Consider any measurement \((r,s)\). Since \(a, a'\) are in the same partition and they are not the endpoint of any measurement, for both edges \((a,b)\) and \((a',b)\), the effective resistance value will come from the same column (one of III, IV, VI, VII, VIII, or IX from Table 8 if \(r,s\) are in different partitions, or columns X, XI, XII from Table 9 if \(r,s\) are in the same partition) when they are altered.

Thus, we have at least \(n-k\) vertices with degree at least 1 in \(G'\) and so the sum of the degrees is at least \(n-k\). By the Handshaking lemma, we must have at least \(\frac{n-k}{2}\) edges, and since the number of edges is an integer, it must be at least \(\left\lceil\frac{n-k}{2}\right\rceil\).

3.4.2 Upper Bound in Theorem 4↩︎

3.4.2.1 The measurement strategy

We describe a measurement strategy for any tripartite graph. This will form the building block for the general \(k\)-partite case. Below, we employ notation like \(u \in p_u\) because we feel this is intuitive; however, the symbol/variable \(u\) is being used to denote both a vertex and a natural number, i.e., the index of the partition. We believe the intuitive clarity justifies this slight abuse of notation.

We now describe the strategy for the general \(k\)-partite graph with partitions \(p_1, \ldots, p_k\) satisfying \(2 \leq |p_1| \leq \ldots \leq |p_k|\). If \(k\equiv 1 \mod{3}\), let \(i \in \{1, \ldots, k\}\) be the index that achieves the minimum in \(\min_{i\in\{1,\ldots, k\}}\left\{\left\lceil\frac{2(|p_i| - 1)}{3}\right\rceil + val(L\setminus\{i\})\right\}\), and let the partition \(p_i\) be called \(P\). If \(k\equiv 2 \mod{3}\), let \(i,j \in \{1, \ldots, k\}\) be the indices that achieve the minimum in \[\min_{i, j\in \{1,\ldots, k\},\; i\neq j}\left\{\left\lceil\frac{2(|p_i| + |p_j| - 2)}{3}\right\rceil + val(L\setminus\{i,j\})\right\}.\] In this case, the partitions \(p_i\) and \(p_j\) form a bipartite subgraph that will be called \(B\) in the following. In both cases, we group the remaining partitions, i.e., indexed by \(\{1, \ldots, k\}\setminus \{i\}\) in the first case and \(\{1, \ldots, k\}\setminus \{i,j\}\) in the second case, into tripartite subgraphs in order of the sizes of the partitions. We refer to these tripartite subgraphs as \(T_1, \ldots, T_{\lfloor k/3\rfloor}\).

We next implement the following steps.

1. The tripartite graph strategy (Definition 12) is applied to \(T_i\) for all \(i = 1, \ldots, \lfloor k/3 \rfloor\).

2. If \(k\equiv 1 \mod{3}\), place as many partition butterfly wing measurements (Definition 9) within this partition as possible. If any vertices remain in \(P\) that were not used in any of these partition butterfly measurements, place a measurement from each of these vertices to \(w\), where \(w\) is any center node of a partition butterfly measurement in \(P\).

3. If \(k\equiv 2 \mod{3}\), let \(p_i, p_j\) denote the partitions used to form the bipartite subgraph \(B\) such that \(|p_i| \leq |p_j|\). Maintain one designated node \(u \in p_i\). Place as many disjoint zig-zagging bipartite wing measurement schemes (Definition 7) as possible, between \(p_i\) and \(p_j\) without involving the designated node \(u\). If one node \(v \in p_i\setminus\{u\}\) remains that is unable to be placed in a zig-zagging butterfly wing measurement scheme, place a hairpin butterfly wing measurement (Definition 8) between \(p_i\) and \(p_j\) with \(v\in p_i\setminus\{u\}\) as the center node, without involving any of the previously used nodes. If there are two nodes \(v_1,v_2 \in p_i\setminus\{u\}\) that have not been used in any measurements so far, place a hairpin butterfly wing measurement between \(p_i\) and \(p_j\) with \(v_1,v_2\) as its wing nodes, and any unused node in \(p_j\) as the center node. If there are nodes left in \(p_j\) that have not been used in any measurements so far, place as many disjoint partition butterfly wing measurements (Definition 9) as possible within \(p_j\). If one node \(v\) remains in \(p_j\) that has not been used in any measurements so far, make measurement \((v,w)\) where \(w\) is any previously used center node in \(p_j\). If two nodes \(v_1, v_2\) remain that have not been used in any measurements so far, place a partition butterfly wing measurement involving \(v_1, w, v_2\), where \(w\) is any previously-used center node in \(p_j\).

We claim that the above measurement strategy suffices.

3.4.2.2 Measurement Counts

We first count the number of measurements used in the tripartite graph measurement strategy (Definition 12). One has to consider nine different cases, depending on the relationships between the partition sizes \(|p_\alpha|, |p_\beta|\) and \(|p_\gamma|\). It can be verified that these counts are given by the values enumerated in Table 2. Since \(|p_\alpha| \leq |p_\beta| \leq |p_\gamma|\) in all cases and the number of measurements must be integer, we see from the values in Table 2 that we have a general upper bound of \(2|p_\gamma|-2\).

For the general \(k\)-partite case, we observe that if \(k \equiv 0 \mod{3}\), then we simply have the bounds from the \(k/3\) tripartite subgraphs, giving us an upper bound of \(\sum_{i \in [k]: i \mod{3} = 0} (2|p_i| -2)\). If \(k \equiv 1 \mod{3}\), then once we select the isolated partition \(P\) as per our strategy, we can apply the tripartite upper bound of \(2|p_\gamma| - 2\) for each of the tripartite subgraphs \(T_i\), \(i=1, \ldots, \lfloor k/3 \rfloor\). By definition of \(val(L)\) for an ordered list \(L\) of numbers (Definition 3) and the choice of \(P\), we have the stated bound. Similarly, in the case where \(k \equiv 2 \mod{3}\), our choice of the bipartite subgraph \(B\) and the definition of \(val(L)\) gives the stated bound.

3.4.2.3 Correctness

Consider any two edges \(e,e' \in E(G)\) with \(e = (a,b)\) and \(e' = (a',b')\), where \(a \in p_a, b \in p_b, a' \in p_{a'}, b' \in p_{b'}\). We must show that there exists a measurement which gives different effective resistance values when these two edges are altered. Note that this notation implies, for example, that \(s \in p_b\) if and only if \(b \in p_s\). We will use such facts without explicit mention below. In the case analysis, when we consider tripartite subgraphs \(T_i, T_j, T_k\), we allow for the possibility that some subset of the indices \(\{i,j,k\}\) (possibly all) are all equal to each other unless some pairs are explicitly assumed to be unequal in the case under consideration.

Case 1: \(e\) has both endpoints in \(T_i\) and \(e'\) has both endpoints in \(T_j\) such that \(i \neq j\)

We observe that there exists a measurement \((r,s)\) within a tripartite butterfly wing measurement in \(T_i\) such that \(a \in p_r\). Using this measurement, the effective resistance when \(e'\) is altered has value corresponding to column IX in Table 8, and for \(e\), the new effective resistance will have value from any of the columns from I to VI since \(a \in p_r\). This implies that these two edges will give differing values of effective resistance for measurement \((r, s)\) when altered.

Case 2: \(e\) and \(e'\) have both endpoints in \(T_i\) for some \(i\)

Since there are only three partitions in \(T_i\), one of these partitions must contain an endpoint of both edges. Without loss of generality, let \(a,a'\) be in the same partition \(p_a\) in \(T_i\).

Case 2a: Suppose \(b\) and \(b'\) are in different partitions. In this case, any measurement \((r,s)\) within a tripartite butterfly wing measurement in \(T_i\) such that \(r \in p_a\) and \(s \in p_b \cup p_{b'}\) will distinguish \(e\) and \(e'\). Since \(b, b'\) are in different partitions, we may assume (up to a relabeling of the edges) that \(s \in p_b\) or equivalently, \(b \in p_s\). If \(a = r\) and \(b =s\), when \(e\) is altered, the effective resistance value comes from column I and for \(e'\), the value comes from either column V if \(a' = a\) or column VI if \(a' \neq a\). Similarly, if \(a = r\) and \(b \in p_s, b \neq s\), for \(e\), the value comes from column II, and for \(e'\), the value comes from either column V if \(a' = a\) or column VI if \(a' \neq a\). If \(a \neq r\) and \(b = s\), when \(e\) is altered, the effective resistance value comes from column III, and for \(e'\), the value comes from column V or column VI depending on whether or not \(a' = r\). If \(a \neq r\) and \(b \in p_s, b \neq s\), for \(e\) the value comes from column IV, and for \(e'\) value comes from column V or column VI depending on whether or not \(a' = r\).

Case 2b: Suppose \(b\) and \(b'\) are in the same partition. We now go through the following possibilities.

Suppose \(a = a'\). Either \(b\) or \(b'\) must be involved in a measurement since there is at most one designated node in the partition containing \(b, b'\). Without loss of generality, let us assume that \(b\) is one of the endpoints of the measurement \((r,s)\) with \(b=s\). If \(r = a = a'\), then the value when \(e\) is altered comes from column I in Table 8, and for \(e'\), the value comes from column II. If \(r \in p_a\) but \(r \neq a\), then for \(e\), the value comes from III and for \(e'\), it is column IV. If \(r\) is in the partition that is different from \(p_a\) and \(p_b\), then for \(e\), the value comes from column VII and for \(e'\), we use column VIII. Finally, if \(r \in p_b\), then for \(e\), the value comes from column X in Table 9, and for \(e'\), the value comes from XI (Note that to read the values in Table 9, we have to switch the labels of the endpoints of the two edges).

Suppose \(b = b'\) (and therefore, \(a\neq a'\)). Observe that up to relabeling of the labels on the endpoints, this case is the same as the previous case with \(a=a'\).

We now consider the situation where \(a \neq a'\) and \(b \neq b'\). Either \(a\) or \(a'\) must be involved in a measurement since there is at most one designated node in the partition \(p_a\). Without loss of generality, let us assume that \(a\) is one of the endpoints of the measurement \((r,s)\) with \(a = r\). If \(s\) is in the partition that does not contain \(a\) or \(b\), then if \(e\) is altered, the effective resistance value comes from column V, and for \(e'\), the value comes from column VI. If \(s \in p_b\) with \(s \neq b'\), then if \(e\) is altered, the effective resistance value comes from either column I or II depending on whether \(s = b\) or not, and for \(e'\), the value comes from column IV. If \(s \in p_b\) with \(s = b'\), then there exists a different measurement \((\bar r, \bar s)\) in the strategy incident on either \(a\) or \(b'\) (since there are no components of size two in the measurement graph for the outlined measurement strategy). Again, up to switching the labels on the endpoints of the edges, we may assume \(\bar r = a\). Now we must fall into one of the previously considered cases and we are done. Finally, consider the case where \(s \in p_a\). If \(s \neq a'\), then for \(e\), the value comes from column X in Table 9 and for \(e'\), it comes from column XI. If \(s = a'\), then there exists a different measurement \((\bar r, \bar s)\) in the strategy incident on either \(a\) or \(a'\) (since there are no components of size two in the measurement graph for the outlined measurement strategy). In fact, both \(\bar r\) and \(\bar s\) must be in \(p_a\) because \(r,s\) must be involved in a partition butterfly wing measurement within \(p_a\). We are again able to distinguish edges \(e, e'\) using columns X and XI, respectively, in Table 9.

Case 3: \(e\) has both endpoints in \(T_i\) and \(e'\) has one endpoint in \(T_j\) and another in \(T_k\) such that \(j \neq k\)

Without loss of generality, assume \(k \neq i\) and \(b' \in p_{b'} \subset T_k\). There exists a measurement \((r,s)\) within a tripartite butterfly wing measurement in \(T_k\) such that \(b' \in p_{s}\) that will distinguish \(e\) and \(e'\). This is because the effective resistance value when \(e\) is altered comes from column IX in Table 8 since \(a,b \notin \{p_r,p_s\}\), and for \(e'\) the value comes from columns VII or VIII depending on whether or not \(b'=s\). This implies that the edges will have different values for the effective resistance when altered.

Case 4: \(e\) has one endpoint in \(T_{i_1}\) and another in \(T_{i_2}\) \((i_1 < i_2)\) and \(e'\) has one endpoint in \(T_{j_1}\) and
another in \(T_{j_2}\) \((j_1 < j_2)\)

First, we examine the case in which either \(i_1 \neq j_1\) or \(i_2 \neq j_2\). We consider the case \(i_2 \neq j_2\); the other case has a symmetrical argument. There exists a measurement \((r,s)\) within a tripartite butterfly wing measurement in \(T_{j_2}\) such that \(b' \in p_s \subset T_{j_2}\). Using this measurement, we will be able to distinguish \(e\) and \(e'\) as they will have different values for effective resistance; for \(e\), the value comes from column IX in Table 8 since \(a,b \notin \{ p_r,p_s\}\) and for \(e'\), the value comes from VII or VIII depending on whether or not \(b' = s\).

If \(i_1 = j_1\) and \(i_2 = j_2\), we first consider the case where either \(a' \not\in p_a\) or \(b' \not\in p_b\). In the first case, we can use a tripartite measurement \((r,s)\) such that \(r \in p_a \cup p_{a'}\) and \(s \in T_{i_1}/\{p_a,p_{a'}\}\) to distinguish the edges. Indeed, we may assume (up to changing the labels on the edges) that \(a \in p_r\). Therefore, when \(e\) is altered, the effective resistance value comes from column V or VI depending on whether or not \(a = r\), and for \(e'\), the value comes from column IX as \(a',b' \notin \{p_r,p_s\}\). The case where \(b' \not\in p_b\) can be argued in the same way after switching the labels on the endpoints of both edges.

So, we now consider the situation where \(a'\in p_a\) and \(b' \in p_b\). Since \(e \neq e'\), either \(a \neq a'\) or \(b\neq b'\). Up to a relabeling of the endpoints, we may assume \(b \neq b'\). Since \(b,b' \in p_b\), one of them must be involved in a measurement \(r,s\) since there is at most one designated vertex in every partition that is not involved in any measurement. Further, there must exist a measurement that involves \(b\) or \(b'\) but not both since there are no components of size two in the measurement graph associated with the outlined measurement strategy.

Without loss of generality, we assume that \(b = s\). Regardless of whether or not \(a = a'\), we are able to say the following about the effective resistance values when \(e\) and \(e'\) are altered. If \(r\) is not in the same partition \(p_b\) as \(s\), for \(e\), the value comes from column VII in Table 8 since \(a \notin p_r\), and for \(e'\), the value comes from column VIII as \(b \in p_s, b\neq s\) and \(a' \notin p_r\). If \(r\) is in the same partition \(p_b\) as \(s\), for \(e\), the value comes from column X in Table 9, and for \(e'\), the value comes from column XI as \(a' \notin p_r\) and \(b' \in p_r\) (Note that one has to switch the labels on the endpoints of the edges to read the values from Table 9).

Case 5: \(e\) has one endpoint in P and another in \(T_i\) and \(e'\) has one endpoint in \(T_j\) and another in \(T_k\)

For edge \(e\), let \(a \in P\) and \(b \in T_i\). We use a partition butterfly wing measurement \((r,s)\) within \(P\) such that \(a = r\). This means that when \(e\) is altered, the effective resistance value comes from column X, and for \(e'\), the value comes from column XII as \(a, b \notin p_r\).

Case 6: \(e\) has one endpoint in \(P\) and another in \(T_i\) and \(e'\) has one endpoint in \(P\) and another in \(T_j\)

Let \(a,a' \in P\), \(b \in T_i\), and \(b' \in T_j\). If \(a \neq a'\), then there exists a partition butterfly wing measurement \((r,s)\) that uses exactly one of the vertices \(a\) and \(a'\), and we may assume without loss of generality that \(a=r\). If \(e\) is altered, the effective resistance value will come from column X, and for \(e'\), the value comes from column XI.

If \(a = a'\), we use a tripartite butterfly wing measurement \((r,s)\) in \(T_i\) such that \(s \in p_b \cup p_{b'}\). Without loss of generality, let \(s \in p_b\). If \(b' \notin p_b\), then the effective resistance value when \(e\) is altered comes from columns VII or VIII depending on whether or not \(b = s\), and for \(e'\), the value comes from column IX as \(a',b' \notin \{ p_r,p_s \}\). If \(b' \in p_b\), then there exists a measurement involving \(b\) or \(b'\) but not both as we cannot have more than one designated node within a partition and there cannot be components of size two in the measurement graph for the outlined measurement strategy. Again, without loss of generality, let \(b = s\). If \(s \notin p_r\), then the effective resistance value when \(e\) is altered comes from column VII from Table 8 as \(a \notin p_r\), and for \(e'\), the value comes from column VIII as \(a' \notin p_r\) and \(b' \in p_s, b' \neq s\). If \(s \in p_r\), then for \(e\), the value comes from column X in Table 9, and for \(e'\) the value comes from column XI as \(a \notin p_r\) and \(b' \in p_r, b' \neq s\) (One has to switch the labels on the endpoints of the edges to read off the values from Table 9).

Case 7: \(e\) has both endpoints in \(B\) and \(e'\) has one endpoint in \(T_i\) and another in \(T_j\)

Without loss of generality, assume \(b' \in T_j\). Regardless of whether \(i=j\) or not, we use a measurement \((r,s)\) within a tripartite butterfly wing measurement in \(T_j\) such that \(b' \in p_s\) (and thus \(r \in T_j \setminus p_{b'}\)). This measurement allows us to say that when \(e\) is altered, the effective resistance value comes from column IX in Table 8 as \(a,b \notin \{p_r,p_s\}\) and for \(e'\), the value comes from columns I–VIII depending on the which partitions \(a',b' , r\) and \(s\) fall into within \(T_i\) and \(T_j\) (with the possibility that \(i=j\)).

Case 8: \(e\) has both endpoints in \(B\) and \(e'\) has one endpoint in \(B\) and another in \(T_i\)

Without loss of generality, let \(b' \in p_{b'} \subset T_i\). We use a measurement \((r,s)\) within a tripartite butterfly wing measurement in \(T_{i}\) such that \(b' \in p_s\) and \(r\) is in another partition in \(T_{i}\). This means that when \(e\) is altered, the effective resistance value comes from column IX in Table 8 as \(a,b \notin \{p_r,p_s\}\), and for \(e'\), the value comes from column VII if \(b' = s\) or column VIII if \(b' \neq s\).

Case 9: \(e\) and \(e'\) have both endpoints in \(B\)

Let \(a, a' \in p_a\) and \(b,b' \in p_b\). Since \(e \neq e'\), either \(a \neq a'\) or \(b\neq b'\). Up to a relabeling of the endpoints, we may assume that \(a \neq a'\). Recall that \(p_a\) contains at most one designated node not involved in any measurement. Further, there are no components of size two in the measurement graph associated with the outlined measurement strategy. Therefore, there must exist a measurement \((r,s)\) that involves \(a\) or \(a'\) but not both. Without loss of generality, let \(a\) be this vertex with \(a = r\).

Suppose first that \(b = b'\). If \(s \notin p_r\) and if \(b = s\), when \(e\) is altered, the effective resistance value comes from column I in Table 8 since \(a=r\), and for \(e'\), the value comes from column III since \(a' \in p_r, a' \neq r\). If \(s \notin p_r\) and \(b \in p_s\) with \(b \neq s\), when \(e\) is altered, the value comes from column II since \(a =r\), and for \(e'\), the value comes from column IV since \(a' \in p_r, a' \neq r\). If instead \(s \in p_r\), the effective resistance value when \(e\) is altered comes from column X in Table 9 as \(a=r\), and for \(e'\), the value comes from column XI as \(a' \in p_r, a' \neq r\) by the choice of \((r,s)\).

Suppose now that \(b \neq b'\). If \(s \in p_r\), then \((r,s)\) is a partition butterfly wing measurement, in which case for \(e\), the effective resistance value comes from column X in Table 9, and for \(e'\), the value comes from column XI as \(a' \in p_r, a' \neq r\) by the choice of \((r,s)\), and \(b \notin p_r\). Now, suppose \(s \notin p_r\). If \(s \neq b'\), then the effective resistance value when \(e\) is altered comes from column I or column II in Table 8 depending on whether \(b = s\) or not, and for \(e'\), the value comes from column IV as \(a' \in p_r, a' \neq r\) and \(b' \in p_s, b'\neq s\). Finally, consider the situation that \(s = b'\). Since there are no components of size two in the measurement graph associated with the outlined measurement strategy, there must exist another measurement \((\bar r, \bar s)\) with either \(\bar r = a\) or \(\bar s = b'\), but not both. Then, up to relabeling the endpoints of the edges, we can apply one of the previous arguments within this paragraph.

Case 10: \(e\) has one endpoint in \(B\) and another in \(T_i\) and \(e'\) has one endpoint in \(T_j\) and another in \(T_k\)

Let \(a \in p_a \subseteq B\). We can distinguish the edges by using any measurement \((r,s)\) that is a measurement from a zig-zagging butterfly wing scheme or a hairpin butterfly wing measurement and that uses a vertex in \(p_a\). As \(b \notin p_s\), when \(e\) is altered, the effective resistance value comes from column V or column VI depending on whether \(a = r\) or not, and for \(e'\), the value comes from column IX since \(a', b' \notin \{ p_r,p_s \}\).

Case 11: \(e\) has one endpoint in \(B\) and another in \(T_i\) and \(e'\) has one endpoint in \(B\) and another in \(T_j\)

Let \(a \in p_a \subseteq B\), \(a' \in p_{a'} \subseteq B\) and consider the following three subcases.

If \(a = a'\), the same argument as that of Case 7 when \(a=a'\) can be used to show that a tripartite butterfly wing measurement \((r,s)\) in \(T_i\) such that \(s \in p_b \cup p_{b'}\) exists and will distinguish \(e\) and \(e'\).

Suppose now that \(a' \in p_a\), but \(a \neq a'\). Recall that there is at most one designated node in any partition that is not involved in a measurement in the strategy, and there are no components of size two in the measurement graph associated with the strategy. Thus, there must exist a measurement \((r,s)\) in \(B\) that has \(a\) or \(a'\), but not both, as an endpoint; without loss of generality, let \(a = r\). If \(s \notin p_r\), this means that when \(e\) is altered, the effective resistance value comes from column V as \(a=r\) and \(b \notin p_s\), and for \(e'\), the value comes from column VI since \(a' \in p_r, a' \neq r\) and \(b' \notin p_s\). If \(s \in p_r\), then for \(e\), the value comes from column X as \(b \notin \{p_r,p_s\}\), and for \(e'\), the value comes from XI since \(a' \in p_r, a' \neq r\) and \(b' \notin \{p_r,p_s\}\).

Finally, if \(a' \notin p_a\), using the same logic, there must exist a measurement that involves exactly one of \(a\) or \(a'\) as an endpoint; let \(a\) be involved in measurement \((r,s)\) with \(a = r\). If \(s \notin p_r\), this means that \(e\) will have value from column V as \(a=r\) and \(b \notin p_s\), and for \(e'\) the value comes from column VI since \(a' \in p_r, a' \neq r\) and \(b' \notin p_s\) (after switching the labels on \(r,s\)). If \(s \in p_r\), then for \(e\), the value comes from column X, and for \(e'\), the value comes from XII since \(a', b' \notin p_r\).

4 Conclusion and future directions↩︎

In this paper, we introduce a new combinatorial optimization problem (Definition 1) motivated by a fundamental question in fault diagnosis in electrical systems. We believe the problem is mathematically rich and the insights are widely applicable in diverse areas. There are two broad future research directions to pursue:

. In this paper, we focus on giving tight lower and upper bounds on the smallest number of measurements in complete graphs and complete \(k\)-partite graphs. It would be great to extend this analysis to other important families of graphs, e.g. grid/lattice graphs (in general \(d\)-dimensions), wheels, polyhedral graphs for structured polyhedra such as hypercubes/fullerene graphs, and others. Beyond tight bounds on the smallest number of measurements, one can also give other insights on the structure of the optimal set of measurements for structured graph families, or relate the optimal number of measurements to other well-studied combinatorial properties such as edge covers, matchings etc., or spectral properties of the Laplacian or adjacency matrices.

. The design of efficient algorithms for solving the faulty edge detection problem has never been explored in the literature, to the best of our knowledge. For example, the following question is open:

For what class of graphs can the faulty edge detection problem be solved in polynomial time?

It is not hard to show that the problem can be modeled as a set cover or an integer programming problem. The polyhedral combinatorics of this special set cover/integer programming problem is also worth studying, e.g., deriving classes of valid inequalities for the feasible solutions. This will have computational implications in terms of speeding up integer programming based algorithms for the faulty edge detection problem.

Acknowledgments↩︎

The authors gratefully acknowledge the support from the Air Force Office of Scientific Research (AFOSR) grant FA9550-25-1-0038. The authors are also very grateful to Prof. Daniel Naiman and Prof. Fadil Santosa at Johns Hopkins University for suggesting the fault detection problem in Definition 2 in the first place, and for very helpful discussions around the problem.

5 The Laplacian and Effective Resistance↩︎

We discuss matrix representations of a graph \(G\) that are used in obtaining effective resistance values within the original graph \(G\) and when an edge \((a,b)\in E\) is altered.

Below, given a Laplacian matrix \(L\), \(L(v)\) denotes the Laplacian matrix with the \(v\)-th row and column removed.

The values in ?? are standard in electrical network theory and the values in ?? come about from using the Sherman-Morrison-Woodbury formula for computing the Laplacian inverse entries after updating the weight of the edge. For details, see Theorem 5.2 and equation (5.4) in [22].

6 Effective resistance values for complete graphs↩︎

The Laplacian \(L\) of a complete graph \(\mathbb{K}_n\) has entries \(L_{ii} = n-1\) for \(i=1, \ldots, n\) and \(L_{ij} = -1\) for all \(i \neq j\). For any vertex \(v\), after eliminating the \(v^{th}\) row and column from \(L\), the inverse \(L(v)^{-1}\) has entries \(L(v)^{-1}_{ii} = \frac{2}{n}\) and \(L(v)^{-1}_{ij} = \frac{1}{n}\) for all \(i \neq j\).

7 Effective resistance values for k-partite graphs↩︎

Let \(P = \{p_1, ... p_k\}\) represent the set of \(k\) partitions of a complete \(k\)-partite graph \(G\) and let \(n = \sum_{i=1}^k |p_i|\). The Laplacian matrix of \(G\) is a block matrix with blocks of size \(|p_i|\) by \(|p_j|\). For any \(v\in V\), \(L(v)\) has the following block representation. We use \(\mathbb{1}_{d\times d}\) and \(\mathbb{I}_{d\times d}\) to denote the all ones and the identity matrices of size \(d\times d\), respectively. We introduce the notation \(\widetilde{p_i} = p_i -1\) for this purpose (making the formulas compact when the \(v^{th}\) row and column has been removed). For ease of exposition, we give the formulas when \(v\in p_1\); when \(v\) is in the other partitions, the formulas are modified accordingly.

\[\begin{bmatrix} (n - |p_1|)\mathbb{I}_{|\widetilde{p_1}| x |\widetilde{p_1}|} & -\mathbb{1}_{|\widetilde{p_1}| x |p_2|} & ... & -\mathbb{1}_{|\widetilde{p_1}| x |p_k|}\\ -\mathbb{1}_{|p_2| x |\widetilde{p_1}|} & (n-|p_2|)\mathbb{I}_{|p_2| x |p_2|} & \ddots & \vdots \\ \vdots & \ddots & \ddots & -\mathbb{1}_{|p_{k-1}| x |p_{k}|} \\ -\mathbb{1}_{|p_k| x |\widetilde{p_1}|} & \dots & -\mathbb{1}_{|p_{k}| x |p_{k-1}|} & (n-|p_k|)\mathbb{I}_{|p_k| x |p_k|} \end{bmatrix}\]

The inverse of \(L(v)\) is given by the following block representation multiplied by the factor \(\frac{1}{n-|p_1|}\). This can be checked by direct matrix multiplication calculations.

\[\begin{bmatrix} \mathbb{1}_{|\widetilde{p_1}| x |\widetilde{p_1}|} + \mathbb{I}_{|\widetilde{p_1}| x |\widetilde{p_1}|} & \mathbb{1}_{|\widetilde{p_1}| x |p_2|} & \mathbb{1}_{|\widetilde{p_1}| x |p_3|} & \dots & \mathbb{1}_{|\widetilde{p_1}| x |p_k|} \\ \mathbb{1}_{|p_2| x |\widetilde{p_1}|} & D_{p_2} & \frac{n-1}{n}\mathbb{1}_{|p_2| x |p_3|} & \dots & \frac{n-1}{n}\mathbb{1}_{|p_2| x |p_k|}\\ \vdots & \frac{n-1}{n}\mathbb{1}_{|p_3| x |p_2|} & \ddots & \ddots & \vdots \\ \vdots & \vdots & \ddots & \ddots & \frac{n-1}{n}\mathbb{1}_{|p_{k-1}| x |p_k|} \\ \mathbb{1}_{|p_k| x |\widetilde{p_1}|} & \frac{n-1}{n}\mathbb{1}_{|p_k| x |p_2|} & \dots & \frac{n-1}{n}\mathbb{1}_{|p_k| x |p_{k-1}|} & D_{p_k} \end{bmatrix}\]

where \[D_{p_i} = \frac{|\widetilde{p_1}|n + \sum_{p_j \in P/\{p_1, p_i\}}{|p_j|(n-1)}}{(n-|p_i|)(n-|p_1|)n} \mathbb{1}_{|p_i| x |p_i|} + \frac{1}{n-|p_i|}\mathbb{I}_{|p_i| x |p_i|}.\]

Given these block matrix forms, we can calculate effective resistance values using the expressions in Theorem 5.

References↩︎