---
_id: '10586'
abstract:
- lang: eng
  text: 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.
author:
- first_name: Christian
  full_name: Scheideler, Christian
  id: '20792'
  last_name: Scheideler
- first_name: Alexander
  full_name: Setzer, Alexander
  id: '11108'
  last_name: Setzer
citation:
  ama: 'Scheideler C, Setzer A. On the Complexity of Local Graph Transformations.
    In: <i>Proceedings of the 46th International Colloquium on Automata, Languages,
    and Programming</i>. Vol 132. LIPIcs. Dagstuhl Publishing; 2019:150:1--150:14.
    doi:<a href="https://doi.org/10.4230/LIPICS.ICALP.2019.150">10.4230/LIPICS.ICALP.2019.150</a>'
  apa: 'Scheideler, C., &#38; Setzer, A. (2019). On the Complexity of Local Graph
    Transformations. In <i>Proceedings of the 46th International Colloquium on Automata,
    Languages, and Programming</i> (Vol. 132, pp. 150:1--150:14). Patras, Greece:
    Dagstuhl Publishing. <a href="https://doi.org/10.4230/LIPICS.ICALP.2019.150">https://doi.org/10.4230/LIPICS.ICALP.2019.150</a>'
  bibtex: '@inproceedings{Scheideler_Setzer_2019, series={LIPIcs}, title={On the Complexity
    of Local Graph Transformations}, volume={132}, DOI={<a href="https://doi.org/10.4230/LIPICS.ICALP.2019.150">10.4230/LIPICS.ICALP.2019.150</a>},
    booktitle={Proceedings of the 46th International Colloquium on Automata, Languages,
    and Programming}, publisher={Dagstuhl Publishing}, author={Scheideler, Christian
    and Setzer, Alexander}, year={2019}, pages={150:1--150:14}, collection={LIPIcs}
    }'
  chicago: Scheideler, Christian, and Alexander Setzer. “On the Complexity of Local
    Graph Transformations.” In <i>Proceedings of the 46th International Colloquium
    on Automata, Languages, and Programming</i>, 132:150:1--150:14. LIPIcs. Dagstuhl
    Publishing, 2019. <a href="https://doi.org/10.4230/LIPICS.ICALP.2019.150">https://doi.org/10.4230/LIPICS.ICALP.2019.150</a>.
  ieee: C. Scheideler and A. Setzer, “On the Complexity of Local Graph Transformations,”
    in <i>Proceedings of the 46th International Colloquium on Automata, Languages,
    and Programming</i>, Patras, Greece, 2019, vol. 132, pp. 150:1--150:14.
  mla: Scheideler, Christian, and Alexander Setzer. “On the Complexity of Local Graph
    Transformations.” <i>Proceedings of the 46th International Colloquium on Automata,
    Languages, and Programming</i>, vol. 132, Dagstuhl Publishing, 2019, pp. 150:1--150:14,
    doi:<a href="https://doi.org/10.4230/LIPICS.ICALP.2019.150">10.4230/LIPICS.ICALP.2019.150</a>.
  short: 'C. Scheideler, A. Setzer, in: Proceedings of the 46th International Colloquium
    on Automata, Languages, and Programming, Dagstuhl Publishing, 2019, pp. 150:1--150:14.'
conference:
  end_date: 2019-07-12
  location: Patras, Greece
  name: ICALP 2019
  start_date: 2019-07-09
date_created: 2019-07-08T17:19:01Z
date_updated: 2022-01-06T06:50:45Z
ddc:
- '004'
department:
- _id: '79'
doi: 10.4230/LIPICS.ICALP.2019.150
file:
- access_level: closed
  content_type: application/pdf
  creator: ups
  date_created: 2019-08-26T09:21:27Z
  date_updated: 2019-08-26T09:21:27Z
  file_id: '12955'
  file_name: LIPIcs-ICALP-2019-150.pdf
  file_size: 537649
  relation: main_file
  success: 1
file_date_updated: 2019-08-26T09:21:27Z
has_accepted_license: '1'
intvolume: '       132'
keyword:
- Graphs transformations
- NP-hardness
- approximation algorithms
language:
- iso: eng
page: 150:1--150:14
project:
- _id: '1'
  name: SFB 901
- _id: '5'
  name: SFB 901 - Subproject A1
- _id: '2'
  name: SFB 901 - Project Area A
publication: Proceedings of the 46th International Colloquium on Automata, Languages,
  and Programming
publication_status: published
publisher: Dagstuhl Publishing
series_title: LIPIcs
status: public
title: On the Complexity of Local Graph Transformations
type: conference
user_id: '477'
volume: 132
year: '2019'
...