NP-Completeness of the Combinatorial Distance Matrix Realisation Problem
<|reference_start|>NP-Completeness of the Combinatorial Distance Matrix Realisation Problem: 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.<|reference_end|>
@article{fairbairn2024np-completeness,
    title={NP-Completeness of the Combinatorial Distance Matrix Realisation Problem},
    author={David L. Fairbairn, George B. Mertzios, Norbert Peyerimhoff},
    journal={arXiv preprint arXiv:2406.14729},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.14729},
    primaryClass={cs.DS cs.CC cs.DM}
}