Feda Almuhisen
email: feda.almuhisen@univ-amu.fr

Nicolas Durand
email: nicolas.durand@univ-amu.fr

Mohamed Quafafou
email: mohamed.quafafou@univ-amu.fr

Sequential Formal Concepts over Time for Trajectory Analysis

Keywords: Sequential patterns, Concept lattice, Spatiotemporal data, Trajectories, Visualisation

Tracking technologies and location-acquisition have led to the increase of the availability of trajectory data. Many efforts are devoted to develop methods for mining and analysing trajectories due to its importance in lots of applications such as traffic control, urban planning etc. In this paper, we present a new trajectory analysis and visualisation framework for massive movement data. This framework leverages formal concepts, sequential patterns, emerging patterns, and analyses the evolution of mobility patterns through time. Tagged city maps are generated to display the resulting evolution analysis and directions at different spatio-temporal granularity values. Experiments on real-world dataset show the relevance of the proposition and the usefulness of the resulting tagged city maps.

I. INTRODUCTION

With the maturity of positioning and tracking technologies in cities, global positioning system (GPS) sensors have been deployed to collect citizen's movement, where these movements represent the moving objects spatio-temporal sequences records. Analysing and visualising such information is very important to understand the users behaviours. Moreover, visualising the direction of movements in geographical space gives more detailed analysis. For example, direction describes how moving objects redistribute when passing through an intersection node in a traffic network. This analysis plays a major role in smart city applications such as human mobility understanding, vehicle and pedestrian traffic control, smart transportation, and urban planning [START_REF] Pan | Trace analysis and mining for smart cities: Issues, methods, and applications[END_REF] [START_REF] Lin | Mining GPS data for mobility patterns: A survey[END_REF]. Our research work aims at finding a solution for mining and analysing movement data. Trajectory T rj can be defined as a sequence of geographical points returned at specific time stamp t [START_REF] Zheng | Trajectory data mining: An overview[END_REF] [START_REF] Zheng | Computing with spatial trajectories[END_REF]. Each T rj contains a set of points {p 1 , p 2 , ..., p k-1 , p ki } in which each point p k ∈ T rj is defined in a three-dimensional space, i.e., p k = (longitude p k , latitude p k , t p k ).

Sequential pattern mining technique [START_REF] Fournier-Viger | A survey of sequential pattern mining[END_REF] is one of the mining tools applied to trajectories. It helps in discovering important sequential ordering patterns and relationships between events and elements in the dataset. Most of the proposed approaches are based on two steps: Sequence transformation and pattern mining. In the first step, trajectories are transformed into sequences where each element of a sequence can represent either grid ID [START_REF] Giannotti | Trajectory pattern mining[END_REF], line segment [START_REF] Cao | Mining frequent spatiotemporal sequential patterns[END_REF], or cluster [START_REF] Ye | Mining individual life pattern based on location history[END_REF]. While the second step focuses on how to mine patterns in the set of generated sequences. A large amount of effort has been devoted to mining patterns with a closeness constraint, which significantly reduces the size of the output. Examples of such algorithms are CloSpan [START_REF] Yan | Clospan: Mining closed sequential patterns in large datasets[END_REF] and Moving Trajectory CloSpan Algorithm (MTCloSpan Algorithm) [START_REF] Wang | Discovering closed frequent patterns in moving trajectory database[END_REF].

This paper presents a novel aspect of analysing and visualising massive movement data, where we propose a new trajectory analysis framework. Our main contribution corresponds to leveraging formal concepts [START_REF] Ganter | Formal concept analysis: Mathematical foundations[END_REF], sequential patterns [START_REF] Fournier-Viger | A survey of sequential pattern mining[END_REF], and emerging patterns [START_REF] Dong | Efficient mining of emerging patterns: Discovering trends and differences[END_REF] for the purpose of understanding the characteristics and the evolution of mobility movements patterns through time and visualising their corresponding directions. To the best of our knowledge, there is no research work based on these three notions for analysing moving objects. This work extends our previous work [START_REF] Almuhisen | Detecting behavior types of moving object trajectories[END_REF] by considering sequences and movement directions visualisation. We propose a method to build a spatial-temporal trajectory discrete representation in order to extract hidden closed sequential patterns using uniform grids. We construct the sequential concept lattice to encode the maximal correspondence between the discovered closed sequential patterns (ordered visited spatial regions) and trajectories that pass through these regions. This usage will reduce the search space to reveal the underlying movement patterns. We propose an algorithm that analyses the evolution of the discovered sequential formal concepts over time and define different evolution types (emerging, decreasing, latent, jumping, and lost). Finally, we provide a visual representation of the results in maps which are tagged by different evolution types and show their corresponding movement directions. One practical advantage of these maps is that they can be generated in different spatio-temporal level to provide a description of the movements in the city. We evaluated the proposed method using a real-world dataset composed of taxi movements in San Francisco. Let us remark that the proposed method is generic and is not limited to taxi data and a smart city context.

The rest of the paper is organised as follows. Section II gives some definitions about sequential patterns and concept lattice. The proposed method is detailed in Section III. The experimental results are presented in Section IV. Finally, we conclude in Section V.

II. PRELIMINARIES

Sequential pattern mining [START_REF] Fournier-Viger | A survey of sequential pattern mining[END_REF] is an important data mining task with a wide range of applications such as text analysis, market basket analysis, and trajectory analysis. Let I = {i 1 , ..., i k } be a set of items. A subset I ⊆ I is called an itemset. |I| denotes the number of items of I. A sequence is an ordered list of itemsets. It can be represented as s =< (I 1 )(I 2 )...(I k ) > where each I i is a subset of I and I i comes before I j if i ≤ j. The aim is to find all the frequent subsequences in a sequential database. Let S =< s 1 , ..., s n > be a list of sequences in a database. A sequence s 1 =< a 1 , . . . , a m > is a subsequence of another sequence Formal concept analysis (FCA) [START_REF] Ganter | Formal concept analysis: Mathematical foundations[END_REF] is a theory of data analysis identifying the conceptual structures within datasets. The closure properties and its capability of discovering inherent hierarchical structures give it the advantage to be used to analyse the different pattern relationships and build better mining algorithms [START_REF] Poelmans | Formal concept analysis in knowledge processing: A survey on applications[END_REF]. A formal context is composed of a set of objects O, a set of items I, and a binary relation R 1 between O and I (i.e., R 1 ⊆ O × I). While by dealing with ordered data, each object represents a sequence in S. Thus, items in each object are partially ordered through the time.

s 2 =< b 1 , . . . , b n >, denoted by (s 1 ⊆ s 2 ), if there are integers 1 ≤ i 1 ≤ i 2 ≤ • • • ≤ i m ≤ n, such as a 1 ⊆ b i1 , a 2 ⊆ b i2 , . . . ,
A sequential context (or order context) C [START_REF] Garriga | Lattice theory for sequences[END_REF] is defined as (R, O, I), where R ⊆ O × I × N. For an entry (o, i, k) ∈ R, k represents the order of occurrence of i with respect to the other attributes in the same object. Sequential context can be represented by a cross table where rows are labeled by objects and the columns are labeled by the items. The entry in row j and column i corresponds to the order of item i in the equivalent input sequence s j . Given a sequential context, there is a unique ordered set which describes the inherent lattice structure defining natural groupings and relationships among the objects and their related sequences [START_REF] Garriga | Lattice theory for sequences[END_REF]. This structure is called a sequence concept lattice. Each element of the lattice is a couple (O, S) composed of a set of sequences (the intent) and a set of objects (the extent). Each couple (called sequence formal concept) must be a complete couple with respect to R, which means that the following mappings (noted φ and ψ) hold. For O ⊆ O and S ⊆ S, we have: [START_REF] Pan | Trace analysis and mining for smart cities: Issues, methods, and applications[END_REF]

φ(O) = {s ∈ S | s is maximally contained in s i , ∀ i ∈ O} and (2) ψ(S) = {i ∈ O | s ⊆ s i , ∀ s ∈ S}. φ(O)
returns sequences common to all objects o ∈ O, while ψ(S) returns objects that have at least all sequences s ∈ S. The idea of maximally extending the sets being formalised by the mathematical notion of closure in ordered sets. φ and ψ form a Galois connection and the compositions ∆ = ψ • φ and ∆ = φ • ψ are the Galois closure operators. Let S be a set of sequences if ∆(S) = S then each sequence of S is a closed sequence. A sequence formal concept is composed of a set of closed sequences and of the set of objects containing this closed sequences. We call sequential formal concepts, the sequence of formal concepts that have at least minsup objects in their extent, and sequential concept lattice, the lattice formed using the sequential formal concepts.

III. TRAJECTORY EVOLUTION TYPES DETECTION

In this section, we present a new trajectory analysis framework based on sequential patterns, FCA, and emerging patterns. The main steps are: (1) Spatio-temporal preprocessing ; (2) Sequential concept lattice and evolution type detection ; and (3) Visualisation of geolocalised evolution type.

