IMFM Institute of Mathematics, Physics and Mechanics Jadranska 19, 1000 Ljubljana, Slovenia Preprint series Vol. 50 (2012), 1176 ISSN 2232-2094 ADAPTIVE IDENTIFICATION IN TORII IN TRIANGULAR GRIDS Matjaž Kovse Peter Stanet Ljubljana, April 13, 2012 cm i-H O cm CO o Ö cm CO u cu Adaptive Identification in Torii in Triangular Grids Matjaz Kovse*T Bioinformatics Group, Department of Computer Science and Interdisciplinary Center for Bioinformatics University of Leipzig, Hartelstrasse 16-18, D-04107 Leipzig, Germany matjaz.kovse@gmail.com Peter Stanet Raiffeisen Zagrebska cesta 76, SI-2000 Maribor, Slovenia peterstanet@gmail.com Mathematics Subject Classifications: 05C99, 05C70, 94B60, 94C12 CO cm Abstract Adaptive identification consists in asking the questions one after the other, allowing one to choose the next question according to the answers received so far, and CO its goal is to identify a (posible) faulty vertex in a graph. One can view adaptive identification also as a game, with the first player secretly choosing a vertex to be faulty, or no vertex at all, and the second player trying to locate the faulty vertex by asking questions of the type "is there a faulty vertex in the ball B(v) center at some vertex v?" for vertices in graph G. The goal of the first player is to maximize the number of needed queries and the goal of the second player is to minimize this number. In this paper we study adaptive identification in torii in the triangular lattice. CD 1 Introduction CD Adaptive identification was introduced by Julien Moncel in his PhD thesis [10] and studied generally in [1], where in particular it has also been studied in torii in the square lattice. *This research is supported by the ANR Project IDEA - Identifying coDes in Evolving grAphs, ANR-Q 08-EMER-007, 2009-2012. ^The author is also with the Institute of Mathematics, Physics and Mechanics, Ljubljana u In [2] it has been studied in torii in the king lattice. Adaptive identification presents a dynamic variation of the classical static variant called identifying codes, which have been introduced in [9] with a purpose of fault diagnosis in multiprocessor systems. Identifying code of a graph G is a subset of vertices C such that each vertex of G belongs to a ball centered at some member of C, and for each pair u,v of vertices, there is a ball centered at some member of C, which includes exactly one of u,v. Suppose we have a faulty vertex in a graph G, a graph with identifying code C. Then we can ask simultaneously all members of C if there is a faulty vertex in the balls center at them. From these questions the existence of identifying code C allows us to uniquely determine a faulty vertex, if it exist. After the introduction of identifying codes they have been widely studied, see [14] for a dynamic up-to-date online bibliography on identifying codes and related problems, edited by Antoine Lobstein. If for a graph G with n vertices there exist an identifying code, then the minimum size of identifying code can be bounded below by |~log2(n + 1)], see [11] for graphs attaining this bound and it can be bounded above by n — 1, see [3] for graphs attaining this bound. Hence in the worst case we need at most n — 1 questions to identify a faulty vertex using an identifying code in a graph in which an identifying code exist. The idea of adaptive identification is in asking the questions one after the other, instead of posing them simultaneously as in the case of identifying codes, and allowing one to choose the next question according to the answers received so far. One of the main features, as shown in [1] of adaptive indetification is that is can significantly reduce the number of questions. Adaptive identification can be also interpreted as a two players game, where one player choose a faulty vertex or no vertex at all, and the other player tries to identify a possible faulty vertex by asking questions as described above. In this sense adaptive identification is closely related to a Renyi-type search problem studied by Ruszinko in [13] and by Ben-Haim and coauthors in [1, 2]. Next we define an infinite graph called triangular grid. The vertex set of the triangular grid T consist of the set V = |i(1, 0) + j ^2, ; i,j E Z j and there is an edge between any two vertices at distance one. Static identifying codes and some related invariants were already studied in this lattice, see [4, 5, 6, 7, 8]. The paper is structured as follows: the next section presents all necessary definitions and introduces notations needed in what follows. Section 3 brings main results about adaptive identification in torii in the triangular lattice, namely it presents bounds and exact values for adaptive identification in torii in the triangular lattice, as well as an ^ illustrative example. o I cm 00 cm CD ■ i-H U CD CO 2 Basic definitions and notations For a connected graph G = (V, E), an integer r > 1, we denote by Br (v) the r-ball centered at v E V, where Br(v) = {x E V | d(x, v) < r} and d(x,v) denotes the geodetic distance between vertex x and vertex v. Two vertices x and y are called r-twins in G if Br (x) = Br (y). A graph is called r-twin-free if it has no pair of twin vertices. Jh U a u A code C is a nonempty subset of vertices of V, and its elements are called codewords. If x G Br (v), we say that x and v r-cover each other. If every vertex in some subset X Ç V is r-covered by at least some vertex from Y, we say that a set X is r-covered by a set Y. A code D is called an r-dominating set if Br (x) if D = 0 for every x G V .A code S r-separates two vertices x and y of V, if Br (x) if S = Br (y) f S. A code S is an r-separating set if it r-separates all pairs of distinct vertices of V. A code which is both r-dominating and r-separating, is called an r-identifying code. If all r-balls centered at vertices of a code C are pairwise disjoint, C is called an r-packing. A code which is both ^ an r-covering code and an r-packing is called an r-perfect code. Fundamental observation about r-identifying codes is that, for a given graph G and an integer r > 1, there exists an r-identifying code if and only if G is r-twin-free. Then we also say that G is r-identifiable graph. For an r-identifiable graph G let ir (G) denote the minimum cardinality of an r-identifying code of G. Let cr (G) (resp. Yr (G)) denote the maximum cardinality (resp. the minimum cardinality) of an r-packing of graph G (resp. of an r-covering code in graph G). Denote by a(r, 1 and let G be an r-regular r-identifiable graph. Then we have Cr(G) - 1 + [/og2(vr(G) + 1)] < a(G) < Yr(G) - 1 + dr(G). CO 3 Bounds and exact values for adaptive identification in torii in triangular grid Given two integers p and q, the p x q torus in the triangular lattice, denoted by Tpq, is the graph having vertex set V = {(i,j);0 < i < p - 1, 0 < j < q - 1} and edge set E = {{(i,j), (i,j + 1)}, {(i,j), (i + 1,j)}, {(i,j), (i + 1,j + 1)};0 < i < p - 1, 0 < j < q - 1}}, with sums on the first coordinate carried modulo p, and sums on the second coordinate carried modulo q. In triangular grid 1-ball has cardinality 7, see Fig. 1. While r-ball in triangular grid has a shape of hexagon. In this hexagon we have 2r + 1 rows. The cardinality of the middle row is 2r + 1, continuing above and below, every next row has cardinality which is CD CD CO a one less then the cardinality of the preceding row, see Fig. 2 for r = 3. The last row has cardinality r + 1. Hence we get the following calculation for the cardinality of an r-ball in a triangular grid: 2 r vr (TPq) = 2 -J] i + (2r + 1) = 2 ■ i / 2r(2r + 1) r(r + 1) i=r+1 2 2 + 2r + 1 = 3r2 + 3r + 1. U a vD in o Figure 1: 1-ball in Tp p,q- o I 00 ^ CO CO Figure 2: 3-ball in Tp,q consists of 7 rows m CD $H CD m u a CD U If p and q are both divisible by 3r2 + 3r + 1, then there exist a perfect code in a graph Tpq. Graph Tpq has p x q vertices. If p and q are both divisible by 3r2 + 3r + 1, then also the number p x q is divisible by 3r2 + 3r + 1. It follows that Tp q contains pairwise disjoint r-balls. In this case we have cr (Tp q) = Yr (Tp q). Theorem 2. Let p, q > 7 an let both p and q be divisible by 7, and let Tp,q be a p x q torus in the triangular lattice. Then pq a1(Tp,q) = y + 2. CM i-H o CM CO u a vD in o cm i CO cm cm CO m CD Figure 3: 1-perfect code in T7,7 Proof. Since p and q are both divisible by 7, there exist a 1-perfect code in Tpq. There are altogether Pq pairwise disjoint r-balls. To identify an r-ball with the faulty vertex, if the faulty vertex exist, we need at most Pq — 1 queries. Because if for the first Pq — 1 queries about whether there is a faulty vertex in a particular r-ball we receive answer NO, we continue with queries in the last ball. Suppose the faulty vertex, if it exists, is in the ball B^x,y). We can always identify it with 3 queries as follows: Question 1: Is there a faulty vertex in B^x — 1,y — 1)? YES, question 2: Is there a faulty vertex in B^x — 1,y — 2)? YES, question 3: Is there a faulty vertex in Bi(x — 2,y — 1)? YES, the faulty vertex is (x — 1, y — 1). NO, the faulty vertex is (x,y — 1). NO, question 3: Is there a faulty vertex in B1(x — 2,y)? YES, the faulty vertex is (x — 1,y). NO, the faulty vertex is (x,y). NO, question 2: Is there a faulty vertex in B1(x + 1, y + 2)? YES, question 3: Is there a faulty vertex in B1(x,y + 2)? YES, the faulty vertex is (x,y + 1). NO, the faulty vertex is (x + 1, y + 1). NO, question 3: Is there a faulty vertex in B1(x + 2,y)? YES, the faulty vertex is (x + 1,y). NO, there is no faulty vertex in the graph. □ CD For a Tp,q, a p x q torus in the triangular lattice, let us denote by Qr(x,y) question, whether r-ball Br (x, y) (the r-ball centered in the vertex with coordinates (x, y)) contains a faulty vertex, and with AQr (x) the answer to this question. Lemma 3. Let r > 1, p, q > 3 and let Tp,q be a p x q torus in the triangular lattice. Then u a we have Rog2(3r2 + 3r + 2)] < dr(TM) < 2f/og2(r + 1)] + 3. o Proof. For the lower bound we have 3r2 + 3r + 1 different choices for a faulty vertex if there exists one, hence the bound follows from the general lower bound for a dichotomic 00 search in a set of cardinality 3r2 + 3r + 1. Suppose the faulty vertex belongs to the ball Br (x,y). Let us start with a question Qr(x — r, y — r). If AQr(x — r, y — r) = YES, then we have to consider vertices that belong to a subgraph, which is of a rhombic shape and consists of (r + 1) x (r + 1) vertices. To identify a faulty vertex in this rhomb we need at most 2f/og2(r + 1)] questions. If AQr (x — r, y — r) = NO, then as a second question we choose Qr (x + r, y + r). If the answer to the second question is YES, then again we have to consider vertices that belong to a subgraph, which is of a rhombic shape and consists of (r +1) x (r +1) vertices, and we need at most 2f/og2(r + 1)] questions. We have already used two additional questions, which altogether brings 2f/og2(r + 1)] +2 questions. If AQr(x + r, y + r) = NO, two subgraphs of a shape of an equilateral triangle remain, where sides in both triangles consist of r — 1 vertices. With the third question we decide which of both triangles contains a faulty vertex. We can consider the triangle then as a rhomb with side r — 1, for which we need at most 2f/og2(r — 1)] questions to identify a faulty vertex. If the answer to the third question is NO, we cannot know whether the exist a faulty vertex in the remaining triangle, but this makes us no problem. In the last row we have only one vertex and we can check with one question whether it is faulty. Altogether we need 2f/og2(r — 1)] +3 questions, which is less then the claimed upper bound from the theorem. □ 00 cm 2 The next two lemmata will be useful to determine how much the lower and the upper bound from Lemma 3 can differ. Both of them can be easily proved by induction and the proofs are left to the reader. Lemma 4. For r =1 and for r = 2m — s, where 1 < s < 2m-2 and m > 2, we have |7og2(2r2 + 2r + 2)] = 2f/og2(r + 1)] + 1. Lemma 5. For r = 2m + s, where 0 < s < 2m-1 and m > 2, we have (2f/o^(r + 1)] +1) — f/o^(2r2 + 2r + 2)] e {0,1}. From Lemma 4 and Lemma 5 and since f/og2(2r2 + 2r + 2)] < f/og2(3r2 + 3r + 2)] and (2f/o^(r + 1)] +3) — (2f/o^(r + 1)] + 1) = 2, it follows (2f/o^(r + 1)] +3) — f/o^(3r2 + 3r + 2)] e {0,1, 2, 3}. CO Example 6. For r = 2 the lower bound equals f/og220] = 5, and the upper bound equals 2f/og23] +3 = 7. Suppose the faulty vertex, if it exists, belong to B2(x,y). Suppose AQ2(x — 2,y — 2)=NO and AQ2(x + 2,y + 2)=YES. From this it follows that a faulty a vertex belongs to 3 x 3 rhombus, which consist of nine vertices. Since f/og29] = 4, we need at most 4 queries to identify a faulty vertex in the rhombus. Altogether this means 6 CM i-H o CM CO u a vD in 0 o cm 1 cm CO cm cm £ CO CO m CD $H CD m u a CD U rhombus2 rhombus Figure 4: 5-ball in Tpq consist of two 6 x 6 rhombi and two equilateral triangles with sides of length 4. queries, which means that the lower bound cannot be reached. But, from Q2(x —2, y— 2) = NO, we can deduce that a vertex (x,y) is not faulty. Vertex (x,y) is contained in the 3 x 3 rhombus, which is determined by the second question and we need to inquire only 8 vertices, which can be done with at most three questions, since log28 = 3. Let us now consider inquiry of B2(x,y) with five questions, which is the lower bound for r = 2. Question 1: Is there a faulty vertex in B2(x — 2, y — 2)? YES, question 2: Is there a faulty vertex in B2(x — 3, y — 3)? YES, question 3: Is there a faulty vertex in B2(x — 1,y + 1)? YES, question 4: Is there a faulty vertex in B2(x + 1, y — 1)? YES, the faulty vertex is (x — 1,y — 1). NO, the faulty vertex is (x — 2, y — 1). YES, question 4: Is there a faulty vertex in B2(x + 1, y — 2)? YES, the faulty vertex is (x — 1,y — 2). NO, the faulty vertex is (x — 2, y — 2). NO, question 3: Is there a faulty vertex in B2(x,y + 2)? YES, question 4: Is there a faulty vertex in B2(x — 1, y + 2)? YES, question 5: Is there a faulty vertex in B2(x + 1,y)? YES, the faulty vertex is (x — 1,y). u NO, the faulty vertex is (x — 2,y). NO, the faulty vertex is (x,y). NO, question 4: Is there a faulty vertex in B2(x,y + 1)? YES, the faulty vertex is (x,y — 1). NO, the faulty vertex is (x, y — 2). NO, question 2: Is there a faulty vertex in B2(x + 2, y + 2)? YES, question 3: Is there a faulty vertex in B2(x + 3, y + 3)? YES, question 4: Is there a faulty vertex in B2(x + 1, y — 1)? YES, question 5: Is there a faulty vertex in B2(x — 1, y + 1)? YES, the faulty vertex is (x + 1, y +1). NO, the faulty vertex is (x + 2,y + 1). NO, question 5: Is there a faulty vertex in B2(x — 1, y + 2)? YES, the faulty vertex is (x + 1, y + 2). NO, the faulty vertex is (x + 2,y + 2). NO, question 4: Is there a faulty vertex in B2(x + 1, y — 2)? YES, question 5: Is there a faulty vertex in B2(x — 1,y)? YES, the faulty vertex is (x + 1, y). NO, the faulty vertex is (x + 2,y). NO, question 5: Is there a faulty vertex in B2(x,y — 1)? YES, the faulty vertex is (x, y + 1). NO, the faulty vertex is (x, y + 2). NO, question 3: Is there a faulty vertex in B2(x + 1, y — 1)? YES, the faulty vertex is (x + 1, y — 1). NO, question 4: Is there a faulty vertex in B2(x — 1, y + 1)? YES, the faulty vertex is (x — 1,y + 1). NO, there is no faulty vertex in the graph. o I cm 00 cm Figure 5: 2-ball in Tpq, which contains two rhombi of size 3 x 3. The central vertex (x,y) is contained in both rhombi. Theorem 7. Le p and q be divisible by 3r2 + 3r + 1 and let Tp,q be a p x q torus in the triangular lattice. Then we have £ 3r2 +Pqr + 1 — 1 + Rog2(3r2 + 3r + 2)1 < ar(TP, q) < ^ +pjr + 1 + ^(r + 1)] + 2. Oh Proof. Since both p and q are divisible by 3r2 + 3r + 1, there exist a r-perfect code in Tp,q, which means cr (Tp,q) = Yr (Tp,q). Thus there are 3r2+qr+1 pairwise disjoint r-balls in Tp,q, which cover all the vertices. Hence to identify r-ball with the faulty vertex, if such a vertex exists, we need at most 3r2+p3r+1 — 1 questions. Since if the first 3r2+lr+1 — 1 questions receive a NO answer, then we continue with queries in the remaining r-ball. The proof follows from Lemma 3 and Theorem 1. □ U a o co CO So far we have considered only cases where there might be at most one faulty vertex. In what follows we take a look at cases where there might be at most two faulty vertices. Theorem 8. Let p, q > 14 and let p and q be both divisible by 7. Then we have a(1,<2)(Tp,q) < y + 7- Proof. Since p and q are divisible by 7, there exist a 1-perfect code in Tp,q, where we have Pq pairwise disjoint 1-balls covering al the vertices in a graph. Hence we need at most pq queries to identify the ball with faulty vertices.The following situations might occur: (1) Answers to all questions are NO. Then we know that in Tp,qthere is no faulty vertex. (2) One of the questions receives a YES answer. A 1-ball in Tp,q consist of seven vertices, hence we can check for each of them if there is faulty vertex or not, no matter if there is only one or there are two faulty vertices, bringing all together at most 7 additional CM questions. (3) Two questions receive a YES answer. Then we know that both of this 1-balls contain exactly one faulty vertex. To determine a faulty vertex in any of those 1-balls we then need at most 3 questions, which brings altogether 6 questions. Also when these 1-balls are adjacent, there is no problem, since we can identify a faulty vertex in one ball without a question which covers some vertex from the other ball. □ Returning to (2) from the previous proof. Suppose we have have one or two faulty vertices in the 1-ball B1(x, y) and let us start with Q1(x — 1, y — 1). If AQ1(x — 1, y — 1) = NO, then we need at most three additional questions. If AQ1(x — 1,y — 1) = YES, we continue with Q1(x + 1, y + 2). If AQ1(x + 1, y + 2) = YES, we need one more additional question to determine whether a faulty vertex is (x,y +1) or (x + 1,y +1). And we need two additional questions to determine which of the vertices (x — 1, y — 1), (x — 1, y), (x, y — 1) and (x, y) are faulty. Altogether this means 5 questions. If AQ1(x + 1, y + 2) = NO, we continue with Q1(x + 2,y). If AQ1(x + 2,y) = YES, then one of the two faulty vertices is identified. The second faulty vertex can then be determined as in the first example. Altogether this means 5 questions. If AQ1(x + 2,y) = NO, we have to check the following vertices (x — 1,y — 1), (x — 1,y), (x,y — 1) and (x,y). In this case we don't know whether we have one or two faulty vertices. Hence we need 3 additional questions. Altogether this means 7 questions. This is the only case where we achieve the upper bound pq + 7. 7 Remark 9. For I > 3 a graph Tpq is not (r, < ^-identifiable graph, see Fig. 6. CM i-H o CM CO u a < vO IN Figure 6: Suppose that in Tp,q there are at most 3 faulty vertices and suppose that vertices with coordinates (x,y — 1) and (x,y + 1) are already known to be faulty. In this case there is no question which would determine whether a vertex (x, y) is a faulty vertex or 0 Ö o CM 1 CM CO CM CM £ CO CO CO CD $H CD CO u a CD U Acknowledgements This work is also a part of bachelor thesis [12] of the first author, which was done under the guidance of the first author. References [1] Y. Ben-Haim, S. Gravier, A. Lobstein, J. Moncel, Adaptive Identification in Graphs, Journal of Combinatorial Theory Series A 115 (2008), 1114-1126. [2] Y. Ben-Haim, S. Gravier, A. Lobstein, J. Moncel, Adaptive Identification in Torii in the King Lattice, Electron. J. Combin. 18 (2011), # P116. [3] F. Foucaud, E. Guerrini, M. Kovse, R. Naserasr, A. Parreau, P. Valicov, Extremal graphs for the identifying code problem, European J. Combin. 32 (2011), 628-638. [4] I. Honkala, An optimal edge-robust identifying code in the triangular lattice, Ann. Comb. 8 (2004), 303-323. [5] I. Honkala, An optimal locating-dominating set in the infinite triangular grid, Discrete Math. 306 (2006), no. 21, 2670-2681. [6] I. Honkala, An optimal strongly identifying code in the infinite triangular grid, Electron. J. Combin. 17 (2010), # P91. [7] I. Honkala, T. Laihonen, Tero On identification in the triangular grid, J. Combin. Theory Ser. B 91 (2004), no. 1, 67-86. [8] I. Honkala, T. Laihonen, On identifying codes in the triangular and square grids, SIAM J. Comput. 33 (2004), 304-312 [9] M. G. Karpovsky, K. Chakrabarty, L. B. Levitin, On a New Class of Codes for Identifying Vertices in Graphs, IEEE Transactions on Information Theory 44 (1998), 599-611. x i-H O 00 u a vD in 0 G & O 1 00 CO co CO CD Jh CD CO $H a CD Jh 10] J. Moncel, Codes identifiants dans les graphes, Ph.D. dissertation, Universit Joseph Fourier, Grenoble, 2005 (in French). 11] J. Moncel, On graphs on n vertices having an identifying code of cardinality |~log2(n+ 1)1, Discrete Appl. Math. 154 (2006), 203-2039. 12] P. Stanet, Adaptivna identifikacija v grafih, bachelor thesis, University of Maribor, Maribor, 2011 (in Slovenian). 13] M. Ruszinko, On a 2-dimensional search problem, Journal of Statistical Planning and Inference, 37 (1993), 371-383. 14] Online bibliography on Antoine Lobsteins webpage : http://www.infres.enst.fr/ ~lobstein/bibLOCDOMetID.html