NP-Completeness of the Combinatorial Distance Matrix Realisation Problem

David L. Fairbairn, George B. Mertzios, Norbert Peyerimhoff

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…