The \(k\) -CombDMR problem is that of determining whether an \(n \times n\) distance matrix can be realised as a sub-matrix by \(n\) vertices in some unweighted undirected graph with \(n + k\) vertices. This problem has a simple solution in the case \(k=0\) . In this paper we show that this problem is polynomial-time solvable for \(k=1\) and \(k=2\) , and we provide algorithms to construct such graph realisations by solving appropriate 2-SAT instances. For the case where \(k \ge 3\) , we prove that the problem becomes NP-complete. We show this by a reduction from the k-colourability problem, where \(k\ge 3\) . Finally, we present how the simpler problem of tree realisability can be solved in polynomial time for all \(k \ge 0\) .