Reconstruction problems on graphs and discrete sets: theoretical results and algorithms

This PhD Thesis fits into the fields of Graph Theory and Discrete Geometry. More precisely, we study reconstruction problems on graphs, hypergraphs and polyominoes. We first study the null label problem on $3-$uniform hypergraphs. In particular, a null label is an assignment of $+1$ and $-1$ to the edges of a hypergraph such that each node belongs to the same number of edges labelled with $+1$ and $-1$. We prove that the existence of such labelling is related to the existence of a Hamiltonian cycle in the $2-$intersection graph of the $3-$uniform hypergraph considered. We then focus on the problem of deciding if a graph is the intersection graph of a hypergraph. We prove that this problem is, in general, $NP-$complete. However, we find some subclasses in which the problem can be polynomially solved. Then, we are concerned with retrieving information in the nodes of a graph using aggregated measurements over it. This problem was originally considered for polyominoes, but we extend it to hypergraphs and graphs framework, considering also some notions of convexity on them. Finally, we study the reconstruction of fully convex polyominoes starting from their horizontal and vertical projections. The complexity of this problem is still unknown, thus we first provide some of the previously proven results and, then, we define a new algorithm that could help to solve the problem. Unfortunately, in the last part of the algorithm, it is required to evaluate some $SAT$ formulas, which prevents determining its complexity. Therefore, we demonstrate some properties of these formulas, deriving from the geometrical properties of convex polyominoes, with the aim of simplifying their evaluation.