Document Open Access Logo

FPT Algorithms for Embedding into Low Complexity Graphic Metrics

Authors Arijit Ghosh, Sudeshna Kolay, Gopinath Mishra

PDF
Thumbnail PDF

File

LIPIcs.ESA.2018.35.pdf
  • Filesize: 499 kB
  • 13 pages

Document Identifiers

Author Details

Arijit Ghosh
  • The Institute of Mathematical Sciences, HBNI, Chennai, India
Sudeshna Kolay
  • Eindhoven University of Technology, Eindhoven, Netherlands
Gopinath Mishra
  • Indian Statistical Institute, Kolkata, India

Cite As Get BibTex

Arijit Ghosh, Sudeshna Kolay, and Gopinath Mishra. FPT Algorithms for Embedding into Low Complexity Graphic Metrics. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 35:1-35:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ESA.2018.35

Abstract

The Metric Embedding problem takes as input two metric spaces (X,D_X) and (Y,D_Y), and a positive integer d. The objective is to determine whether there is an embedding F:X - > Y such that the distortion d_{F} <= d. Such an embedding is called a distortion d embedding. In parameterized complexity, the Metric Embedding problem is known to be W-hard and therefore, not expected to have an FPT algorithm. In this paper, we consider the Gen-Graph Metric Embedding problem, where the two metric spaces are graph metrics. We explore the extent of tractability of the problem in the parameterized complexity setting. We determine whether an unweighted graph metric (G,D_G) can be embedded, or bijectively embedded, into another unweighted graph metric (H,D_H), where the graph H has low structural complexity. For example, H is a cycle, or H has bounded treewidth or bounded connected treewidth. The parameters for the algorithms are chosen from the upper bound d on distortion, bound Delta on the maximum degree of H, treewidth alpha of H, and the connected treewidth alpha_{c} of H.
Our general approach to these problems can be summarized as trying to understand the behavior of the shortest paths in G under a low distortion embedding into H, and the structural relation the mapping of these paths has to shortest paths in H.

Subject Classification

ACM Subject Classification
  • Theory of computation → Fixed parameter tractability
Keywords
  • Metric spaces
  • metric embedding
  • FPT
  • dynamic programming

Metrics

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

Related Versions

References

  1. I. Abraham, Y. Bartal, and O. Neiman. Advances in metric embedding theory. Advances in Mathematics, 228(6):3026-3126, 2011. Google Scholar
  2. M. Badoiu, J. Chuzhoy, P. Indyk, and A. Sidiropoulos. Low-Distortion Embeddings of General Metrics into the Line. In Proc. of STOC, pages 225-233, 2005. Google Scholar
  3. M. Badoiu, K. Dhamdhere, A. Gupta, Y. Rabinovich, H. Räcke, R. Ravi, and A. Sidiropoulos. Approximation Algorithms for Low-Distortion Embeddings into Low-Dimensional spaces. In Proc. of SODA, pages 119-128, 2005. Google Scholar
  4. T. Carpenter, F. V. Fomin, D. Lokshtanov, S. Saurabh, and A. Sidiropoulos. Algorithms for low-distortion embeddings into arbitrary 1-dimensional spaces. CoRR, abs/1712.06747, 2017. To appear in SoCG, 2018. Google Scholar
  5. M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh. Parameterized algorithms. Springer, 5(4):16:1-16:20, 2015. Google Scholar
  6. Reinhard Diestel and Malte Müller. Connected tree-width. Combinatorica, 2017. Google Scholar
  7. M. R. Fellows, F. V. Fomin, D. Lokshtanov, E. Losievskaja, F. A. Rosamond, and S. Saurabh. Distortion is Fixed Parameter Tractable. ACM Transactions on Computation Theory, 5(4):16:1-16:20, 2013. Google Scholar
  8. A. Ghosh, S. Kolay, and G. Mishra. FPT algorithms for embedding into low complexity graphic metrics. CoRR, 2018. URL: http://arxiv.org/abs/1801.03253.
  9. A. Gupta, I. Newman, Y. Rabinovich, and A. Sinclair. Cuts, Trees and l₁-Embeddings of Graphs. Combinatorica, 24(2):233-269, 2004. Google Scholar
  10. P. Indyk. Algorithmic Applications of Low-Distortion Geometric Embeddings. In Proc. of FOCS 2001, pages 10-33, 2001. Google Scholar
  11. P. Indyk and J. Matoušek. Low-Distortion Embeddings of Finite Metric Spaces. In Handbook of Discrete and Computational Geometry, Second Edition., pages 177-196. CRC, 2004. Google Scholar
  12. C. Kenyon, Y. Rabani, and A. Sinclair. Low Distortion Maps Between Point Sets. SIAM Journal on Computing, 39(4):1617-1636, 2010. Peliminary version in Proc. of STOC, 2004. Google Scholar
  13. N. Linial, E. London, and Y. Rabinovich. The Geometry of Graphs and Some of its Algorithmic Applications. Combinatorica, 15(2):215-245, 1995. Google Scholar
  14. J. Matoušek. Lectures on Discrete Geometry. Springer-Verlag New York, Inc., 2002. Google Scholar
  15. J. Matoušek. Lecture Notes on Metric Embeddings, 2013. Google Scholar
  16. A. Nayyeri and B. Raichel. Reality Distortion: Exact and Approximate Algorithms for Embedding into the Line. In Proc. of FOCS, pages 729-747, 2015. Google Scholar
  17. A. Nayyeri and B. Raichel. A Treehouse with Custom Windows: Minimum Distortion Embeddings into Bounded Treewidth Graphs. In Proc. of SODA, pages 724-736, 2017. Google Scholar
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact