Document Open Access Logo

On the Size and the Approximability of Minimum Temporally Connected Subgraphs

Authors Kyriakos Axiotis, Dimitris Fotakis

PDF

File

Thumbnail PDF
PDF
LIPIcs.ICALP.2016.149.pdf
  • Filesize: 0.53 MB
  • 14 pages

Document Identifiers

Subject Classification

Keywords
  • Temporal Graphs
  • Temporal Connectivity
  • Approximation Algorithms

Metrics

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

Abstract

We consider temporal graphs with discrete time labels and investigate the size and the approximability of minimum temporally connected spanning subgraphs. We present a family of minimally connected temporal graphs with n vertices and Omega(n^2) edges, thus resolving an open question of (Kempe, Kleinberg, Kumar, JCSS 64, 2002) about the existence of sparse temporal connectivity certificates. Next, we consider the problem of computing a minimum weight subset of temporal edges that preserve connectivity of a given temporal graph either from a given vertex r (r-MTC problem) or among all vertex pairs (MTC problem). We show that the approximability of r-MTC is closely related to the approximability of Directed Steiner Tree and that r-MTC can be solved in polynomial time if the underlying graph has bounded treewidth. We also show that the best approximation ratio for MTC is at least O(2^{log^{1-epsilon}(n)} and at most O(min{n^{1+epsilon},(Delta*M)^{2/3+epsilon}), for any constant epsilon > 0, where M is the number of temporal edges and Delta is the maximum degree of the underlying graph. Furthermore, we prove that the unweighted version of MTC is APX-hard and that MTC is efficiently solvable in trees and 2-approximable in cycles.

Cite As Get BibTex

Kyriakos Axiotis and Dimitris Fotakis. On the Size and the Approximability of Minimum Temporally Connected Subgraphs. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 149:1-149:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ICALP.2016.149

Author Details

Kyriakos Axiotis
Dimitris Fotakis

References

  1. E.C. Akrida, L. Gąsieniec, G.B. Mertzios, and P.G. Spirakis. On Temporally Connected Graphs of Small Cost. In Proc. of the 13th Workshop on Approximation and Online Algorithms (WAOA'15), volume 9499 of LNCS, pages 84-96, 2015. Google Scholar
  2. E.C. Akrida, L. Gąsieniec, G.B. Mertzios, and P.G. Spirakis. Ephemeral networks with random availability of links: The case of fast networks. Journal of Parallel and Distributed Computing, 87:109-120, 2016. Google Scholar
  3. K.A. Berman. Vulnerability of scheduled networks and a generalization of Menger’s Theorem. Networks, 28(3):125-134, 1996. Google Scholar
  4. M.W. Bern and P.E. Plassmann. The Steiner Problem with Edge Lengths 1 and 2. Information Processing Letters, 32(4):171-176, 1989. Google Scholar
  5. K. Bhawalkar, S. Gollapudi, and K. Munagala. Coevolutionary opinion formation games. In Proc. of the 45th ACM Symposium on Theory of Computing (STOC'13), pages 41-50, 2013. Google Scholar
  6. A. Casteigts, P. Flocchini, W. Quattrociocchi, and N. Santoro. Time-varying graphs and dynamic networks. International Journal of Parallel, Emergent and Distributed Systems (IJPEDS), 27(5):387-408, 2012. Google Scholar
  7. M. Charikar, C. Chekuri, T.-Y. Cheung, Z. Dai, A. Goel, S. Guha, and M. Li. Approximation algorithms for directed steiner problems. Journal of Algorithms, 33(1):73-91, 1999. Google Scholar
  8. M. Charikar, M. Hajiaghayi, and H.J. Karloff. Improved Approximation Algorithms for Label Cover Problems. Algorithmica, 61(1):190-206, 2011. Google Scholar
  9. B. Chazelle. The dynamics of influence systems. In Proc. of the 53rd IEEE Symposium on Foundations of Computer Science (FOCS'12), pages 311-320, 2012. Google Scholar
  10. Y. Dodis and S. Khanna. Design Networks with Bounded Pairwise Distance. In Proc. of the 31st ACM Symposium on Theory of Computing (STOC'99), pages 750-759, 1999. Google Scholar
  11. R.G. Downey and M.R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. Google Scholar
  12. C. Dutta, G. Pandurangan, R. Rajaraman, Z. Sun, and E.Viola. On the Complexity of Information Spreading in Dynamic Networks. In Proc. of the 24th ACM-SIAM Symposium on Discrete Algorithms (SODA'13), pages 717-736, 2013. Google Scholar
  13. T. Erlebach, M. Hoffmann, and F. Kammer. On temporal graph exploration. In Proc. of the 42nd International Colloquium on Automata, Languages and Programming (ICALP'15), volume 9134 of LNCS, pages 444-455, 2015. Google Scholar
  14. M. Feldman, G. Kortsarz, and Z. Nutov. Improved approximation algorithms for Directed Steiner Forest. Journal of Computer and System Sciences, 78(1):279-292, 2012. Google Scholar
  15. L. Foschini, J. Hershberger, and S. Suri. On the Complexity of Time-Dependent Shortest Paths. Algorithmica, 68(4):1075-1097, 2014. Google Scholar
  16. E. Halperin and R. Krauthgamer. Polylogarithmic inapproximability. In Proc. of the 35th ACM Symposium on Theory of Computing (STOC'03), pages 585-594, 2003. Google Scholar
  17. P. Holme and J. Saramäki. Temporal Networks. Physics Reports, 519(3):97-125, 2012. Google Scholar
  18. S. Huang, A.W.-C. Fu, and R. Liu. Minimum Spanning Trees in Temporal Graphs. In Proc. of the 2015 ACM International Conference on Management of Data (SIGMOD'15), pages 419-430, 2015. Google Scholar
  19. D. Kempe, J.M. Kleinberg, and A. Kumar. Connectivity and Inference Problems for Temporal Networks. Journal of Computer and System Sciences, 64(4):820-842, 2002. Google Scholar
  20. F. Kuhn, N.A. Lynch, and R.Oshman. Distributed computation in dynamic networks. In Proc. of the 42nd ACM Symposium on Theory of Computing (STOC'10), pages 513-522, 2010. Google Scholar
  21. G.B. Mertzios, O. Michail, I. Chatzigiannakis, and P.G. Spirakis. Temporal network optimization subject to connectivity constraints. In Proc. of the 40th International Colloquium on Automata, Languages and Programming (ICALP'13), volume 7966 of LNCS, pages 657-668, 2013. Google Scholar
  22. R. O'Dell and R. Wattenhofer. Information dissemination in highly dynamic graphs. In Proc. of the DIALM-POMC Joint Workshop on Foundations of Mobile Computing (DIALM-POMC'05), pages 104-110, 2005. Google Scholar
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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact