  The $k$-CombDMR problem is that of determining whether an $n \times n$
distance matrix can be realised by $n$ vertices in some 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$. Moreover, we provide algorithms to construct such graph realisations by
solving appropriate 2-SAT instances. In the case where $k \geq 3$, this problem
is NP-complete. We show this by a reduction of the $k$-colourability problem to
the $k$-CombDMR problem. Finally, we discuss the simpler polynomial time
solvable problem of tree realisability for a given distance matrix.
