Designing sparse directed spanners, which are subgraphs that approximately maintain distance constraints, has attracted sustained interest in TCS in the recent years, especially because of their wide applicability, and the difficulty to obtain tight bounds. However, more complex and yet natural network design problems that may require handling spanner-like constraints for multiple resources have witnessed less progress in the literature. In this paper we initiate the study of Directed Multicriteria spanners, in which the notion of edge lengths is generalized to the notion of resource consumption vectors, and the distance constraints for terminal pairs are generalized to resource constraint vectors. The goal is to find a minimum-cost routing solution that satisfies spanner-like resource constraints.
We obtain the first approximation algorithms for the Directed Multicriteria spanners problems, under natural assumptions, in both the offline setting, as well as in the setting where the input arrives in an online fashion. Our results match the state-of-the-art competitive ratios in a special case of ours, namely, weighted spanners by Grigorescu, Kumar, and Lin (APPROX 2023).
We also establish reductions from other natural network connectivity problems to the Directed Multicriteria spanners problems, including Group Steiner Distances, which was recently introduced in the undirected setting by Bilo, Guala, Leucci and Straziota (ESA 2024). Our reductions imply approximation algorithms for these problems and illustrate that the notion of Directed Multicriteria spanners is an appropriate abstraction and generalization of well-studied special cases.
Our main technical tool is a delicate generalization of the minimum-density junction trees framework of Chekuri, Even, Gupta, and Segev (SODA 2008, TALG 2011) to the notion of minimum-density resource-constrained junction trees, which also extends ideas from Chlamtác, Dinitz, Kortsarz, and Laekhanukit (SODA 2017, TALG 2020).
Based on joint work with Elena Grigorescu (Purdue) and Young-San Lin (Melbourne Business School).
