License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2018.35
URN: urn:nbn:de:0030-drops-94988
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9498/
Go to the corresponding LIPIcs Volume Portal

Ghosh, Arijit ; Kolay, Sudeshna ; Mishra, Gopinath

FPT Algorithms for Embedding into Low Complexity Graphic Metrics

pdf-format:
LIPIcs-ESA-2018-35.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{ghosh_et_al:LIPIcs:2018:9498,
  author =	{Arijit Ghosh and Sudeshna Kolay and Gopinath Mishra},
  title =	{{FPT Algorithms for Embedding into Low Complexity Graphic Metrics}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{35:1--35:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-081-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{112},
  editor =	{Yossi Azar and Hannah Bast and Grzegorz Herman},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9498},
  URN =		{urn:nbn:de:0030-drops-94988},
  doi =		{10.4230/LIPIcs.ESA.2018.35},
  annote =	{Keywords: Metric spaces, metric embedding, FPT, dynamic programming}
}

Keywords: Metric spaces, metric embedding, FPT, dynamic programming
Collection: 26th Annual European Symposium on Algorithms (ESA 2018)
Issue Date: 2018
Date of publication: 14.08.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI