---
_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.
accept: '1'
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: *Proceedings of the 46th International Colloquium on Automata, Languages,
and Programming*. Vol 132. LIPIcs. Dagstuhl Publishing; 2019:150:1--150:14.
doi:10.4230/LIPICS.ICALP.2019.150'
apa: 'Scheideler, C., & Setzer, A. (2019). On the Complexity of Local Graph
Transformations. In *Proceedings of the 46th International Colloquium on Automata,
Languages, and Programming* (Vol. 132, pp. 150:1--150:14). Patras, Greece:
Dagstuhl Publishing. https://doi.org/10.4230/LIPICS.ICALP.2019.150'
bibtex: '@inproceedings{Scheideler_Setzer_2019, series={LIPIcs}, title={On the Complexity
of Local Graph Transformations}, volume={132}, DOI={10.4230/LIPICS.ICALP.2019.150},
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 *Proceedings of the 46th International Colloquium
on Automata, Languages, and Programming*, 132:150:1--150:14. LIPIcs. Dagstuhl
Publishing, 2019. https://doi.org/10.4230/LIPICS.ICALP.2019.150.
ieee: C. Scheideler and A. Setzer, “On the Complexity of Local Graph Transformations,”
in *Proceedings of the 46th International Colloquium on Automata, Languages,
and Programming*, Patras, Greece, 2019, vol. 132, pp. 150:1--150:14.
mla: Scheideler, Christian, and Alexander Setzer. “On the Complexity of Local Graph
Transformations.” *Proceedings of the 46th International Colloquium on Automata,
Languages, and Programming*, vol. 132, Dagstuhl Publishing, 2019, pp. 150:1--150:14,
doi:10.4230/LIPICS.ICALP.2019.150.
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: 2019-11-25T14:28:43Z
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
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'
...