TY - GEN

T1 - VC Set Systems in Minor-free (Di)Graphs and Applications

AU - Le, Hung

AU - Wulff-Nilsen, Christian

N1 - Publisher Copyright: Copyright © 2024 by SIAM.

PY - 2024

Y1 - 2024

N2 - A recent line of work on VC set systems in minor-free (undirected) graphs, starting from Li and Parter [LP19], who constructed a new VC set system for planar graphs, has given surprising algorithmic results [LP19, Le23, DHV20, FHMWN20]. In this work, we initialize a more systematic study of VC set systems for minor-free graphs and their applications in both undirected graphs and directed graphs (a.k.a digraphs). More precisely: 1. We propose a new variant of the Li-Parter set system for undirected graphs. Our set system settles two weaknesses of the Li-Parter set system: the terminals can be anywhere, and the graph can be Kh-minor-free for any fixed h. We obtain several algorithmic applications, notably: (i) the first exact distance oracle for unweighted and undirected Kh-minor-free graphs that has truly subquadratic space and constant query time, and (ii) the first truly subquadratic time algorithm for computing Wiener index of Kh-minor-free graphs, resolving an open problem posed by Ducoffe, Habib, and Viennot [DHV20]. 2. We extend our set system to Kh-minor-free digraphs and show that its VC dimension is O(h2). We use this result to design the first subquadratic time algorithm for computing (unweighted) diameter and all-vertices eccentricities in Kh-minor-free digraphs. 3. We show that the system of directed balls in minor-free digraphs has VC dimension at most h − 1. We then present a new technique to exploit the VC system of balls, giving the first exact distance oracle for unweighted minor-free digraphs that has truly subquadratic space and logarithmic query time. 4. On the negative side, we show that VC set system constructed from shortest path trees of planar digraphs does not have a bounded VC dimension. This leaves an intriguing open problem: determine a necessary and sufficient condition for a set system derived from a minor-free graph to have a bounded VC dimension. The highlight of our work is the results for digraphs, as we are not aware of known algorithmic work on constructing and exploiting VC set systems for digraphs.

AB - A recent line of work on VC set systems in minor-free (undirected) graphs, starting from Li and Parter [LP19], who constructed a new VC set system for planar graphs, has given surprising algorithmic results [LP19, Le23, DHV20, FHMWN20]. In this work, we initialize a more systematic study of VC set systems for minor-free graphs and their applications in both undirected graphs and directed graphs (a.k.a digraphs). More precisely: 1. We propose a new variant of the Li-Parter set system for undirected graphs. Our set system settles two weaknesses of the Li-Parter set system: the terminals can be anywhere, and the graph can be Kh-minor-free for any fixed h. We obtain several algorithmic applications, notably: (i) the first exact distance oracle for unweighted and undirected Kh-minor-free graphs that has truly subquadratic space and constant query time, and (ii) the first truly subquadratic time algorithm for computing Wiener index of Kh-minor-free graphs, resolving an open problem posed by Ducoffe, Habib, and Viennot [DHV20]. 2. We extend our set system to Kh-minor-free digraphs and show that its VC dimension is O(h2). We use this result to design the first subquadratic time algorithm for computing (unweighted) diameter and all-vertices eccentricities in Kh-minor-free digraphs. 3. We show that the system of directed balls in minor-free digraphs has VC dimension at most h − 1. We then present a new technique to exploit the VC system of balls, giving the first exact distance oracle for unweighted minor-free digraphs that has truly subquadratic space and logarithmic query time. 4. On the negative side, we show that VC set system constructed from shortest path trees of planar digraphs does not have a bounded VC dimension. This leaves an intriguing open problem: determine a necessary and sufficient condition for a set system derived from a minor-free graph to have a bounded VC dimension. The highlight of our work is the results for digraphs, as we are not aware of known algorithmic work on constructing and exploiting VC set systems for digraphs.

U2 - 10.1137/1.9781611977912.192

DO - 10.1137/1.9781611977912.192

M3 - Article in proceedings

AN - SCOPUS:85188281944

SP - 5332

EP - 5360

BT - Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)

PB - SIAM

T2 - 35th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2024

Y2 - 7 January 2024 through 10 January 2024

ER -