VC Set Systems in Minor-free (Di)Graphs and Applications
Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
Standard
VC Set Systems in Minor-free (Di)Graphs and Applications. / Le, Hung; Wulff-Nilsen, Christian.
Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 2024. s. 5332-5360.Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
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 -
ID: 394372379