In step 1, trajectories are segmented by time value ∆t, labeled by time granularity value τ , and mapped on a raster area G using local georeference according to spatial granularity value α. These discretised data are then used to extract hidden sequential patterns and the corresponding evolution types in the next step. In step 2, For each time windows T (i.e., a pair of time granularity values (t i-1 , t i )), we compute the sequential concept lattice L according to the minimal support threshold value minsup. Each node of L, i.e., sequential formal concept, encodes the maximal correspondence between a set of closed sequential patterns (where each sequence contains an ordered set of grids), and the set of trajectories passing through these grids. For each sequential formal concept, we analyse the evolution of the closed sequential pattern by computing an indicative value K. By given K, minimal threshold value of emergence θ, and an error tolerance value , we detect the evolution type and the corresponding movement direction for each grid included in the closed sequential pattern. Let us remark that evolution type belongs to a predefined set: {latent, emerging, decreasing, jumping, lost}. Finally, in step 3 we automatically generate maps which are tagged by the detected evolution types.

A. Spatio-Temporal Preprocessing

Preprocessing is an important step in our framework. This step aims at simplifying and reducing the number of points processed with a negligible error for the purpose of mining trajectories. The main steps are (1) Trajectory segmentation according to time values ; (2) Mapping trajectories on a raster area according to spatial granularity value.

1) Segmenting and Labeling Trajectories: GPS data is huge in size to be analysed directly. Therefore, we perform two level of trajectory time segmentation. First step is to segment trajectories by ∆t value. ∆t is a given value that compared the time difference between two cleaned ordered GPS points. We perform this step to get an equal intervals of moving objects sequences. This value is in minutes. In the second step, we segment and label trajectories by a given time granularity τ , (can be minutes, hours, days, etc.) specified according to the type of analysis required. Each value of granularity is called a label. We note La = {l 1 , l 2 , ...., l k-1 , l k } as the set of time granularity values where l j < l j+1 for 1 ≤ j ≤ k -1. Each trajectory is segmented according to the defined labels. The trajectory of object n after segmentation by La can be defined as follow: T rj = {T rj l1 n , T rj l2 n , ..., T rj l k n }. If T rj lj n is empty then this trajectory is deleted.

2) Mapping Trajectories on a Raster Area: Location coordinates in a spatio-temporal series are real numbers, which do not repeat themselves exactly in every pattern instance [START_REF] Cao | Mining frequent spatiotemporal sequential patterns[END_REF]. We proposed to use a solution that represents the continuous movement of an object as a sequence of traversed grid cells along with its respective traversal times. To achieve this, we split the geographical region as a raster area G where grid width and height dimension has an equal size spatial granularity α in kilometers. Then, we map trajectories using local georeference technique on G. This mapping includes conversion of the geographic coordinates (latitude, longitude) values in trajectories to grid index that represents these points. For each trajectory trj we obtain G trj , the set of grids corresponding to trj traversal points. Figure 1 and Table I show an example of 4 taxi trajectories after mapping using local georeferenced system, within the corresponding time label (Day1,Day2).

B. Sequential Concept Lattice and Evolution Type Detection

Evolution type detection associated to trajectories over time windows is performed in two steps presented next.

1) Sequential Concept Lattice Computation: The computation of the sequential lattice allows to obtain the closed sequential patterns of grids (in our case here it maybe spatial zones, routes, etc.) and their corresponding sets of trajectories. The first step to compute this lattice is to create the ordered formal context C = (R, O, I) for a specified time window. O is the set of trajectories for the studied time window. I is the set of grid indexes. Then, the sequential concept lattice is computed according to the specified minimal threshold value minsup. For example, Table I represents a sequence dataset of 4 taxis trajectories. Each trajectory has been segmented by ∆t, and labeled by the corresponding time granularity value (see Table II). Some sequential formal concepts computed with minsup = 2 are presented in Table III.

2) Detection of Evolution Types: We detect the evolution type of each sequence in sequential concept lattice by studying Let F C = (O, S) be a sequential formal concept, θ be the minimal threshold value of emergence, and be the error tolerance. The evolution type of each sequence contained in S is detected by computing K i as follow:

K i (O, S) = count(O, t i ) count(O, t i-1 )
Where count(O, t j ) is the number of trajectories of O labeled by the corresponding t j . We apply the following rules based on III presents some results of computing K i and the detected evolution types from the sequential dataset presented in Table II.

K i value. If K i (O, S) = 0 ± , then the type of S is lost. If ((K i (O, S) > θ) ∧ (θ = 1)) ∨ ((K i (O, S) ≥ θ) ∧ (θ > 1))) then the type of S is emerging. If K i (O, S) < θ, then the type of S is decreasing. If K i (O, S) = 1 ± , then the type of S is latent. If K i (O, S) = +∞, then the type of S is jumping. Table

C. Visualisation

In this step, we present two methods for visualising the detected evolution types in tagged city maps. The first method generates maps tagged by different colors, whereas each color represents a given evolution type. The second method is to represent the results using colors and arrows, where arrows represent the flow directions (North, South, East, etc.) and the color of the arrow represents the corresponding type detected. This representation is important because trajectories of moving objects are directed by nature. Therefore, the direction information is highly relevant and important to display in interactive visualisation systems to provide a fine analysis. Given a sequential concept lattice and the corresponding type values. For each sequence in the intents, we extract the real coordinates of the ordered grids. Each detected type is assigned to a specific color. Hence, when reading the grid index and the type, the color is given to the mapped grid area in the real map. The type of each grid item is chosen according to the majority vote value, which is computed by considering all the sequential formal concepts that contain this grid in its intent. The second method is a variant of the previous method where we detect the direction of a grid in a sequence. For that, we consider the real coordinates of the grid and of the next grid in the sequence. Let us note that if there is no next grid, there is no detected direction. The type of each direction (or none) for a grid item is chosen according to the majority vote value, which is computed by considering all the sequential formal concepts that contain this grid with this direction in its intent.

IV. EXPERIMENTS

A. Data and Protocol

We analysed the data collected from the CRAWDAD website [START_REF] Piorkowski | CRAWDAD dataset epfl/mobility (v. 2009-02-24)[END_REF]. This dataset consists of a 500 taxis trajectories in San Francisco which was collected during the period from 17 May 2008 to 10 June 2008 (24 days). We selected 455 taxis during 23 days. Several experiments were performed by varying time granularity τ (24, 12, 6 hours), spatial granularity α (20, 40, 60 meters), and minsup (0.03, 0.05, 0.07). We set ∆t to 60 minutes, to 0 and θ to 1. Let us note that the chosen ∆t value does not segment again the data. We also conducted a comparative study between the results obtained from sequential concept lattice (noted here as "sequences") with directions or without, and the ones obtained from frequent concept lattice (noted here as "itemsets"). We calculated the similarity between the results by using Jaccard measure (Sim(A, B) = |A∩B| |A∪B| ). The intersection of two results A and B is the set of grids having the same detected type in the two results A and B. In the case of using directions, if the type of a grid corresponds to the type of one direction or more, then the result is considered as the same. The more the value is closer to 1, the more the compared results are similar. All the algorithms were implemented in Java, and all the experiments were performed on an Intel Xeon X5560 2.8GHz with 16GB of memory.

B. Results

Table IV presents the characteristics of the computed sequential datasets. In the tables, May17 corresponds to Saturday (Armed Forces Day), May18 to Sunday, . . . , May26 to Monday (Memorial Day). The types are: LA (latent), E (emerging), D (decreasing), J (jumping), and LO (lost).

1) Quantitative Results: Tables V, VIII, and VII show part of statistical analysis for the results obtained from using different spatial granularities 20, 40, 60 meters respectively (minsup = 0.05 and time granularity = one day). We can observe that the total number of patterns increases whenever we have a high spatial granularity value. Thus, if the spatial granularity value increases, the total number of grids decreases and the data density increases. Consequently, there are more possible common grids between the trajectories, so the probability to find a sequential formal concept increases. We can conclude that there is a relation between spatial granularity and the total number of generated sequential formal concepts. Moreover, we observe that the number of lost and jumping types are low compared to those of the other types. This is due to the time granularity which is coarse and does not allow to capture fast evolution. A set of patterns is lost or jumping if it is not detected during both the two compared time windows. We have also applied the same protocol by changing time granularity value. Instead of using 24 hours, we have set the time granularity value to 12 hours and 6 hours, while keeping spatial granularity value of 60 meters and minsup value as 0.05. Tables VI and IX show the statistical results for 12 hours and 6 hours, respectively for May17, May18, and May19. If we compare these statistics with the ones in Table VII, we can conclude that whenever we decrease the time granularity we get less total number of sequential formal concepts. For example, in time window (May18,May19) Table VII, the total number of sequential formal concepts is equal to 156,138 while for the same period of time on Table VI it is equal to 12,502 and to 3,597 in Table IX. The decreasing of the number of sequential concept lattice occurs because the data density is lower. Finally, we have applied the protocol by changing the minsup value, for the same spatial granularity and time as presented in Tables VII, X and XI. We note from these results that whenever the minsup value increases the number of generated sequential formal concepts decreases, and some evolution types may disappear. For example, if we compare the results in Table X with those in Table XI, we can notice that with minsup=0.07 we have no jumping or lost types.

2) Qualitative Results: Emerging sequential formal concepts have been captured in the Mission District area (see Figure 2) during the period of (May24, May25). This indicates that those regions face a higher taxi movement on the second day compared to the first day. This results can be clarified by the fact that these days are part of Memorial Day weekend. In fact, there was a parade in May25 morning which runs along Mission Street for three hours or more. For that reason traffic in May25 was higher in this area compared to May24. Figure 4 shows a decreasing evolution type in the crossroad of Townsend street and 7th street, within a majority of emerging direction flow to North East and North West, while a majority of decreasing to South East. This precise information gives a detailed analysis compared to the decreasing type without direction captured in Figure 3. This example is typic and shows that the proposed visualisation method using evolution type with directions provides a more fine analysis of movements, a precise description for each region in the city, and a better understanding of traffic flow at street levels.

3) Comparative Results: Table XII presents the similarity values obtained from comparing (1) Itemsets and sequences without direction, Sim(it,seqnod) ; (2) Itemsets and sequences with direction, Sim(it,seqd) ; (3) Sequences with direction and without direction, Sim(seqnod,seqd). The purpose of this comparison is to examine if our extension to direction and the use of majority voting affects the obtained results. As we can see, Sim(seqnod,seqd) has the maximum value among all the other. Hence the results obtained from sequential concept lattice with direction covered the results without direction. Furthermore, this validates that the extension to directions provides more details to the model without affecting the final results. Additionally, we can conclude that the results obtained from our proposed method do not vary a lot from the results obtained from frequent concept lattice, which prove the correctness of both methods. In order to study the effect of different parameters in our framework, we have used different parameter values (see Exp. No. in Table IV). We can observe the following relation, spatial and temporal granularities and minsup values do not affect the comparative results. The proposed method is robust. We always have high similarity values between the two results. Experiments on real-world data have shown the applicability of the proposed method and its relevance. Moreover, we have shown that the use of sequential patterns compared to frequent itemsets provides more precise analysis with the direction information. In future work, we will extend our system to build a probabilistic model to predict the pattern evolution during the next time window.

Fig. 1 :

 1 Fig. 1: Example of trajectory mapping.

Fig. 2 :

 2 Fig. 2: Tagged map for Mission District (May24,May25).

Fig. 3 :

 3 Fig. 3: Tagged map for Townsend street without direction.

Fig. 4 :

 4 Fig. 4: Tagged map for Townsend street with direction.

  and a m ⊆ b im . s 2 is called a supersequence of s 1 (s 2 contains s 1 ). The support of a sequence s n , noted support(s), is the number of occurrences of s n in S. A sequence s is said to be a sequential pattern (also called a frequent sequence) if support(s) ≥ minsup, where minsup is the minimal support threshold value set by the user. A sequential pattern s 1 is closed if s 2 with s 1 ⊂ s 2 and support(s 1 ) = support(s 2 ). Closed sequential patterns are interesting for us because they represent the largest frequent subsequences common to sets of sequences.

TABLE I :

 I Example of taxis data represented by their grid sequences and corresponding time labels

	trajseq-Id	Sequence	label
	T axi1

< (13)(17)(21)(25)(26)(27)(28)(24) > < (20)(16)(15) > < (19)(23)(22)(18) > < (14)(10)(6) > < (5)(9)(13)(17) > Day1 T axi2 < (9)(10)(11)(15) >< (19)(23)(22)(26) > Day1 T axi3 < (20) (16) > < (15) (11) (10) (9) (13) > < (14) (15) (19) (23) (27) > Day2 T axi4 < (5) (6) (7) (11) (15) > < (14) (13) (9) (10) > Day2

TABLE II :

 II Trajectory data sequences in different days represented by grids

	seq-Id	Sequence	label
	s 1	< (13)(17)(21)(25)(26)(27)(28)(24)>	Day1
	s 2	<(20)(16)(15) >	Day1
	s 3	<(19)(23)(22)(18)>	Day1
	s 4	< (14)(10)(6) >	Day1
	s 5	<(5)(9)(13)(17)>	Day1
	s 6	< (9)(10)(11)(15) >	Day1
	s 7	<(19)(23)(22)(26)>	Day1
	s 8	< (20)(16) >	Day2
	s 9	< (15)(11)(10)(9)(13) >	Day2
	s 10	< (14)(15)(19)(23)(27)>	Day2
	s 11

< (5)(6)(7)(11)(15)> Day2 s 12 < (14)(13)(9)(10) > Day2

the support variation through a pair of time windows (t i-1 ,t i ).

Let us remark that the evolution type belongs to a predefined set of labels: {latent, emerging, decreasing, jumping, lost}. Emerging label means that the presence of the pattern increased in t i compared to t i-1 ; Decreasing means that the presence of the pattern decreased in t i compared to t i-1 ; Latent means that the presence of the pattern is quite similar in both time. Jumping means the pattern which was absent in t i-1 , appeared in t i . Lost means that the pattern disappeared in t i .

TABLE III :

 III Some sequential formal concepts and their types obtained with minsup = 2, θ = 1, = 0

	Extent	Intent	day1	day2	K	Evolution type
	{s 2 , s 6 , s 9 , s 10 , s 11 }	{< (15) >}	2	3	1.5	emerging
	{s 2 , s 8 }	{< (20)(16) >}	1	1	1	latent
	{s 3 , s 7 }	{< (19)(23)(22) >}	2	0	0	lost
	{s 3 , s 7 , s 10 }	{< (19)(23) >}	2	1	0.5	decreasing

TABLE IV :

 IV Computed sequential datasets

TABLE V :

 V Number of sequential formal concepts α = 0.02 km, τ = 24 h, minsup = 0.05

	Time windows	#E	#D	#LA	#LO	#J	Total
	(May17,May18)	1,390	35	3	0	0	1,428
	(May18,May19)	751	1,854	71	0	0	2,676
	(May19,May20)	760	1,075	78	0	0	1,913
	(May20,May21)	905	825	86	0	0	1,816
	(May21,May22)	1,300	727	110	0	0	2,137
	(May22,May23)	1,434	938	132	0	0	2,504
	(May23,May24)	1,157	1,273	107	0	0	2,537
	(May24,May25)	1,430	1,197	131	0	0	2,758
	(May25,May26)	1,548	864	100	0	0	2,512

TABLE VI :

 VI Number of sequential formal concepts α = 0.06 km, τ = 12 h, minsup=0.05

	Time windows	#E	#D	#LA	#LO	#J	Total
	May17(am),May17(pm)	856	1	0	0	137	994
	May17(pm),May18(am)	4,600	1,384	85	0	1	6,070
	May18(am),May18(pm)	1,376	4,945	126	0	0	6,447
	May18(pm),May19(am)	1,483	1,817	105	0	0	3,405
	May19(am),May19(pm)	1,306	1,291	53	0	0	2,650

TABLE VII :

 VII Number of sequential formal concepts α = 0.06 km, τ = 24 h, minsup = 0.05

	Time windows	#E	#D	#LA	#LO	#J	Total
	(May17,May18)	53,956	271	55	0	35	54,317
	(May18,May19)	29,644	122,901	3,593	0	0	156,138
	(May19,May20)	26,263	48,478	3,524	0	0	78,265
	(May20,May21)	32,515	30,648	3,517	0	0	66,680
	(May21,May22)	53,050	25,736	4,010	0	0	82,796
	(May22,May23)	75,987	33,585	5,753	0	0	115,325
	(May23,May24)	69,702	62,714	6,175	0	0	138,591
	(May24,May25)	115,022	65,441	8,935	0	0	189,398
	(May25,May26)	114,786	50,599	6,551	0	0	171,936

TABLE VIII :

 VIII Number of sequential formal concepts α = 0.04 km, τ = 24 h, minsup = 0.05

	Time windows	#E	#D	#LA	#LO	#J	Total
	(May17,May18)	9,817	125	19	0	2	9,963
	(May18,May19)	5,046	19,738	606	0	0	25,390
	(May19,May20)	5,258	7,991	642	0	0	13,891
	(May20,May21)	5,827	5,956	644	0	0	12,427
	(May21,May22)	10,287	4,548	688	0	0	15,523
	(May22,May23)	12,031	7,247	1,044	0	0	20,322
	(May23,May24)	11,031	10,674	1,026	0	0	22,731
	(May24,May25)	16,952	11,299	1,424	0	0	29,675
	(May25,May26)	16,847	8,016	954	0	0	25,817

TABLE X :

 X Number of sequential formal concepts α = 0.06 km, τ = 24 h, minsup = 0.03

	Time windows	#E	#D	#LA	#LO	#J	Total
	(May17,May18)	320,457	2,097	508	0	3998	327,060
	(May18,May19)	187,308	748,810	31,919	44	0	968,081
	(May19,May20)	152,627	272,393	25,594	1	0	450,615
	(May20,May21)	176,022	171,445	23,406	0	0	370,873
	(May21,May22)	288,536	150,320	28,110	0	0	466,966
	(May22,May23)	404,990		42,724	0	0	644,291
	(May23,May24)	397,210	353,401	48,511	0	0	799,122
	(May24,May25)	728,667	421,345	71,019	0	0	1,221,031
	(May25,May26)	714,969	359,008	58,396	0	0	1,132,373

TABLE XI :

 XI Number of sequential formal concepts α = 0.06 km, τ = 24 h, minsup = 0.07

	Time windows	#E	#D	#LA	#LO	#J	Total
	(May17,May18)	16,049	73	10	0	1	16,133
	(May18,May19)	8,894	36,883	836	0	0	46,613
	(May19,May20)	8,041	15,140	914	0	0	24,095
	(May20,May21)	10,395	9,708	940	0	0	21,043
	(May21,May22)	15,934	7,434	1,061	0	0	24,429
	(May22,May23)	24,270	9,969	1,594	0	0	35,833
	(May23,May24)	21,702	19,544	1,560	0	0	42,806
	(May24,May25)	34,439	19,396	2,205	0	0	56,040
	(May25,May26)	36,879	14,508	1,831	0	0	53,218

TABLE XII :

 XII Comparative study between itemsets and sequences experiments

	Exp. No.	Sim(it,seqnod)	Sim(it,seqd)	Sim(seqnod,seqd)
	1	0.8875	0.9040	0.9467
	2	0.8147	0.8530	0.8755
	3	0.8232	0.8515	0.8813
	4	0.8802	0.8896	0.9387
	5	0.8515	0.8550	0.9837
	7	0.8274	0.8564	0.8943
	Average	0.8474	0.8682	0.9200

evolution of patterns through time, and to visualise the results in tagged city maps at different spatio-temporal granularities.


Asmae El Beqal

Loubna Kritele

Bachir Benhala

Nature-inspired algorithms for optimal active band pass Filter design

come

The basic purpose in active filters design is to calculate the filter transfer function in order to find the adequate discrete components values (Resistors and Capacitors) forming those filters, which providing the best performances. The selection of the components values must be from industrial series so as to reduce costs and make the design more feasible, then, the search for an optimal set of component values from the numerous possible combinations appears to be an exhaustive process, thus diverting the attention towards the application of the metaheuristics which combines high efficiency with minimal computational time.

In the literature, various metaheuristics were used for optimal design of analog circuits such as Simulated Annealing (SA) [START_REF] Dreo | Metaheuristics for hard optimization: Methods and case studies[END_REF], Tabu Search (TS) [START_REF] Glover | Tabu search-part I[END_REF], Particle Swarm Optimization (PSO) [START_REF] Chan | Swarm Intelligence: focus on ant and particle swarm optimization[END_REF], Ant Colony Optimization (ACO) [START_REF] Kritele | Ant Colony Optimization for Optimal Analog Filter Sizing[END_REF] and Genetic Algorithms (GA) [START_REF] Grimbleby | Automatic analogue circuit synthesis using genetic algorithms[END_REF].

In this paper, we propose to apply the Ant Colony Optimization (ACO) [START_REF] Kritele | Ant Colony Optimization for Optimal Analog Filter Sizing[END_REF] and the Genetic Algorithm (GA) [START_REF] Grimbleby | Automatic analogue circuit synthesis using genetic algorithms[END_REF] techniques, which are increasingly used in the domains of optimization and has been applied successfully in the field of analog circuits, for the optimal sizing of the second order active band pass filter namely Sallen Key (Figure 1), considering two objectives functions, the mid frequency and the selectivity factor.

ACO is a metaheuristic developed in order to solve difficult optimization problems. It

Q Δ 5 . 0 SK ω Δ 5 . 0 SK TE   (1)
where :

Q Q 2 R 1 R 2 1 R SK Q Δ m ω m ω RC 1 SK ω Δ      (2)
The table I presents the optimal values of resistors and capacitors forming the studied filter and the performance associated with these values following the series that gave us the best result for both algorithms, according to the result ACO algorithm achieves the smallest values of the design error.

  algorithms for optimal active band pass Filter design 1 *EL BEQAL Asmae, 1 KRITELE Loubna, 2 BENHALA Bachir & 1 ZORKANI Izeddine 1 asmae.elbekkal@gmail.com,Faculty of Sciences Dhar el Mahraz, Morroco 2 Faculty of Sciences, University of Moulay Ismail, Morroco

  has been inspired by the foraging behavior of real ant colonies. Its basic idea is the indirect communication between the ants mediated by trails of chemical substance, called pheromone, which allows them to find the shortest path from their nest to the food source, while GA is a search heuristic that is inspired by Charles Darwin's theory of natural evolution. This algorithm reflects the process of natural selection where the fittest individuals are selected for reproduction in order to produce offspring of the next generation. The objective function considered is the Total Error (TE SK ) given in (1), which expresses the offset values, of the mid frequency and the selectivity factor, compared to the desired values ( m ω = 6.28 k rad/s ( m f = 1 KHz) et Q = 10). The decision variables are the resistors and capacitors forming the circuit. Each component must have a value of the IMAT3E'18 International Meeting on Advanced Technologies in Energy and Electrical Engineering standard series (E12, E24, E48, E96, and E192). The validity of the proposed techniques was proved via PSPICE simulations (Figure 2).

SK

Figure 1 .

 1 Figure 1. Schematic diagram of 2nd order Sallen-Key active band-pass filter

Figure 2 .

 2 Figure 2. Frequency responses of second order Sallen-Key active band-pass Filter In this work, we have successfully selected the values of discrete components from different manufactured series for the optimal sizing of the second order Sallen-Key active band-pass filter, the topology of Sallen Key can be used to design the 4th order Butterworth active band-pass filter which is used for radio frequency identification (RFID) system reader to reject all signals outside the band (10-20) kHz and to amplify the low antenna signal, that can be detailed a future work.

Table I . Values of component and related filter performance for the ACO and GA

 I

		R1 (KΩ)	R2 (KΩ)	R (KΩ)	C (nF)	𝛥ω SK	𝛥Q SK	TE SK
	ACO (E192)	25.20	48.01 45.30	3.48	0.0101	0.0544	0.0322
	AG (E96)	24.90	47.50 02.61 60.40	0.0101	0.0826	0.0464


Bartlomiej Bosek
email: bosek@tcs.uj.edu.pl

Przemyslaw Gordinowicz

Jaroslaw Grytczuk
email: j.grytczuk@mini.pw.edu.pl

JAROS LAW GRYTCZUK Nicolas Nisse
email: nicolas.nisse@inria.fr

Joanna Sokol
email: j.sokol@mini.pw.edu.pl

Malgorzata Sleszynska-Nowak

PRZEMYS LAW GORDINOWICZ Bart Lomiej Bosek

Joanna Sok Ó L

M A Lgorzata

Śleszy Ńska-Nowak

M Śleszy Ńska-Nowak

Localization game on geometric and planar graphs

come   L'archive ouverte pluridisciplinaire

Introduction

Among dozens of games studied in graph theory, the game of Cops and Robbers [START_REF] Bonato | The game of cops and robbers on graphs[END_REF] is one of the most intriguing. Two players, the cops and the robber, occupy vertices of a graph G, and move along edges to neighboring vertices or remain on their current vertex. The cops move first by occupying a set of vertices. The robber then chooses a vertex to occupy, and the players move in alternate rounds. The game is played with perfect information, so the players see each others' moves. The cops win if they can capture the robber by moving to a vertex the robber occupies; otherwise, the robber wins. The cop number of a graph G, denoted by c(G), is the minimum number of cops needed to win in G.

The game was introduced independently by Quilliot [START_REF] Quillot | Jeux et pointes xes sur les graphes[END_REF] and Nowakowski and Winkler [START_REF] Nowakowski | Vertex-to-vertex pursuit in a graph[END_REF]. Since then it gained lots of research activity resulting in many deep results, unexpected connections, and challenging open problems. Also numerous variants motivated by applications in diverse areas of mathematics and computer science have been considered (see [START_REF] Aigner | A game of cops and robbers[END_REF], [START_REF] Bonato | The game of cops and robbers on graphs[END_REF], [START_REF] Fomin | An annotated bibliography on guaranteed graph searching[END_REF], [START_REF] Seymour | Graph searching and a min-max theorem for tree-width[END_REF]).

In this paper, we study another variant inspired by localization problems in wireless networks. The recent growing popularity of mobile devices (iphones, smartphones, etc.) stimulated lots of technological invention as well as theoretical research for solutions of real-life localization tasks (see [START_REF] Bahl | RADAR: an in-building RF-based user location and tracking system[END_REF], [START_REF] Gu | A Survey of Indoor Positioning Systems for Wireless Personal Networks[END_REF], [START_REF] Olsen | How precise should localization be? A quantitative analysis of the impact of the delay and mobility on reliability of location information[END_REF]). In one of many possible approaches, a network is modeled as a graph with radio signal receivers (such as Wi-Fi access points) located at some vertices. The strength of the signal from a mobile phone is proportional to its distance to particular receivers. So, the information on the actual position of the mobile phone in the network is only partial. Moreover, the mobile phone holder may walk along the network changing his position in time. The task is to find him precisely at some point by a procedure with prescribed efficiency.

