Abstract
The Distance Realization problem is defined as follows. Given an n × n matrix D of nonnegative integers, interpreted as intervertex distances, find an nvertex weighted or unweighted graph G realizing D, i.e., whose intervertex distances satisfy dist_G(i,j) = D_{i,j} for every 1 ≤ i < j ≤ n, or decide that no such realizing graph exists. The problem was studied for general weighted and unweighted graphs, as well as for cases where the realizing graph is restricted to a specific family of graphs (e.g., trees or bipartite graphs). An extension of Distance Realization that was studied in the past is where each entry in the matrix D may contain a range of consecutive permissible values. We refer to this extension as Range Distance Realization (or RangeDR). Restricting each range to at most k values yields the problem kRange Distance Realization (or kRangeDR). The current paper introduces a new extension of Distance Realization, in which each entry D_{i,j} of the matrix may contain an arbitrary set of acceptable values for the distance between i and j, for every 1 ≤ i < j ≤ n. We refer to this extension as Set Distance Realization (SetDR), and to the restricted problem where each entry may contain at most k values as kSet Distance Realization (or kSetDR).
We first show that 2RangeDR is NPhard for unweighted graphs (implying the same for 2SetDR). Next we prove that 2SetDR is NPhard for unweighted and weighted trees. We then explore SetDR where the realization is restricted to the families of stars, paths, or cycles. For the weighted case, our positive results are that for each of these families there exists a polynomial time algorithm for 2SetDR. On the hardness side, we prove that 6SetDR is NPhard for stars and 5SetDR is NPhard for paths and cycles. For the unweighted case, our results are the same, except for the case of unweighted stars, for which kSetDR is polynomially solvable for any k.
BibTeX  Entry
@InProceedings{barnoy_et_al:LIPIcs.MFCS.2022.13,
author = {BarNoy, Amotz and Peleg, David and Perry, Mor and Rawitz, Dror},
title = {{Graph Realization of Distance Sets}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {13:113:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772563},
ISSN = {18688969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16811},
URN = {urn:nbn:de:0030drops168119},
doi = {10.4230/LIPIcs.MFCS.2022.13},
annote = {Keywords: Graph Realization, distance realization, network design}
}
Keywords: 

Graph Realization, distance realization, network design 
Collection: 

47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022) 
Issue Date: 

2022 
Date of publication: 

22.08.2022 