NP-completeness of the combinatorial distance matrix realisation problem

Fairbairn, David; Mertzios, George; Peyerimhoff, Norbert

Abstract

The k-CombDMR problem is that of determining whether an n×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≥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.

Citation

Fairbairn, D., Mertzios, G., & Peyerimhoff, N. (2025, December). NP-completeness of the combinatorial distance matrix realisation problem. Presented at 14th International Symposium on Algorithms and Complexity (CIAC 2025), Rome, Italy

• Presentation Conference Type: Conference Paper (published)
• Conference Name: 14th International Symposium on Algorithms and Complexity (CIAC 2025)
• Acceptance Date: Jan 30, 2025
• Deposit Date: Feb 10, 2025
• Peer Reviewed: Peer Reviewed
• Public URL: https://durham-repository.worktribe.com/output/3476186