## 3 Computational complexity of the reconstruction problem  
In Computational Geometry the problem to determine a n-dimensional representation of a graph is usually known as the _graph realization problem_. A _realization_ of a graph in the n-dimensional Euclidean space is a mapping from the vertices of the graph into n-dimensional coordinates such that the spheres of unit radius centered in every pair of such coordinates intersect if and only if the related vertices of the graph are connected. The _unit_ of the sphere is not crucial here since a realization remains valid also if we scale the distances in the realized structure. Note that any undirected graph can be represented by means of an _adjacency matrix_, i.e. a binary symmetric matrix which contains \(1\) in the entry \(i,j\) if and only if the \(i\)-th vertex and the \(j\)-th vertex are connected. The graph realization problem is thus a generalization of the reconstruction problem from native protein contact maps (i.e. contact maps which contains no errors). The computational complexity of the graph realization problem was first addressed in the mid nineties by [PERSON] and [PERSON] [6]. The authors of [6] show that the problem to determine the _sphericity_ of a graph is _NP-complete_ (i.e. it cannot be solved by any polynomial-time algorithm unless P=NP, see for example [9]). The _sphericity_ of a graph is the smallest dimension in which the graph can be realized. Graphs of sphericity \(1\) are called _unit interval graphs_ and they can be recognized in polynomial time. [PERSON] and [PERSON] show that the problem to determine whether a graph can be realized in dimension \(2\) is no less difficult than the problem to determine whether there is an assignment to the variables of a boolean formula which makes the formula evaluate to true (i.e. the proof is by reduction from the SAT problem which is historically the first decision problem proved to be NP-complete). While the sphericity problem is NP-complete this does not imply that the problem cannot be solved in polynomial-time for some fixed dimension greater than \(2\) (as it happens for unit interval graphs). The authors of [6] argue that their construction can be easily modified to show that the sphericity problem is NP-complete also for dimension \(3\) (which is the most interesting case from our point of view) and, moreover, they conjecture that this is also true for every dimension greater that \(1\). At first glance it can seem that the problem to determine the sphericity of a graph has few to do with the graph realization problem. It is not difficult to see that if the graph realization problem could be solved in polynomial-time then the sphericity problem would be solved in polynomial-time, yielding to a contradiction. Assume that there is some polynomial-time algorithm which can compute a 2D representation of a graph if such graph has sphericity \(2\), on the contrary the algorithm returns some not consistent structure. Then we could use such algorithm to solve in polynomial-time the sphericity problem for dimension \(2\): given a graph we compute a 2D realization in polynomial-time and check (also in polynomial-time) if such realization is consistent with the graph; if the structure is not consistent then the graph has not sphericity \(2\), on the contrary the answer is positive. Actually, the negative result of [PERSON] and [PERSON] has also been extended in a recent work [17], in which the authors show that the graph realization problem cannot be even approximated in polynomial-time unless P=NP. While the graph realization problem is intractable, the reconstruction problem from protein contact maps is not so general. From a biological point of view a realization of a contact map which does not satisfies the constraint of a non-overlapping backbone is useless. With the additional backbone constraint the realization problem could be solved in polynomial-time.