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.ICALP.2019.150
URN: urn:nbn:de:0030-drops-107266
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10726/
Go to the corresponding LIPIcs Volume Portal

Scheideler, Christian ; Setzer, Alexander

On the Complexity of Local Graph Transformations

pdf-format:
LIPIcs-ICALP-2019-150.pdf (0.5 MB)

Abstract

We consider the problem of transforming a given graph G_s into a desired graph G_t by applying a minimum number of primitives from a particular set of local graph transformation primitives. These primitives are local in the sense that each node can apply them based on local knowledge and by affecting only its 1-neighborhood. Although the specific set of primitives we consider makes it possible to transform any (weakly) connected graph into any other (weakly) connected graph consisting of the same nodes, they cannot disconnect the graph or introduce new nodes into the graph, making them ideal in the context of supervised overlay network transformations. We prove that computing a minimum sequence of primitive applications (even centralized) for arbitrary G_s and G_t is NP-hard, which we conjecture to hold for any set of local graph transformation primitives satisfying the aforementioned properties. On the other hand, we show that this problem admits a polynomial time algorithm with a constant approximation ratio.

BibTeX - Entry

@InProceedings{scheideler_et_al:LIPIcs:2019:10726,
  author =	{Christian Scheideler and Alexander Setzer},
  title =	{{On the Complexity of Local Graph Transformations}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{150:1--150:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10726},
  URN =		{urn:nbn:de:0030-drops-107266},
  doi =		{10.4230/LIPIcs.ICALP.2019.150},
  annote =	{Keywords: Graphs transformations, NP-hardness, approximation algorithms}
}

Keywords: Graphs transformations, NP-hardness, approximation algorithms
Collection: 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Issue Date: 2019
Date of publication: 04.07.2019

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