ALGOSTRUCT-ID - Algorithms and structure for identification problems

In the field of identification problems, we are given a discrete structure (graph, set system, geometric configuration), which models data coming from a concrete application: industrial or agricultural complex, information system, computer network , etc.

The goal is to select a small set of elements from that structure, such that all other elements are uniquely identified by their relationships with the selected solution elements. For example, in the case of an industrial or agricultural complex or a computer network, sensors can be positioned on selected elements, so that all the locations in the complex or all the machines in the network are uniquely identified by the sensors [7].
Sensors can be deployed to protect the complex or network from intrusion or threats such as fires.
This type of problem is natural and has been studied in various contexts, under different names in the last decades, see for example [5, 6].

The corresponding algorithmic problem can be formulated as follows:

Discriminating Code
Input: A set system, or hypergraph, (X, S), where S is a family of subsets of a set X.
Output: A set C ⊆ X such that all sets of S have a distinct and non-empty intersection with C.

Another field of application is that of data mining in the field of machine learning [4]. For example, the V-C dimension, introduced by Vapnik and Cervonenkis, is a structural measure of hypergraphs that is very useful in machine learning because it allows to measure the complexity of the data. It turns out that the V-C dimension of a set system is directly related to the Discriminating Code problem, indeed it measures the maximum size of an "ideal" discriminating code [2].

Other applications of the problem concern, for example, medical tests and the biological properties of individuals [5].

Recent work underline the connection between the structural properties of the studieddiscrete structures and the behavior of the identification problems that we study. This is the case for classes of instances that come from geometric systems (for example in the case of sensor networks) [7], or also, graphs. In the latter case, the Discriminating Code problem is studied according to various variations such as Identifying Codes or Locating-Dominating Sets. These two problems have been studied for families of structured graphs which correspond to relevant practical applications [3].

In this project, we will study these problems from an algorithmic and structural point of view, in connection with relevant applications and using in particular the methods of the polyhedral approach, as initiated in [1].

References :
[1] G. Argiroffo, S. Bianchi, Y. Lucarini, A. Wagler. Polyhedra associated with identifying codes in graphs. Discrete Applied Mathematics 245:16–27, 2018.
[2] N. Bousquet, A. Lagoutte, Z. Li, A. Parreau, S. Thomassé. Identifying codes in hereditary classes of graphs and VC-dimension. SIAM Journal on Discrete Mathematics 29(4):2047–2064, 2015.
[3] F. Foucaud, G. B. Mertzios, R. Naserasr, A. Parreau, P. Valicov. Identification, location-domination and metric dimension on interval and permutation graphs. II. Complexity and algorithms. Algorithmica 78(3):914–944, 2017.
[4] S. Goldman, R. Rivest, R. Schapire. Learning binary relations and total orders. SIAM Journal on Computing 22:46–51, 1989.
[5] B. M. E. Moret, H. D. Shapiro. On minimizing a set of tests. SIAM Journal of Scientifical and Statistical Computation 6(4):983–1003, 1985.
[6] A. Rényi. On random generating elements of a finite Boolean algebra. Acta Scientiarum Mathematicarum Szeged 22:75–81, 1961.
[7] R. Ungrangsi, A. Trachtenberg, D. Starobinski. An implementation of indoor location detection systems based on identifying codes. Proc. INTELLCOMM 2004.