## Rolling backwards can move you forward: on embedding problems in sparse expanders

Metadata only

Date

2021-01Type

- Conference Paper

ETH Bibliography

yes
Altmetrics

Abstract

We develop a general embedding method based on the Friedman-Pippenger tree embedding technique (1987) and its algorithmic version, essentially due to Aggarwal et al. (1996), enhanced with a roll-back idea allowing to sequentially retrace previously performed embedding steps. This proves to be a powerful tool for embedding graphs of large girth into expander graphs. As an application of this method, we settle two problems:
• For a graph H, we denote by Hq the graph obtained from H by subdividing its edges with q−1 vertices each. We show that the k-size-Ramsey number [EQUATION] satisfies [EQUATION] for every bounded degree graph H on n vertices and for q = Ω(log n), which is optimal up to a constant factor. This settles a conjecture of Pak (2002).
• We give a deterministic, polynomial time algorithm for finding vertex-disjoint paths between given pairs of vertices in a strong expander graph. More precisely, let G be an (n, d, λ)-graph with λ = O(d1−ε), and let P be any collection of at most [EQUATION] disjoint pairs of vertices in G for some small constant c, such that in the neighborhood of every vertex in G there are at most d/4 vertices from P. Then there exists a polynomial time algorithm which finds vertex-disjoint paths between every pair in P, and each path is of the same length [EQUATION]. Both the number of pairs and the length of the paths are optimal up to a constant factor; the result answers the offline version of a question of Alon and Capalbo (2007). Show more

Publication status

publishedExternal links

Book title

Proceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '21)Pages / Article No.

Publisher

SIAMEvent

Organisational unit

03993 - Sudakov, Benjamin / Sudakov, Benjamin
Notes

Conference lecture held on January 10, 2021More

Show all metadata
ETH Bibliography

yes
Altmetrics