Document Open Access Logo

Minimizing and Computing the Inverse Geodesic Length on Trees

Authors Serge Gaspers , Joshua Lau

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2019.59.pdf
  • Filesize: 0.56 MB
  • 19 pages

Document Identifiers

Author Details

Serge Gaspers
  • UNSW Sydney, Australia
  • Data61, CSIRO, Sydney, Australia
Joshua Lau
  • UNSW Sydney, Australia

Funding

  • Gaspers, Serge: Serge Gaspers is the recipient of an Australian Research Council (ARC) Future Fellowship (FT140100048).

Acknowledgements

We thank David Harvey and Ray Li for fruitful discussions and feedback.

Cite AsGet BibTex

Serge Gaspers and Joshua Lau. Minimizing and Computing the Inverse Geodesic Length on Trees. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 59:1-59:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ISAAC.2019.59

Abstract

For any fixed measure H that maps graphs to real numbers, the MinH problem is defined as follows: given a graph G, an integer k, and a target tau, is there a set S of k vertices that can be deleted, so that H(G - S) is at most tau? In this paper, we consider the MinH problem on trees. We call H balanced on trees if, whenever G is a tree, there is an optimal choice of S such that the components of G - S have sizes bounded by a polynomial in n / k. We show that MinH on trees is Fixed-Parameter Tractable (FPT) for parameter n / k, and furthermore, can be solved in subexponential time, and polynomial space, whenever H is additive, balanced on trees, and computable in polynomial time. A particular measure of interest is the Inverse Geodesic Length (IGL), which is used to gauge the efficiency and connectedness of a graph. It is defined as the sum of inverse distances between every two vertices: IGL(G) = sum_{{u,v} subseteq V} 1/d_G(u,v). While MinIGL is W[1]-hard for parameter treewidth, and cannot be solved in 2^{o(k + n + m)} time, even on bipartite graphs with n vertices and m edges, the complexity status of the problem remains open in the case where G is a tree. We show that IGL is balanced on trees, to give a 2^O((n log n)^(5/6)) time, polynomial space algorithm. The distance distribution of G is the sequence {a_i} describing the number of vertex pairs distance i apart in G: a_i = |{{u, v}: d_G(u, v) = i}|. Given only the distance distribution, one can easily determine graph parameters such as diameter, Wiener index, and particularly, the IGL. We show that the distance distribution of a tree can be computed in O(n log^2 n) time by reduction to polynomial multiplication. We also extend the result to graphs with small treewidth by showing that the first p values of the distance distribution can be computed in 2^(O(tw(G))) n^(1 + epsilon) sqrt(p) time, and the entire distance distribution can be computed in 2^(O(tw(G))) n^{1 + epsilon} time, when the diameter of G is O(n^epsilon') for every epsilon' > 0.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Trees
  • Mathematics of computing → Graph algorithms
Keywords
  • Trees
  • Treewidth
  • Fixed-Parameter Tractability
  • Inverse Geodesic Length
  • Vertex deletion
  • Polynomial multiplication
  • Distance distribution

Metrics

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

Related Versions

References

  1. Amir Abboud, Virginia Vassilevska Williams, and Joshua R. Wang. Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016), pages 377-391. SIAM, 2016. URL: https://doi.org/10.1137/1.9781611974331.ch28.
  2. Karla Atkins, Jiangzhuo Chen, V. S. Anil Kumar, and Achla Marathe. The structure of electrical networks: a graph theory based analysis. International Journal of Computational Intelligence Systems, 5(3):265-284, 2009. URL: https://doi.org/10.1504/IJCIS.2009.024874.
  3. Haris Aziz, Serge Gaspers, Edward J. Lee, and Kamran Najeebullah. Defender Stackelberg Game with Inverse Geodesic Length as Utility Metric. In Proceedings of the 17th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2018), pages 694-702. ACM, 2018. Google Scholar
  4. Haris Aziz, Serge Gaspers, and Kamran Najeebullah. Weakening Covert Networks by Minimizing Inverse Geodesic Length. In Proceedings of the 26th International Joint Conference on Artificial Intelligence, (IJCAI 2017), pages 779-785. IJCAI, 2017. URL: https://doi.org/10.24963/ijcai.2017/108.
  5. Alex Bavelas. Communication Patterns in Task-Oriented Groups. The Journal of the Acoustical Society of America, 22(6):725-730, 1950. URL: https://doi.org/10.1121/1.1906679.
  6. Jon Louis Bentley. Multidimensional divide-and-conquer. Communications of the ACM, 23(4):214-229, 1980. URL: https://doi.org/10.1145/358841.358850.
  7. Davide Bilò, Feliciano Colella, Luciano Gualà, Stefano Leucci, and Guido Proietti. A faster computation of all the best swap edges of a tree spanner. In Proceedings of the 22nd International Colloquium on Structural Information and Communication Complexity (SIROCCO 2015), volume 9439 of LNCS, pages 239-253. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-25258-2_17.
  8. Manuel Blum, Robert W. Floyd, Vaughan Pratt, Ronald L. Rivest, and Robert E. Tarjan. Time bounds for selection. Journal of Computer and System Sciences, 7(4):448-461, 1973. URL: https://doi.org/10.1016/S0022-0000(73)80033-9.
  9. Csaba Böde, István A. Kovács, Máté S. Szalay, Robin Palotai, Tamás Korcsmáros, and Péter Csermely. Network analysis of protein dynamics. FEBS Letters, 581(15):2776-2782, 2007. URL: https://doi.org/10.1016/j.febslet.2007.05.021.
  10. Hans L. Bodlaender, Pål Grønås Drange, Markus S. Dregi, Fedor V. Fomin, Daniel Lokshtanov, and Michal Pilipczuk. A c^k n 5-Approximation Algorithm for Treewidth. SIAM Journal on Computing, 45(2):317-378, 2016. URL: https://doi.org/10.1137/130947374.
  11. Karl Bringmann, Thore Husfeldt, and Måns Magnusson. Multivariate Analysis of Orthogonal Range Searching and Graph Distances. In 13th International Symposium on Parameterized and Exact Computation (IPEC 2018), volume 115 of Leibniz International Proceedings in Informatics (LIPIcs), pages 4:1-4:13, Dagstuhl, Germany, 2019. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.IPEC.2018.4.
  12. Sergio Cabello and Christian Knauer. Algorithms for graphs of bounded treewidth via orthogonal range searching. Computational Geometry: Theory and Applications, 42(9):815-824, 2009. URL: https://doi.org/10.1016/j.comgeo.2009.02.001.
  13. Timothy M. Chan and Mihai Pǎtraşcu. Counting inversions, offline orthogonal range counting, and related problems. In Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2010), pages 161-173. SIAM, 2010. URL: https://doi.org/10.1137/1.9781611973075.15.
  14. Paolo Crucitti, Vito Latora, Massimo Marchiori, and Andrea Rapisarda. Efficiency of scale-free networks: error and attack tolerance. Physica A: Statistical Mechanics and its Applications, 320:622-642, 2003. URL: https://doi.org/10.1016/S0378-4371(02)01545-5.
  15. Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-21275-3.
  16. David Dagon, Guofei Gu, Christopher P. Lee, and Wenke Lee. A Taxonomy of Botnet Structures. In Proceedings of the 23rd Annual Computer Security Applications Conference (ACSAC 2007), pages 325-339. IEEE Computer Society, 2007. URL: https://doi.org/10.1109/ACSAC.2007.44.
  17. Philippe Flajolet and Robert Sedgewick. Analytic Combinatorics. Cambridge University Press, 1st edition, 2009. Google Scholar
  18. Martin Fürer. Faster Integer Multiplication. SIAM Journal on Computing, 39(3):979-1005, 2009. URL: https://doi.org/10.1137/070711761.
  19. Martin Fürer. How fast can we multiply large integers on an actual computer? In Proceedings of the 11th Latin American Symposium on Theoretical Informatics (LATIN 2014), volume 8392 of LNCS, pages 660-670. Springer, 2014. URL: https://doi.org/10.1007/978-3-642-54423-1_57.
  20. Murad Hossain, Sameer Alam, Tim Rees, and Hussein Abbass. Australian Airport Network Robustness Analysis : A Complex Network Approach. In Proceedings of the 36th Australasian Transport Research Forum (ATRF 2013), pages 1-21, 2013. Google Scholar
  21. Thore Husfeldt. Computing Graph Distances Parameterized by Treewidth and Diameter. In Proceedings of the 11th International Symposium on Parameterized and Exact Computation (IPEC 2016), volume 63 of LIPIcs, pages 16:1-16:11. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. URL: https://doi.org/10.4230/LIPICS.IPEC.2016.16.
  22. Russell Impagliazzo and Ramamohan Paturi. On the Complexity of k-SAT. Journal of Computer and System Sciences, 62(2):367-375, 2001. URL: https://doi.org/10.1006/JCSS.2000.1727.
  23. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? Journal of Computer and System Sciences, 63(4):512-530, 2001. URL: https://doi.org/10.1006/jcss.2001.1774.
  24. Camille Jordan. Sur Les Assemblages des Lignes. Journal für die Reine und Angewandte Mathematik, 70:185-190, 1869. Google Scholar
  25. István A. Kovács and Albert-László Barabási. Destruction perfected. Nature, 524(7563):38-39, 2015. URL: https://doi.org/10.1038/524038a.
  26. Leopold Kronecker. Grundzüge einer arithmetischen Theorie der algebraischen Grössen. G. Reimer, 1882. Google Scholar
  27. Silviu Maniu, Pierre Senellart, and Suraj Jog. An Experimental Study of the Treewidth of Real-World Graph Data. In 22nd International Conference on Database Theory (ICDT 2019), volume 127 of Leibniz International Proceedings in Informatics (LIPIcs), pages 12:1-12:18, 2019. URL: https://doi.org/10.4230/LIPIcs.ICDT.2019.12.
  28. Louis Monier. Combinatorial solutions of multidimensional divide-and-conquer recurrences. Journal of Algorithms, 1(1):60-74, 1980. URL: https://doi.org/10.1016/0196-6774(80)90005-X.
  29. Flaviano Morone and Hernán A. Makse. Influence maximization in complex networks through optimal percolation. Nature, 524(7563):65-68, 2015. URL: https://doi.org/10.1038/nature14604.
  30. Kamran Najeebullah. Complexity of Optimally Attacking and Defending a Network. PhD thesis, UNSW Sydney, 2018. Google Scholar
  31. Léon Planken, Mathijs de Weerdt, and Roman van der Krogt. Computing All-Pairs Shortest Paths by Leveraging Low Treewidth. Journal of Artificial Intelligence Research, 43:353-388, 2012. URL: https://doi.org/10.1613/jair.3509.
  32. A. Schönhage and V. Strassen. Schnelle Multiplikation großer Zahlen. Computing, 7(3-4):281-292, 1971. URL: https://doi.org/10.1007/BF02242355.
  33. Ian Michael Shamos. Computational geometry. PhD thesis, Yale University, 1978. Google Scholar
  34. Piotr L. Szczepański, Tomasz P. Michalak, and Talal Rahwan. Efficient algorithms for game-theoretic betweenness centrality. Artificial Intelligence, 231:39-63, 2016. URL: https://doi.org/10.1016/j.artint.2015.11.001.
  35. Kevin Topley. Computationally Efficient Bounds for the Sum of Catalan Numbers. Technical Report 1601.04223, ArXiv, 2016. URL: http://arxiv.org/abs/1601.04223.
  36. Alexander Veremyev, Oleg A. Prokopyev, and Eduardo L. Pasiliao. Critical nodes for distance-based connectivity and related problems in graphs. Networks, 66(3):170-195, 2015. URL: https://doi.org/10.1002/net.21622.
  37. Harry Wiener. Structural Determination of Paraffin Boiling Points. Journal of the American Chemical Society, 69(1):17-20, 1947. URL: https://doi.org/10.1021/ja01193a005.
  38. Ryan Williams. A New Algorithm for Optimal Constraint Satisfaction and Its Implications. In Proceedings of the 31st International Colloquium on Automata, Languages and Programming (ICALP 2004), volume 3142 of LNCS, pages 1227-1237. Springer, 2004. URL: https://doi.org/10.1007/978-3-540-27836-8_101.
  39. Bo Zhou, Xiaochun Cai, and Nenad Trinajstić. On Harary index. Journal of Mathematical Chemistry, 44(2):611-618, 2008. URL: https://doi.org/10.1007/s10910-007-9339-2.
  40. Yihai Zhu, Jun Yan, Yan Sun, and Haibo He. Revealing cascading failure vulnerability in power grids using risk-graph. IEEE Transactions on Parallel and Distributed Systems, 25(12):3274-3284, 2014. URL: https://doi.org/10.1109/TPDS.2013.2295814.
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