2024/06/20 by Fairbairn, David L., Mertzios, George B., Peyerimhoff, Norbert
#Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #F.2.2 #FOS: Computer and information sciences #G.2.2
paper · doi:10.48550/arxiv.2406.14729
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.