[{"file_date_updated":"2019-08-26T09:21:27Z","date_updated":"2019-11-25T14:28:43Z","publication":"Proceedings of the 46th International Colloquium on Automata, Languages, and Programming","language":[{"iso":"eng"}],"doi":"10.4230/LIPICS.ICALP.2019.150","author":[{"first_name":"Christian","last_name":"Scheideler","id":"20792","full_name":"Scheideler, Christian"},{"first_name":"Alexander","last_name":"Setzer","id":"11108","full_name":"Setzer, Alexander"}],"conference":{"name":"ICALP 2019","start_date":"2019-07-09","location":"Patras, Greece","end_date":"2019-07-12"},"volume":132,"_id":"10586","keyword":["Graphs transformations","NP-hardness","approximation algorithms"],"title":"On the Complexity of Local Graph Transformations","file":[{"file_name":"LIPIcs-ICALP-2019-150.pdf","date_updated":"2019-08-26T09:21:27Z","date_created":"2019-08-26T09:21:27Z","creator":"ups","success":1,"file_id":"12955","content_type":"application/pdf","access_level":"closed","file_size":537649,"relation":"main_file"}],"publication_status":"published","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."}],"date_created":"2019-07-08T17:19:01Z","accept":"1","ddc":["004"],"status":"public","type":"conference","year":"2019","department":[{"_id":"79"}],"publisher":"Dagstuhl Publishing","project":[{"_id":"1","name":"SFB 901"},{"name":"SFB 901 - Subproject A1","_id":"5"},{"name":"SFB 901 - Project Area A","_id":"2"}],"intvolume":" 132","page":"150:1--150:14","user_id":"477","citation":{"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} }","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.","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.","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","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.","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","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."},"series_title":"LIPIcs"},{"date_created":"2019-03-01T11:56:55Z","issue":"5-6","status":"public","oa":1,"type":"journal_article","department":[{"_id":"596"}],"year":"2014","intvolume":" 14","extern":"1","page":"517-540","citation":{"short":"S. Gharibian, J. Kempe, Quantum Information & Computation 14 (2014) 517–540.","apa":"Gharibian, S., & Kempe, J. (2014). Hardness of approximation for quantum problems. *Quantum Information & Computation*, *14*(5–6), 517–540.","mla":"Gharibian, Sevag, and Julia Kempe. “Hardness of Approximation for Quantum Problems.” *Quantum Information & Computation*, vol. 14, no. 5–6, 2014, pp. 517–40.","ama":"Gharibian S, Kempe J. Hardness of approximation for quantum problems. *Quantum Information & Computation*. 2014;14(5-6):517-540.","bibtex":"@article{Gharibian_Kempe_2014, title={Hardness of approximation for quantum problems}, volume={14}, number={5–6}, journal={Quantum Information & Computation}, author={Gharibian, Sevag and Kempe, Julia}, year={2014}, pages={517–540} }","chicago":"Gharibian, Sevag, and Julia Kempe. “Hardness of Approximation for Quantum Problems.” *Quantum Information & Computation* 14, no. 5–6 (2014): 517–40.","ieee":"S. Gharibian and J. Kempe, “Hardness of approximation for quantum problems,” *Quantum Information & Computation*, vol. 14, no. 5–6, pp. 517–540, 2014."},"user_id":"71541","article_type":"original","external_id":{"arxiv":["1209.1055"]},"date_updated":"2019-03-06T22:00:44Z","publication":"Quantum Information & Computation","language":[{"iso":"eng"}],"author":[{"id":"71541","full_name":"Gharibian, Sevag","last_name":"Gharibian","first_name":"Sevag","orcid":"0000-0002-9992-3379"},{"last_name":"Kempe","first_name":"Julia","full_name":"Kempe, Julia"}],"main_file_link":[{"url":"https://arxiv.org/abs/1209.1055","open_access":"1"}],"volume":14,"_id":"8171","keyword":["Hardness of approximation","polynomial time hierarchy","succinct set cover","quantum complexity"],"title":"Hardness of approximation for quantum problems","publication_status":"published","abstract":[{"text":"The polynomial hierarchy plays a central role in classical complexity theory. Here, we define\r\na quantum generalization of the polynomial hierarchy, and initiate its study. We show that\r\nnot only are there natural complete problems for the second level of this quantum hierarchy, but that these problems are in fact hard to approximate. Using the same techniques, we\r\nalso obtain hardness of approximation for the class QCMA. Our approach is based on the\r\nuse of dispersers, and is inspired by the classical results of Umans regarding hardness of approximation for the second level of the classical polynomial hierarchy [Umans, FOCS 1999].\r\nThe problems for which we prove hardness of approximation for include, among others, a\r\nquantum version of the Succinct Set Cover problem, and a variant of the local Hamiltonian\r\nproblem with hybrid classical-quantum ground states.","lang":"eng"}]}]