Motivated by this scenario, we consider the following metric version of the Cops and Robbers game. Let G = (V, E) be a simple connected undirected graph and let k ≥ 1 be a fixed integer. The localization game involves two Players: the Cop-player (playing with a team of k cops) and the Robber-player (the robber), and proceeds as follows. In the first turn, the robber chooses a vertex r ∈ V unknown to the Cop-player (in the localization game, the robber is a priori "invisible"). Then, at every turn, first the Cop-player picks (or probes) k vertices B = {v 1 , v 2 , . . . , v k } ∈ V k and, in return, gets the vector D(B) = (d 1 , d 2 , . . . , d k ) where d i = d G (r, v i ) is the distance (in G) from r to v i for every i = 1, 2, . . . , k. If the Cop-player can determine the position of the Robber-player from D(B) (i.e., r is uniquely defined by D(B) and the knowledge that the Cop-player has from previous turns), then the Cop-player wins. Note that r is not required to be in B. Otherwise, the Robber-player may move to a neighboring node r ∈ N [r]1 (unknown by the Cop-player) and then, during the next turn, the Cop-player can probe another set (possibly the same) of k vertices, and if the robber is not located the robber may move to a neighbor, and so on. The cops win if they can precisely locate the position (the occupied vertex) of the robber after a finite number of turns (before the possible move of the robber). The robber wins otherwise. Let ζ(G) denote the least integer k for which the cops have a winning strategy whatever be the strategy of the robber (that is, we consider the worst case when the Robber-player a priori knows the whole strategy of the Cop-player). This game restricted to k = 1 was introduced by Seager [START_REF] Seager | Locating a robber on a graph[END_REF], and studied further in [START_REF] Brandt | Locating a robber on a tree[END_REF], [START_REF] Carraher | Locating a robber on a graph via distance queries[END_REF], [START_REF] Seager | Locating a backtracking robber on a tree[END_REF]. It can be shown that, for every tree T , ζ(T ) ≤ 2 [START_REF] Seager | Locating a robber on a graph[END_REF]. Moreover, trees T for which ζ(T ) = 2 are characterized in [START_REF] Seager | Locating a backtracking robber on a tree[END_REF]. More precisely, Seager [START_REF] Seager | Locating a robber on a graph[END_REF] proved that one cop is sufficient to localize a robber on any tree when robber is not allowed to move to a vertex just checked by the cop (in the previous round). In [START_REF] Seager | Locating a backtracking robber on a tree[END_REF], she proved that this restriction is necessary for trees that contains a ternary regular tree of height 2 as a subtree.

The localization game is also connected to the notion of metric dimension2 of a graph G, denoted by dim(G), introduced independently by Harary and Melter [START_REF] Harary | On the metric dimension of a graph[END_REF], and by Slater [START_REF] Slater | Leaves of trees[END_REF]. Indeed, dim(G) can be defined as the least number k such that the Cop-player wins the localization game in one turn by cleverly choosing k vertices of G. Hence, the parameter ζ(G) can be seen as the game theoretic variant of dim(G). The localization game has also been introduced recently in [START_REF] Haslegrave | Locating a robber with multiple probes[END_REF], where it is proven that ζ(G) ≤ (∆+1) 2 4 + 1 in any graph G with maximum degree ∆.

Our main goal in this paper is to find out for which classes of graphs the number ζ(G) is bounded. Clearly, this holds for classes with bounded metric dimension by the trivial inequality ζ(G) ≤ dim(G). We are mainly interested in graph classes with bounded traditional cop number c(G). In particular we focus on graphs with various geometric representations because of their frequent applications to cellular networks, including planar graphs for which c(G) ≤ 3 as proved by Aigner and Fromme in [START_REF] Aigner | A game of cops and robbers[END_REF]. Our results. As a warm-up, we give easy results and intuitions on the localization number (Section 2). Then, we show ζ(G) ≤ k for any graph with pathwidth at most k (Section 3). Our main result is that, somewhat surprisingly, ζ(G) is unbounded in graphs obtained from any tree by adding a universal vertex (i.e., planar graphs with treewidth at most 2) (Section 4). Then, we show that deciding whether ζ(G) ≤ k is NP-complete in the class of graphs G with diameter at most 2 (Section 5). Finally, we prove boundedness of ζ(G) for some geometric graph in the plane (Section 6). In the final section (Section 7) we set several open problems for future research.

Warm-up

Let us start with determining the localization number of some simple graphs. For instance, for a path P n on n vertices, we have ζ(P n ) = 1. Indeed, the Cop-player wins in one turn by starting from one of the ends of the path, which shows that also dim(P n ) = 1. For complete graphs we have

ζ(K n ) = dim(K n ) = n -1.
On the other hand, for a star S n on n vertices, dim(S n ) = n -1, while ζ(S n ) = 1. To see this latter statement suppose that the Cop-player probes the leaves one by one. At some point the robber must be located. So, the difference between parameters ζ(G) and dim(G) can be arbitrarily large.

Determination of ζ(G) for complete bipartite graphs is slightly less immediate. Proof. Let A and B be the two partition classes of K a,b with size a and b, respectively. We can assume that a ≤ b. First we will show that ζ(K a,b ) ≤ min(a, b). In the first round the Cop-player probes all vertices of A except one, and probes one vertex of B. If the robber occupies any vertex from A, the Cop-player wins, as she gets answer 0 from one vertex from A or all answers from vertices from A are 2 in which case the robber is in the unselected vertex from A. Otherwise, in next turns, the Cop-player changes only one vertex; she still probes all vertices of A except one, and she probes a new vertex of B. If the robber stays all the time in the same of the vertices of B, the Cop-player will locate him at some round. If he moves to some vertex from A, she will also locate him. Now we will show that if the Cop-player can probe at most min(a, b) -1 vertices in each round, then the robber has a winning strategy. If the Cop-player probes all vertices from only one partition class, then the robber may choose any of vertices from the second class. If the Cop-player probes at least one vertex from B, then the robber may stay in one of the unselected vertices from A (remind that the robber fully knows the strategy of Cop since we are considering a worst case). As there are at least two such vertices the robber remains hidden. The proof is complete. Proof. The idea of the proof is the same as in case of complete bipartite graphs. This time, the cops recognize the partition class in which the robber is by parity of answers. If all answers from vertices from A are even and different from 0, then the robber is in the unselected vertex from A. Otherwise he occupies one of vertices from B and the cops will eventually locate him in some future round.

It is also worth noticing that in general parameter ζ(G) is not monotone on taking subgraphs. Let G be as depicted in Figure 1, and let H = K 4 be its subgraph. In this section, we show that the localization number of a graph is bounded from above by the pathwidth of the graph.

A path-decompositon of a graph

G = (V, E) is a sequence X = (X 1 , • • • , X t
) of subsets of V , called bags, such that, for every edge {u, v} ∈ E, there exists a bag containing both u and v, and such that, for every 1

≤ i ≤ k ≤ j ≤ t, X i ∩ X j ⊆ X k .
The width of X equals max 1≤i≤t |X i | -1 and the pathwidth of G, denoted by pw(G), is the minimum width of its path-decompositions. Pathwidth and path-decompositions are closely related to some kind of pursuit-evasion games [START_REF] Bienstock | Graph searching, path-width, tree-width and related problems (a survey)[END_REF]. moving, the robber can only reach some vertex in i+1≤j X j . Hence, the induction hypothesis holds. Eventually (for i = t), the robber will be located.

To show that the bound is achieved in interval graphs, consider the strategy where the robber stays in a maximum clique of an interval graph G (i.e., a clique of size pw(G) + 1). Using at most pw(G) -1 probes, there are always two vertices of the clique that are not distinguishable and where the robber may be.

Planar graphs; blind cops and bush cutting

This section is devoted to prove that the localization number of planar graphs (even for graphs obtained from a tree by adding to it a universal vertex, in particular, with treewidth 2) is unbounded. To this end we introduce another variant of the localization game in which the cops are blind. The game proceeds as follows. First the robber chooses a vertex of a graph G (unknown to the cops). Then k blind cops probe k vertices of G and their neighbors. That is, if the robber is occupying one of the probed vertices or any neighbor of the probed vertices, it is immediately caught. Otherwise, the cops only learn that the robber do not occupy any of these vertices. If the robber is caught the game is over. Otherwise, in next round robber may walk to a neighboring vertex while cops may choose new vertices arbitrarily. Let ζ b (G) denote the least number of blind cops needed to catch the robber on a graph G. Note that ζ b (G) and ζ(G) are a priori not comparable since, in the blind game, the cops have less power if the robber is "far" (they do no get any information about its distance) but the cops are more powerful if the robber is "close", since the robber is precisely located (and so, caught) at any vertex of the closed neighborhood of the probed vertices.

However, the following proposition shows relation between the two localization games. Proof. Suppose that ζ(G ) = k, and consider localization game on G with k + 1 cops, with one extra cop placed on the new vertex v during the whole game. This forces robber to use only vertices of G, but of course, the cops still have a winning strategy. Moreover, each situation in the usual localization game on G is now transformed into the blind cops game on G (removing the cop in v). That is so, because the distance in G from the robber to any vertex occupied by a cop is either one or two, which corresponds to the situation when the robber is in the neighborhood of a cop or not (in the blind game on G). By the assumption the usual game ends with localizing the robber at some vertex x. Hence, the blind game can be ended in the next move by placing a cop on that vertex x.

Our aim is now to prove that there exists a sequence of trees T k such that ζ b (T k ) > k. By Proposition 4, this will prove unboundedness of ζ(G) for planar graphs since each graph T k is planar. To achieve this goal we introduce a slightly modified game just to simplify the logic of forthcoming arguments.

Consider the following turn-by-turn game. Let k be a positive integer. Initially, a bush is present on each vertex of a graph and the goal of k bush-cutters is to remove it completely. At every turn, every bush-cutter chooses a vertex and removes the bush from the closed neighborhood of it. Then, the bush extends to every neighbor of the vertices where the bush is still present. Let the bush number of G, denoted by B(G), be the least number of bushcutters for which there is a strategy to remove the bush. Clearly by choosing any dominating set bush-cutters can cut the whole bush in one round. Hence the bush number is well defined and B(G) ≤ γ(G), where γ(G) denotes the size of a smallest dominating set of G.

Note that this model is connected with the blind cops game strategy in the following sense.

Proposition 5. Every graph G satisfies B(G) ≤ ζ b (G).
Proof. Suppose for a contrary that k-cutters never can cut the whole bush on G, i.e., k < B(G). We show that k < ζ b (G), that is, we show that the robber can win against k blind cops. It means that we aim at describing an infinite strategy of the robber that prevents the k blind cops to localized it. Since the strategy of the blind cops is deterministic and the number of configurations (positions of the cops and of the robber) is finite, it is sufficient to show that there is a long enough strategy of the robber that prevents the k blind cops to localized it. We actually show that, for every t ∈ N and for every strategy of the cops, there is a strategy of the robber that prevents the k blind cops to localized it for at least t rounds. Let us consider any strategy S of k blind cops (i.e., at every turn, k vertices are probed). Note that, in the blind game, the cops get no information unless they localize the robber and win. Therefore, any strategy is actually defined as an infinite sequence

(v i 1 , • • • , v i k ) i∈N , where the vertices in (v i 1 , • • • , v i k )
are the ones that are probed at the ith turn. The strategy is winning if there is a turn i when the robber is occupying a vertex in the closed neighborhood of the probed vertices at this turn.

Let us show that, for every t ∈ N, there is a strategy for the robber to win against S during at least k turns. Let S be the strategy of k brush-cutters that follows S (i.e., when one vertex v is probed in S, the bush is cut in N [v] in S ). Since k < B(G), after t turns, there is a vertex x ∈ V (G) that still belongs to the bush. By definition of the growth of the bush, there exists a sequence W = (x 1 , • • • , x t ) of vertices such that, for every 1 ≤ i ≤ t, x i+1 ∈ N [x i ] and x i is in the bush after the ith turn of the cut-bushers.

Note that for every turn i, there is

x i / ∈ j≤k N [v i j ]
. Hence, the robber just has to follow the walk W in order to win t turns against S.

Przemek: Lemma 6 (in the previous version) was wrong, removed. I've rewrited the tatement and the proof of the following to omit using it. Please check it. For your (and my) convenience I've decided to write everything in black. Begin of changes.

Before proving the main result of this section we will need the following technical lemma on bicolored matchings in trees. Let (T, f ) be any tree together with a coloring f : V (T ) → {0, 1} where f is any 2-vertex coloring of the tree T (not necessary proper). Recall that a matching is a set of disjoint edges. We say that a matching

M ⊆ E(T ) of a 2-colored tree (T, f ) is bicolored if every edge uv ∈ M has endpoints in different colors, in other words f (u) = f (v). We say that (T, f ) is monochromatic if f -1 (1) = V (T ) or f -1 (0) = V (T ), i.e.
, if all vertices receive the same color. The following claim is obvious: Claim 6. If (T, f ) is not monochromatic, then there is a bicolored edge.

Przemek: I've changed name of root vertex to v to prevent misunderstanding as we use term r-subtree for rooted trees with noname root. Given a tree T rooted in v ∈ V (T ), an r-subtree T of T is any sub-tree of T rooted in a child of the root vertex v. For any k ≥ 1 and h ≥ 1, let T k h be the complete (12k + 1)-ary rooted tree of height h.

Let n h,k = |V (T k h )| = (12k + 1) h + 1. Lemma 7. Let k ≥ 1, T k h be complete (12k + 1)-ary rooted tree of height 1 ≤ h ≤ 6k. Let f : V (T k h ) → {0, 1} be any 2-vertex coloring of T k h such that (4.1) n h,k + h -8k 2 ≤ |f -1 ({1})| < n h,k + 6k -h 2 .
Then there exists a bicolored matching of size at least h.

Proof. The proof is by induction on h ≥ 1. For base step, h = 1 note that a tree T k 1 have between 2k and 9k leaves with color 1. Hence, since T k 1 has 12k + 1 leaves, T k 1 is non monochromatic, there is a bicolored edge (matching of size 1). Now, let h be such that 1 < h ≤ 6k, and let us assume by induction that the lemma is true for every h < h. Let f be any 2-coloring of T k h satisfying (4.1), and let M be a corresponding maximum bicolored matching. We show that |M | ≥ h.

If (T k h , f ) contains at least 6k (vertex-disjoint) non-monochromatic r-subtrees, then there is a bicolored matching M with |M | ≥ 6k ≥ h by Claim 6 and the lemma is proved. Hence, we may assume that T k h contains at most 6k -1 non-monochromatic r-subtrees, i.e., at least 6k + 2 monochromatic r-subtrees.

By (4.1), for y ∈ {0, 1}, the number of monochromatic y-colored r-subtrees is not greater than 6k. Therefore, there must be at least one monochromatic r-subtree colored with 0 and at least one colored with 1. Hence, the root of T k h is an endpoint of some edge of M . There are two cases to be considered.

(1) If a unique r-subtree (say T ) is not colored monochromatically by f , then we are done. Indeed, in this case, by above paragraph, there are exactly 6k monochromatic r-subtrees colored with 0 and 6k monochromatic r-subtrees colored with 1. Note that the number of vertices n h-1,k of any r-subtree satisfies (12k + 1)n h-1,k + 1 = n h,k . Hence, by (4.1), the number |f -1 |T ({1})| of vertices colored with 1 in T is between

n h,k +h-8k 2
-6k * n h-1,k -1 (the last "minus one" is in case the root of T k h is colored with 1) and

n h,k +6k-h 2 -6k * n h-1,k . That is, n h-1,k + (h -1) -8k 2 ≤ |f -1 |T ({1})| < n h-1,k + 6k -(h -1)
2 Therefore, by the inductive assumption, T contains a matching of at least h -1 bicolored edges. Adding the bicolored edge between one monochromatic r-subtree and the root of T k h , we get that a bicolored matching of size at least h in T k h . (2) Suppose now that there are x ≥ 2 non monochromatic r-subtrees. Enumerate all rsubtrees by T 1 , T 2 , . . . , T 12k+1-x , T 12k+2-x , . . . , T 12k+1 , in such a way that, for every i ≤ 12k + 1 -x, the r-subtree T i is monochrome (while the r-subtrees T 12k+2-x , . . . , T 12k+1 are not monochomatic). Consider now the subtrees of T k h rooted in the grand-children of the root of T k h , i.e., the r-subtrees of the T i 's. To avoid confusion, let us refer to these (12k + 1)(12k + 1) subtrees as the s-subtrees.

Note that there are less than 6k non monochromatic such s-subtrees since otherwise, by Claim 6, we would already get a bicolored matching of size at least 6k. Combined with (4.1), this implies that, for y ∈ {0, 1}, there are at least (12k+1)6k+1 monochromatic s-subtrees colored with y. Therefore, at least one of T i 's has monochromatic s-subtree in each color. Renumbering when necessary, assume that it is T = T 12k+1 . We claim that it is possible to improve the coloring f to a new coloring f , satisfying |f -1 ({1})| = |f -1 ({1})| such that the maximum bicolored matching M corresponding to f is such that |M | ≤ |M | and all trees T i for i < 12k + 1 are monochromatic. Therefore, we are back to the case (1) when there is exactly one non-monochromatic r-subtree which finishes the proof.

Let z < 6k be the number of non monochromatic s-subtrees. Note that, the x non monochromatic r-subtrees T i (i ≥ 12k + 2 -x) contain (12k + 1)x -z monochromatic s-subtrees. Let t y be the number of monochromatic s-subtrees with color y ∈ {0, 1}. Note that, according to (4.1) one has t 0 mod (12k + 1) + t 1 mod (12k + 1) + z = 12k + 1.

Indeed, for h = 2 there is z = 0. For h > 2 consider such a coloring of these z s-subtrees that numbers of y-colored vertices are the same and at most one s-subtree is non monochrome, clearly there is z y < z y-colored s-subtrees for y ∈ {0, 1}. Notice that (from (4.1)) there is t y mod (12k + 1) + z y = 6k, while z y < z < 6k.

We want to exchange these s-subtrees (precisely, we aim at exchanging their coloring) between r-subtrees to minimize the number of r-subtrees containing s-subtrees in both colors. So, for y ∈ {0, 1}, let x y = ty 12k+1 be the number of desired monochromatic trees T i with i ≥ 12k + 1 -x. Clearly x 0 + x 1 = x -1, moreover at least x y r-subtrees T i contains monochromatic s-subtree in a color y. For i between 12k +2-x and 12k assign g i as the desired color of the r-subtree T i following the two rules: the tree T i contains monochromatic s-subtree in color g i and among values of g i , there are precisely x 0 zeros and x 1 ones.

