Document Open Access Logo

On the Complexity of Local Graph Transformations

Authors Christian Scheideler , Alexander Setzer

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2019.150.pdf
  • Filesize: 0.51 MB
  • 14 pages

Document Identifiers

Author Details

Christian Scheideler
  • Paderborn University, Germany
Alexander Setzer
  • Paderborn University, Germany

Funding

This work was supported by the German Research Foundation (DFG) within the Collaborative Research Center "On-The-Fly Computing" (SFB 901) under Grant No.: GZ SFB 901/02.

Cite AsGet BibTex

Christian Scheideler and Alexander Setzer. On the Complexity of Local Graph Transformations. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 150:1-150:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ICALP.2019.150

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Problems, reductions and completeness
  • Theory of computation → Approximation algorithms analysis
Keywords
  • Graphs transformations
  • NP-hardness
  • approximation algorithms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Ajit Agrawal, Philip N. Klein, and R. Ravi. When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks. SIAM J. Comput., 24(3):440-456, 1995. URL: http://dx.doi.org/10.1137/S0097539792236237.
  2. Susanne Albers, Stefan Eilts, Eyal Even-Dar, Yishay Mansour, and Liam Roditty. On nash equilibria for a network creation game. In Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2006, Miami, Florida, USA, January 22-26, 2006, pages 89-98, 2006. Google Scholar
  3. Noga Alon, Erik D. Demaine, Mohammad Taghi Hajiaghayi, and Tom Leighton. Basic Network Creation Games. SIAM J. Discrete Math., 27(2):656-668, 2013. URL: http://dx.doi.org/10.1137/090771478.
  4. Marc Andries, Gregor Engels, Annegret Habel, Berthold Hoffmann, Hans-Jörg Kreowski, Sabine Kuske, Detlef Plump, Andy Schürr, and Gabriele Taentzer. Graph Transformation for Specification and Programming. Sci. Comput. Program., 34(1):1-54, 1999. URL: http://dx.doi.org/10.1016/S0167-6423(98)00023-9.
  5. James Aspnes and Yinghua Wu. O(logn)-Time Overlay Network Construction from Graphs with Out-Degree 1. In Proceedings of the 11th International Conference on Principles of Distributed Systems, (OPODIS '07), pages 286-300, 2007. Google Scholar
  6. Azrina Abd Aziz, Y. Ahmet Sekercioglu, Paul G. Fitzpatrick, and Milosh V. Ivanovich. A Survey on Distributed Topology Control Techniques for Extending the Lifetime of Battery Powered Wireless Sensor Networks. IEEE Communications Surveys and Tutorials, 15(1):121-144, 2013. URL: http://dx.doi.org/10.1109/SURV.2012.031612.00124.
  7. Andrew Berns, Sukumar Ghosh, and Sriram V. Pemmaraju. Building self-stabilizing overlay networks with the transitive closure framework. Theor. Comput. Sci., 512:2-14, 2013. Google Scholar
  8. Davide Bilò, Luciano Gualà, Stefano Leucci, and Guido Proietti. Locality-Based Network Creation Games. TOPC, 3(1):6:1-6:26, 2016. URL: http://dx.doi.org/10.1145/2938426.
  9. Stephen A. Cook. The Complexity of Theorem-proving Procedures. In Proceedings of the Third Annual ACM Symposium on Theory of Computing, STOC '71, pages 151-158, New York, NY, USA, 1971. ACM. URL: http://dx.doi.org/10.1145/800157.805047.
  10. Andreas Cord-Landwehr, Martina Hüllmann, Peter Kling, and Alexander Setzer. Basic Network Creation Games with Communication Interests. In Algorithmic Game Theory - 5th International Symposium, SAGT 2012, Barcelona, Spain, October 22-23, 2012. Proceedings, pages 72-83, 2012. URL: http://dx.doi.org/10.1007/978-3-642-33996-7_7.
  11. Erik D. Demaine, MohammadTaghi Hajiaghayi, Hamid Mahini, and Morteza Zadimoghaddam. The price of anarchy in network creation games. In Proceedings of the Twenty-Sixth Annual ACM Symposium on Principles of Distributed Computing, PODC 2007, Portland, Oregon, USA, August 12-15, 2007, pages 292-298, 2007. URL: http://dx.doi.org/10.1145/1281100.1281142.
  12. Shlomi Dolev and Ronen I. Kat. HyperTree for self-stabilizing peer-to-peer systems. Distributed Computing, 20(5):375-388, 2008. Google Scholar
  13. Hartmut Ehrig, Hans-Jörg Kreowski, Ugo Montanari, and Grzegorz Rozenberg, editors. Handbook of Graph Grammars and Computing by Graph Transformations, Volume 3: Concurrency, Parallelism, and Distribution. World Scientific, 1999. Google Scholar
  14. Alex Fabrikant, Ankur Luthra, Elitza N. Maneva, Christos H. Papadimitriou, and Scott Shenker. On a network creation game. In Proceedings of the Twenty-Second ACM Symposium on Principles of Distributed Computing, PODC 2003, Boston, Massachusetts, USA, July 13-16, 2003, pages 347-351, 2003. URL: http://dx.doi.org/10.1145/872035.872088.
  15. Michael Feldmann, Christina Kolb, Christian Scheideler, and Thim Strothmann. Self-Stabilizing Supervised Publish-Subscribe Systems. In 2018 IEEE International Parallel and Distributed Processing Symposium, IPDPS 2018, Vancouver, BC, Canada, May 21-25, 2018, pages 1050-1059, 2018. URL: http://dx.doi.org/10.1109/IPDPS.2018.00114.
  16. M. Goemans and D. Williamson. A General Approximation Technique for Constrained Forest Problems. SIAM Journal on Computing, 24(2):296-317, 1995. URL: http://dx.doi.org/10.1137/S0097539793242618.
  17. Martin Groß, Anupam Gupta, Amit Kumar, Jannik Matuschke, Daniel R. Schmidt, Melanie Schmidt, and José Verschae. A Local-Search Algorithm for Steiner Forest. In Anna R. Karlin, editor, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018), volume 94 of Leibniz International Proceedings in Informatics (LIPIcs), pages 31:1-31:17, Dagstuhl, Germany, 2018. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: http://dx.doi.org/10.4230/LIPIcs.ITCS.2018.31.
  18. Anupam Gupta and Amit Kumar. Greedy Algorithms for Steiner Forest. In Proceedings of the Forty-seventh Annual ACM Symposium on Theory of Computing, STOC '15, pages 871-878, New York, NY, USA, 2015. ACM. URL: http://dx.doi.org/10.1145/2746539.2746590.
  19. Yair Halevi and Yishay Mansour. A Network Creation Game with Nonuniform Interests. In Internet and Network Economics, Third International Workshop, WINE 2007, San Diego, CA, USA, December 12-14, 2007, Proceedings, pages 287-292, 2007. URL: http://dx.doi.org/10.1007/978-3-540-77105-0_28.
  20. Reiko Heckel. Graph Transformation in a Nutshell. Electr. Notes Theor. Comput. Sci., 148(1):187-198, 2006. URL: http://dx.doi.org/10.1016/j.entcs.2005.12.018.
  21. Riko Jacob, Andréa W. Richa, Christian Scheideler, Stefan Schmid, and Hanjo Täubig. SKIP^+: A Self-Stabilizing Skip Graph. J. ACM, 61(6):36:1-36:26, 2014. URL: http://dx.doi.org/10.1145/2629695.
  22. Riko Jacob, Stephan Ritscher, Christian Scheideler, and Stefan Schmid. Towards higher-dimensional topological self-stabilization: A distributed algorithm for Delaunay graphs. Theor. Comput. Sci., 457:137-148, 2012. Google Scholar
  23. Kamal Jain. A Factor 2 Approximation Algorithm for the Generalized Steiner Network Problem. Combinatorica, 21(1):39-60, 2001. URL: http://dx.doi.org/10.1007/s004930170004.
  24. Kishore Kothapalli and Christian Scheideler. Supervised Peer-to-Peer Systems. In 8th International Symposium on Parallel Architectures, Algorithms, and Networks, ISPAN 2005, December 7-9. 2005, Las Vegas, Nevada, USA, pages 188-193, 2005. URL: http://dx.doi.org/10.1109/ISPAN.2005.81.
  25. Andreas Koutsopoulos, Christian Scheideler, and Thim Strothmann. Towards a universal approach for the finite departure problem in overlay networks. Inf. Comput., 255:408-424, 2017. URL: http://dx.doi.org/10.1016/j.ic.2016.12.006.
  26. Leonid Anatolevich Levin. Universal sequential search problems. Problemy Peredachi Informatsii, 9(3):115-116, 1973. Google Scholar
  27. Mo Li, Zhenjiang Li, and Athanasios V. Vasilakos. A Survey on Topology Control in Wireless Sensor Networks: Taxonomy, Comparative Study, and Open Issues. Proceedings of the IEEE, 101(12):2538-2557, 2013. URL: http://dx.doi.org/10.1109/JPROC.2013.2257631.
  28. Chih-Long Lin. Hardness of Approximating Graph Transformation Problem. In Algorithms and Computation, 5th International Symposium, ISAAC '94, Beijing, P. R. China, August 25-27, 1994, Proceedings, pages 74-82, 1994. URL: http://dx.doi.org/10.1007/3-540-58325-4_168.
  29. Rizal Mohd Nor, Mikhail Nesterenko, and Christian Scheideler. Corona: A stabilizing deterministic message-passing skip list. Theor. Comput. Sci., 512:119-129, 2013. URL: http://dx.doi.org/10.1016/j.tcs.2012.08.029.
  30. Ram Ramanathan and Regina Hain. Topology Control of Multihop Wireless Networks Using Transmit Power Adjustment. In Proceedings IEEE INFOCOM 2000, The Conference on Computer Communications, Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies, Reaching the Promised Land of Communications, Tel Aviv, Israel, March 26-30, 2000, pages 404-413, 2000. URL: http://dx.doi.org/10.1109/INFCOM.2000.832213.
  31. Grzegorz Rozenberg, editor. Handbook of Graph Grammars and Computing by Graph Transformations, Volume 1: Foundations. World Scientific, 1997. Google Scholar
  32. Christian Scheideler and Alexander Setzer. On the Complexity of Local Graph Transformations (full version), 2019. URL: http://arxiv.org/abs/1904.11395.
  33. Stefan Schmid, Chen Avin, Christian Scheideler, Michael Borokhovich, Bernhard Haeupler, and Zvi Lotker. SplayNet: Towards Locally Self-Adjusting Networks. IEEE/ACM Trans. Netw., 24(3):1421-1433, 2016. URL: http://dx.doi.org/10.1109/TNET.2015.2410313.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact