The Generalized Microscopic Image Reconstruction Problem for Hypergraphs

In this paper we study a particular case of the microscopic image reconstruction problem, first introduced in [6,10] and then extended to undirected unweighted graphs in [2]. We consider a general hypergraph H = (V, E) such that each node v has assigned a physical value lv that we would determine. Since in many applications it may be difficult or almost impossible to directly extract these values, we study how to retrieve them starting from the set of probes P-v = Sigma(w is an element of N(w)) lw, i.e. the sum of labels of v's neighbors. In particular, we prove that the values l(v) can be found in polynomial time using linear algebra tools and that the problem can be shifted to undirected weighted graphs trough the concept of 2-section of a hypergraph. Finally, we provide some classes of hypergraphs whose 2-intersection graphs have a specific form (a line or a s-tree) and whose related reconstruction problem from the probes can be performed with the minimum number of zero or one surgical probe.