By a simple counting argument, for at least one color y ∈ {0, 1} there are at least two monochromatic y-colored s-subtrees in T = T 12k+1 and there is a tree T i with g i = y such that T i contains an s-subtree which is not in color y (either non monochrome or in other color). We improve the coloring exchanging those two subtrees. Note, that it does not increase the size of the bicolored matching (as T contains another monochromatic subtrees in both colors, while T i in color y). We repeat this procedure until each r-subtree T i , i < 12k + 1, contains only monochromatic s-subtrees in one color. Now, for each r-subtrees T i for which the root has a color different than g i , let us exchange the color of this root with the color of some vertex from the tree T with the opposite color. Clearly it removes one edge from a matching (in the tree T i ) and adds at most one in T . Therefore it does not increase the total size of the bicolored matching. Finally, we have obtained a coloring f as claimed which finishes the proof.

Przemek: End of changes

We are now ready to prove the aforementioned result. Theorem 8. For every k ≥ 1, there exists a tree T k such that B(T k ) > k.

Proof. Let k, i ∈ N. Let T k i be the complete (12k +1)-ary rooted tree of height i. The number of vertices of T k i satisfies

|V (T k i )| = (12k + 1) i+1 -1 12k .
The tree T k is constructed by subdividing twice each edge of T k 6k . The vertices of T k of degree different than 2 are said regular vertices, while vertices of degree 2 -subdivision vertices.

For regular vertices we will use a terminology of parents, children, ancestors and descendants (regarding corresponding T k 6k tree), while for the whole tree -a terminology of neighbors. Let k ≥ 1. Let n = |V (T k 6k )| denote the number of regular vertices in T k . We show that k bush-cutters cannot clean a tree T k . Suppose otherwise. Then there exists a strategy of cutting allowing to clean the tree. For each time step t (before cutters move) denote by m t number of clean (without bush) regular vertices.

Let now t be the last round when, before cutters move, bush grows on more than a half of regular vertices, so this is the last moment when m t < n 2 . As at each time step cutters can cut at most k regular vertices the number m t of clean regular vertices satisfies inequality

n 2 -k ≤ m t .
By Lemma 7 (color vertices of T k 6k by 0 or by 1 whether corresponding regular vertices of T k are bush or clean respectively), there exists a bicolored matching M of size 6k in T k 6k (whose edges are between bush and clean vertices). In the tree T k , the edges of M correspond to paths (say M -paths) of length 3 connecting bush and clean vertices with the property that each vertex belong to at most one such path.

In three consecutive rounds cutters can cut the bush on at most 3k endpoints of Mpaths. While on at least 3k such an endpoints bush regrows. Hence, m t+3 ≤ m t < n 2 . A contradiction.

From Propositions 4 and 5 and Theorem 8, we get that: Corollary 9. For any k > 0, there exists a planar graph G with treewidth 2 (precisely, a tree plus a universal vertex) such that ζ(G) > k.

Complexity

In this section, we prove that the localization game (i.e., computing ζ) is NP-hard. We first introduce some related problems. A set L ⊆ V of vertices is called a locating set if, for every u, v ∈ V \ L, N [u] ∩ L = N [v] ∩ L. Note that a locating set must "see" almost all vertices. Formally, for any locating set L, |V \ N [L]| ≤ 1. Indeed, otherwise, there would be two vertices u, v such that

N [u] ∩ L = N [v] ∩ L = ∅. A set LD ⊆ V of vertices is called a dominating-locating set if LD is a dominating set and, for every u, v ∈ V \ LD, N [u] ∩ LD = N [v] ∩ LD.
By definition, the minimum size of a dominating-locating set is at least the minimum size of locating set. Moreover, by remark above the minimum size of a dominating-locating set is at most one plus the minimum size of locating set. It is known that: Theorem 10. [START_REF] Cohen | On Identifying Codes[END_REF][START_REF] Charon | Minimizing the Size of an Identifying or Locating-Dominating Code in a Graph is NP-Hard[END_REF] Computing a minimum dominating-locating set is NP-hard.

We first deduce the following easy result Corollary 11. Computing a minimum locating set is NP-hard in the class of graphs with diameter 2.

Proof. We first show that computing a minimum locating set is NP-hard in general graphs. We present a reduction from the problem of computing a minimum dominating-locating set which is NP-hard by previous Theorem. Let G be any graph and let G be the graph obtained from G by adding to it an isolated vertex x. Then, G has a locating-dominating set of size k if and only if G has a locating set of size k. Indeed,

• assume that C ⊆ V (G) is a locating-dominating set of G, then it is clearly a locating set of G (where x is the only vertex with N [x] ∩ C = ∅).

• On the other hand, let

C ⊆ V (G ) be locating set of G . If C ∩ V (G) is a dominating set of V (G), then C is a locating-dominating set of G. Otherwise, a unique vertex v ∈ V (G) is not dominated by C. In that case, x must belong to C (otherwise we would have N [x]∩C = N [v]∩C = ∅).
Therefore, C∪{v}\{x} is a locating-dominating set of G with same size than C. Now, let us show that computing a minimum locating set is NP-hard in the class of graphs with a universal vertex. The reduction is from the locating set problem which is NP-hard by previous paragraph. Let G be any graph with at least two vertices, and let G be the graph obtained from G by adding three new vertices u, v, w, the edge {v, w} and making u universal, i.e., adjacent to every vertex of V (G) ∪ {v, w}. Then, G has a locating set of size k if and only if G has a locating set of size k + 1. Indeed,

• if C ⊆ V (G) is a locating set of G, then C ∪ {v} is a locating set for G . • Now, let C ⊆ V (G ) be a minimum locating set of G .
It is easy to check that exactly one of v or w must belong to C (if none of them belongs to it, they cannot be distinguished, and if both of them belongs to C, one of them can be removed) and that u does not (adding u in C would differentiate only itself while it is already identified by v or w). W.l.o.g., we may assume that C ∩ {u, v, w} = {v}. Therefore, it is also easy to check that C \ {v} is a locating set for G.

We are now ready for our main result Theorem 12. The localization game is NP-hard.

Proof. We present a reduction from the problem of computing a minimum locating set in graphs with diameter 2 which is NP-hard by previous corollary.

Let G be any n-node graph with diameter 2. Let G be the graph obtained from G by adding n + 1 pairwise non-adjacent vertices x 1 , • • • , x n+1 , each of them being adjacent to every vertex of V (G). Note that, because G has diameter 2, then G is an isometric subgraph of G (i.e., distances are preserved). Let k be the minimum size of a locating set of G. We prove that ζ(G ) = k + 1.

• First, let us prove that ζ(G ) ≤ k + 1. Let C be a locating set of G with size k. The game will last at most n + 1 turns. At turn i, the Cop-player probes the vertices in C ∪ {x i }. We show that the robber can never reach a vertex of V (G) without being immediately caught. Therefore, the robber is stacked at its initial position in {x 1 , • • • , x n+1 }, say x j . Hence, it will be caught at turn j. First, at every turn i, the Cop-player can decide if the location r of the robber belongs to V (G) or not. Indeed, the robber is located at {x 1 , • • • , x n+1 } if and only if the distance between r and x i is strictly larger than the distance between r and every other vertex of C. Now assume that r ∈ V (G) just before any turn i and that r / ∈ C (otherwise it is immediately caught). For every vertex v ∈ C, r ∈ N (v) if and only if the distance between v and r equals the distance between r and x i . Since C is a locating set (and recall that G is isometric in G ), r can be identified.

• Finally, let us prove that ζ(G ) ≥ k + 1. For this purpose, let us describe an escape strategy for the robber when the Cop-player can probe at most k vertices at each turn. Note that, since (obviously) k < n, at every turn, at least two vertices of {x 1 , • • • , x n+1 } are not probed.

-If the robber is currently occupying a vertex of V (G), then it goes to a vertex x i that will not be probed by the Cop-player (recall that we assume the worst case, i.e., the robber knows the whole strategy of the Cop-player). By the remark above (two vertices of {x 1 , • • • , x n+1 } are not probed), the location of the robber cannot be identified. -If the robber currently occupies a vertex in {x 1 , • • • , x n+1 } and the Cop-player is about to probe k vertices in V (G), then the robber stays idle. -Finally, consider the case when the robber occupies a vertex in {x 1 , • • • , x n+1 } and the Cop-player will probe t ≤ k -1 vertices in V (G) (and k -t vertices in

{x 1 , • • • , x n+1 }). Let Y ⊆ V (G) be the set of vertices of V (G ) \ {x 1 , • • • , x n+1 }
that will be probed. Note that because the graph G has diameter 2, for any probed vertex v, the distance between v and the location r of the robber only gives the information of whether r = v or r ∈ N (v) or r / ∈ N [v] (similar information as given by a locating set). Since Y is not a locating set (because |Y | < k), at least two vertices u and v cannot be distinguished by Y in G. Then, the robber goes to one of these vertices (note that the probed vertices in {x 1 , • • • , x n+1 } bring no more information allowing to distinguish u and v).

Geometric localization game

Consider an infinite graph G 1 whose vertices are all points of the plane with edges between points at Euclidean distance at most one. In other words, G 1 is the intersection graph of all unit disks in the plane. Notice that the graph distance between two vertices in G 1 is the least integer not smaller than the Euclidean distance between the corresponding points. In the first result we show that a countable number of cops is not sufficient to localize the robber exactly on G 1 . Recall that ℵ 0 denotes the cardinality of the natural numbers.

