Representation of Short Distances in Structurally Sparse Graphs

Author Zdeněk Dvořák



PDF
Thumbnail PDF

File

LIPIcs.STACS.2023.28.pdf
  • Filesize: 0.74 MB
  • 22 pages

Document Identifiers

Author Details

Zdeněk Dvořák
  • Computer Science Institute, Charles University, Prague, Czech Republic

Cite AsGet BibTex

Zdeněk Dvořák. Representation of Short Distances in Structurally Sparse Graphs. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 28:1-28:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.STACS.2023.28

Abstract

A partial orientation H of a graph G is a weak r-guidance system if for any two vertices at distance at most r in G, there exists a shortest path P between them such that H directs all but one edge in P towards this edge. In case that H has bounded maximum outdegree Δ, this gives an efficient representation of shortest paths of length at most r in G: For any pair of vertices, we can either determine the distance between them or decide the distance is more than r, and in the former case, find a shortest path between them, in time O(Δ^r). We show that graphs from many natural graph classes admit such weak guidance systems, and study the algorithmic aspects of this notion. We also apply the notion to obtain approximation algorithms for distance variants of the independence and domination number in graph classes that admit weak guidance systems of bounded maximum outdegree.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph theory
Keywords
  • distances
  • structurally sparse graphs

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. H. Adler and I. Adler. Interpreting nowhere dense graph classes as a classical notion of model theory. European Journal of Combinatorics, 36:322-330, 2014. Google Scholar
  2. J. Dreier. Lacon-and shrub-decompositions: a new characterization of first-order transductions of bounded expansion classes. In 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), pages 1-13. IEEE, 2021. Google Scholar
  3. J. Dreier, J. Gajarský, S. Kiefer, M. Pilipczuk, and Sz. Toruńczyk. Treelike decompositions for transductions of sparse graphs. arXiv, 2022. URL: http://arxiv.org/abs/2201.11082.
  4. Z. Dvořák. Constant-factor approximation of domination number in sparse graphs. European Journal of Combinatorics, 34:833-840, 2013. Google Scholar
  5. Z. Dvořák. Induced subdivisions and bounded expansion. European Journal of Combinatorics, 69:143-148, 2018. Google Scholar
  6. Z. Dvořák. On distance r-dominating and 2r-independent sets in sparse graphs. J. Graph Theory, 91(2):162-173, 2019. Google Scholar
  7. Z. Dvořák and A. Lahiri. Approximation schemes for bounded distance problems on fractionally treewidth-fragile graphs. In 29th Annual European Symposium on Algorithms (ESA 2021). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2021. Google Scholar
  8. J. Gajarský, P. Hliněnỳ, J. Obdržálek, D. Lokshtanov, and MS Ramanujan. A new perspective on FO model checking of dense graph classes. ACM Transactions on Computational Logic (TOCL), 21(4):1-23, 2020. Google Scholar
  9. J. Gajarský, S. Kreutzer, J. Nešetřil, P. Ossona De Mendez, M. Pilipczuk, S. Siebertz, and Sz. Toruńczyk. First-order interpretations of bounded expansion classes. ACM Transactions on Computational Logic (TOCL), 21(4):1-41, 2020. Google Scholar
  10. R. Ganian, P. Hliněný, J. Nešetřil, J. Obdržálek, and P. Ossona de Mendez. Shrub-depth: Capturing Height of Dense Graphs. Logical Methods in Computer Science, 15, 2019. Google Scholar
  11. Ł. Kowalik and M. Kurowski. Oracles for bounded length shortest paths in planar graphs. ACM Trans. Algorithms, 2:335-363, 2006. Google Scholar
  12. J. Nešetřil, P. Ossona de Mendez, M. Pilipczuk, R. Rabinovich, and S. Siebertz. Rankwidth meets stability. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2014-2033. SIAM, 2021. Google Scholar
  13. J. Nešetřil and P. Ossona de Mendez. Sparsity (Graphs, Structures, and Algorithms), volume 28 of Algorithms and Combinatorics. Springer, 2012. Google Scholar
  14. J. Pach and P. K. Agarwal. Combinatorial geometry. John Wiley & Sons, 2011. Google Scholar
  15. M. Pilipczuk, S. Siebertz, and Sz. Toruńczyk. On the number of types in sparse graphs. In Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS'18, pages 799-808. ACM, 2018. Google Scholar
  16. F. Reidl and B. D. Sullivan. A color-avoiding approach to subgraph counting in bounded expansion classes. arXiv preprint, 2020. URL: http://arxiv.org/abs/2001.05236.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail