Skip to main content

Retracting graphs to cycles

Publication ,  Conference
Haney, S; Liaee, M; Maggs, BM; Panigrahi, D; Rajaraman, R; Sundaram, R
Published in: Leibniz International Proceedings in Informatics, LIPIcs
July 1, 2019

We initiate the algorithmic study of retracting a graph into a cycle in the graph, which seeks a mapping of the graph vertices to the cycle vertices so as to minimize the maximum stretch of any edge, subject to the constraint that the restriction of the mapping to the cycle is the identity map. This problem has its roots in the rich theory of retraction of topological spaces, and has strong ties to well-studied metric embedding problems such as minimum bandwidth and 0-extension. Our first result is an O(min{k, n})-approximation for retracting any graph on n nodes to a cycle with k nodes. We also show a surprising connection to Sperner's Lemma that rules out the possibility of improving this result using certain natural convex relaxations of the problem. Nevertheless, if the problem is restricted to planar graphs, we show that we can overcome these integrality gaps by giving an optimal combinatorial algorithm, which is the technical centerpiece of the paper. Building on our planar graph algorithm, we also obtain a constant-factor approximation algorithm for retraction of points in the Euclidean plane to a uniform cycle.

Duke Scholars

Published In

Leibniz International Proceedings in Informatics, LIPIcs

DOI

ISSN

1868-8969

Publication Date

July 1, 2019

Volume

132

Related Subject Headings

  • 46 Information and computing sciences
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Haney, S., Liaee, M., Maggs, B. M., Panigrahi, D., Rajaraman, R., & Sundaram, R. (2019). Retracting graphs to cycles. In Leibniz International Proceedings in Informatics, LIPIcs (Vol. 132). https://doi.org/10.4230/LIPIcs.ICALP.2019.70
Haney, S., M. Liaee, B. M. Maggs, D. Panigrahi, R. Rajaraman, and R. Sundaram. “Retracting graphs to cycles.” In Leibniz International Proceedings in Informatics, LIPIcs, Vol. 132, 2019. https://doi.org/10.4230/LIPIcs.ICALP.2019.70.
Haney S, Liaee M, Maggs BM, Panigrahi D, Rajaraman R, Sundaram R. Retracting graphs to cycles. In: Leibniz International Proceedings in Informatics, LIPIcs. 2019.
Haney, S., et al. “Retracting graphs to cycles.” Leibniz International Proceedings in Informatics, LIPIcs, vol. 132, 2019. Scopus, doi:10.4230/LIPIcs.ICALP.2019.70.
Haney S, Liaee M, Maggs BM, Panigrahi D, Rajaraman R, Sundaram R. Retracting graphs to cycles. Leibniz International Proceedings in Informatics, LIPIcs. 2019.

Published In

Leibniz International Proceedings in Informatics, LIPIcs

DOI

ISSN

1868-8969

Publication Date

July 1, 2019

Volume

132

Related Subject Headings

  • 46 Information and computing sciences