Proposition 13. ζ(G 1 ) > ℵ 0 .
Proof. We will show that after each round there are uncountably many possible locations for the Robber-player. Let C be the set of probed points. For any c ∈ C consider a set of all circles with center c and integer radius. Such circles divide the plane into regions according to their distance from c. Let us denote the set of possible positions of the Robber-player by R. Assume that after the previous rounds of the game there are uncountably many points in R (which is true at the beginning of the game). Consider the partition of R created by all such circles around all points from C. Since there are countably many circles, at least one region of the partition must contain uncountably many points. Hence if Robber chooses to stay in that region he will not be localized.

In view of the above result we consider a relaxed version of the game in which Cop measures the actual Euclidean distance to robber's location. We will call it the geometric localization game on the plane. Theorem 14. The following statements hold for the geometric localization game on the plane:

(1) Three cops can win in one round.

(2) Two cops can win in two rounds.

(3) One cop cannot win in any number of rounds.

v 1 v 2 p 1 p 2 v 3 v 4 Figure 2.
The winning strategy in two moves for the Cop Proof. For the first statement, the winning strategy for the Cop-player is to choose three noncolinear points. Then for every possible location of the robber, the sequence of distances is unique, so he is immediately localized.

For the second statement, the winning strategy (presented in Figure 2) for the Cop-player is the following:

• In the first round, the Cop-player checks any two points v 1 and v 2 . If the robber is not on one of these points (which would end the game), then each of v 1 and v 2 gives a circle on which the robber is located. If these cycles intersect in only one point, this is the location of the robber and the Cop-player wins. Otherwise, the circles intersect in two points: p 1 and p 2 , and the Cop-player needs the second round to win. • In second round, the Cop-player already knows that the robber was in one of the two possible locations p 1 , p 2 , and he moved by at most one, hence he is in one of the two unit disks with centers in p 1 and p 2 (the disks may have nonempty intersection). Now, the Cop-player can draw a line such that both disks lie entirely on the same side of the line. Hence the robber is on that side of the line. Then, the Cop-player chooses any two points on the line v 3 and v 4 and asks for their distances to the robber. Again she gets two circles on which the robber is located, which intersect in at most two points. But now only one of those points is on the same side of the line as the disks, and that point is the location of the robber. To prove the third assertion of the theorem we will show that the robber has a winning strategy even if, at the beginning of each round, he tells the Cop-player his previous location p. That implies that, at the beginning of each round, the Cop-player knows that the current location of the robber is in a unit disk D centered in p. Then, the Cop-player chooses a vertex c to check and the robber makes his move. Note that, as long as the robber avoids point c, the distance d between c and the robber is greater than zero. This gives a circular arc (intersection of a circle with D) with center in c and radius d, where the robber must be located. If the robber stays in the interior of D, then the arc will consist of more than one point. Hence the robber will not be located.

From the point of view of practical applications it is also natural to consider approximate version of the geometric localization game, where the Cop-player is satisfied with determining the robber's position up to some small error.

Theorem 15. For any ε > 0, one cop can locate the robber with error of at most 1 + ε. In other words one cop can determine a disk of radius 1 + ε in which the robber is contained.

Proof. Let ε > 0 and δ such that 0 < (1 + δ) 2 + δ 2 ≤ 1 + ε. We will show that, in three rounds, the Cop-player will know that the robber is on a single arc which is arbitrarily close to a segment of length at most 2 + 2δ (see Figure 3). Note that, in the end of the ith round, the Cop-player knows that the robber is in the intersection of a circle (with center in the checked vertex c i and radius equal to its distance from the robber) and an area A i , which she predicted to contain the robber (with prediction being based on previous rounds). Hence, the robber is in the set S i which is a collection of circular arcs. It is easy to see that A i+1 = {z ∈ R 2 : dist(z, s) ≤ 1 for some s ∈ S i }.

The strategy for the Cop-player is to draw a line through two points of A i which are at the largest possible distance from each other. Then in the next round to choose a vertex c i from the line arbitrarily far from A i .

After first round, the Cop-player knows that the robber is on a circle and predicts that in the next round he must be in an annulus A 2 . In the second round, she probes a vertex c 2 in the unbounded face of R 2 \ A 2 . The intersection S 2 of received circle and A 2 will consist

  The graph-parameter ζ(G) is called the localization number of a graph G. Notice that this parameter is well defined since the inequality ζ(G) ≤ |V (G)| holds obviously. Note also that, by definition, ζ(G) is equal to the maximum ζ(C) among the connected components C of G. Therefore, from now on, only connected graphs are considered.

Proposition 1 .

 1 Every complete bipartite graph K a,b satisfies ζ(K a,b ) = min(a, b).

Corollary 2 .

 2 Every bipartite graph G with partition classes of size a and b satisfies ζ(G) ≤ min(a, b).

Figure 1 .

 1 Figure 1. ζ(H) = 3, ζ(G) = 2

Proposition 4 .

 4 For a given graph G, let G be a copy of G with one additional vertex v adjacent to all vertices of G. Then ζ b (G) ≤ ζ(G ).

3 Figure 3 .

 33 Figure 3. Locating the robber on an arc close to a short segment.

In this paper, N (v) denotes the set of neighbors of a vertex v and N [v] = N (v) ∪ {v}.

The metric dimension of a graph G is the minimum cardinality of a subset S of vertices such that all other vertices are uniquely determined by their distances to the vertices in S.

Proposition 3. Every graph G satisfies ζ(G) ≤ pw(G). Moreover, this bound is achieved for interval graphs.Przemek: Proof was changed from submission.Proof. We may assume that G is connected and has at least two vertices. Let (X 1 , • • • , X t ) be an optimal path-decomposition (of width pw(G)) of G. We may assume that|X i \ X i+1 | ≥ 1 for every 1 ≤ i < t (otherwise, if X i ⊆ X i+1 , we may consider the path decomposition (X 1 , • • • , X i-1 , X i+1 , • • • , X t )).We also may assume that, for every 1 ≤ i < t and every u ∈ X i \ X i+1 , u has a neighbor in X i (otherwise, because G is connected, we may consider the path decomposition (X1 , • • • , X i-1 , X i \ {u}, X i+1 , • • • , X t )).For every 1 ≤ i < t, let u i be any vertex in X i \ X i+1 and let v i be a neighbor of u i in X i . Finally, let v t be any vertex in X t \ X t-1 and u t be any neighbor of v t (u t exists since G is connected and belongs to X t ). Sequentially, for i = 1 to t, the Cop-player probes X i \ v i . We will show by induction on i, that before the i th turn of the Cop-player, the robber must occupy some vertex in i≤j X j (this clearly holds for i = 1). If the robber is in X i \ v i , he is located. Moreover, if he is in v i , he is located because the robber is at distance 1 from u i (and not already localized) iff he is at v i . If not located, the robber must be in G \ ( j≤i X j ). By

B. BOSEK, P. GORDINOWICZ, J. GRYTCZUK, N. NISSE, J. SOK Ó L, AND M. ŚLESZY ŃSKA-NOWAK

B. BOSEK, P. GORDINOWICZ, J. GRYTCZUK, N. NISSE, J. SOK Ó L, AND M. ŚLESZY ŃSKA-NOWAK

This work was supported by The National Center for Research (J. Grytczuk, J. Sokó l, M. Śleszyńska-Nowak) and Development under the project PBS2/B3/24/2014, by the ANR project Stint (ANR-13-BS02-0007) (N. Nisse) and the associated Inria team AlDyNet (N. Nisse).

of either one or two arcs. Notice that the further the chosen vertex c 2 is from A 2 , the closer the arcs from S 2 are to be segments. In other words, we can find a line l such that for every point x ∈ S 2 there exists y ∈ l with dis(x, y) < δ. Hence every point from

is at distance at most 1 + δ from l (by the triangle inequality).

Then in the third round, the Cop-player chooses a vertex c 3 to be 'far' from A 3 and on the line l. The intersection S 3 of A 3 and the resulting circle is one arc. Again, if c 3 is far enough from A 3 , then we can find a line k such that for every point x ∈ S 3 there exists y ∈ k with dis(x, y) < δ. Moreover we can choose k to be perpendicular to the line l. Let p be the point of the intersection of k and l. Let k be the intersection of k and A 3 . Then the distance between p and any point of k is at most 1 + δ. Hence the distance from p to any point of S 3 (which contains the robber's current location) is at most (1 + δ) 2 + δ 2 ≤ 1 + ε. So, localizing the robber in p is correct up to an error of at most 1 + ε.

Further Work

In this paper, we have introduced the localization game (also introduced independently in [START_REF] Haslegrave | Locating a robber with multiple probes[END_REF]). Our study focused on upper bounds of ζ in planar graphs and computational complexity of this parameter in general graphs. Many questions remain open such that determining close formulas or bounds on ζ in other graph classes (e.g., outer-planar graphs, hypercube, partial cubes, chordal graphs, etc.). The question of the computational complexity of ζ in various graph classes such as bipartite graphs, split graphs (where computing the metric dimension is known to be NP-complete), bounded treewidth graphs, etc. is also of interest. Finally, most of the interesting turn-by-turn two-player games are known to be PSPACE-hard or even EXPTIME-complete. The exact status of the complexity of the localization game is still open.

It is also interesting to compare parameter ζ(G) to other graph invariants. For instance, it was proved in [START_REF] Johnson | Subgraphs and Colourability of Locatable Graphs[END_REF] that every graph with ζ(G) = 1 is four colorable. This leads to the following conjecture.