Document Open Access Logo

Optimal Centrality Computations Within Bounded Clique-Width Graphs

Author Guillaume Ducoffe

PDF
Thumbnail PDF

File

LIPIcs.IPEC.2021.16.pdf
  • Filesize: 0.72 MB
  • 16 pages

Document Identifiers

Author Details

Guillaume Ducoffe
  • National Institute for Research and Development in Informatics, Bucharest, Romania
  • University of Bucharest, Romania

Funding

This work was supported by project PN-19-37-04-01 "New solutions for complex problems in current ICT research fields based on modelling and optimization", funded by the Romanian Core Program of the Ministry of Research and Innovation (MCI) 2019-2022.

Cite AsGet BibTex

Guillaume Ducoffe. Optimal Centrality Computations Within Bounded Clique-Width Graphs. In 16th International Symposium on Parameterized and Exact Computation (IPEC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 214, pp. 16:1-16:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.IPEC.2021.16

Abstract

Given an n-vertex m-edge graph G of clique-width at most k, and a corresponding k-expression, we present algorithms for computing some well-known centrality indices (eccentricity and closeness) that run in O(2^{O(k)}(n+m)^{1+ε}) time for any ε > 0. Doing so, we can solve various distance problems within the same amount of time, including: the diameter, the center, the Wiener index and the median set. Our run-times match conditional lower bounds of Coudert et al. (SODA'18) under the Strong Exponential-Time Hypothesis. On our way, we get a distance-labeling scheme for n-vertex m-edge graphs of clique-width at most k, using O(klog²{n}) bits per vertex and constructible in Õ(k(n+m)) time from a given k-expression. Doing so, we match the label size obtained by Courcelle and Vanicat (DAM 2016), while we considerably improve the dependency on k in their scheme. As a corollary, we get an Õ(kn²)-time algorithm for computing All-Pairs Shortest-Paths on n-vertex graphs of clique-width at most k, being given a k-expression. This partially answers an open question of Kratsch and Nelles (STACS'20). Our algorithms work for graphs with non-negative vertex-weights, under two different types of distances studied in the literature. For that, we introduce a new type of orthogonal range query as a side contribution of this work, that might be of independent interest.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
  • Theory of computation → Fixed parameter tractability
  • Theory of computation → Shortest paths
Keywords
  • Clique-width
  • Centralities computation
  • Facility Location problems
  • Distance-labeling scheme
  • Fine-grained complexity in P
  • Graph theory

Metrics

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

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 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 377-391. SIAM, 2016. URL: https://doi.org/10.1137/1.9781611974331.ch28.
  2. John Adrian Bondy and Uppaluri Siva Ramachandra Murty. Graph theory, volume 244 of Graduate Texts in Mathematics. Springer-Verlag London, 2008. Google Scholar
  3. R Borie, JL Johnson, V Raghavan, and JP Spinrad. Robust polynomial time algorithms on clique-width k graphs. 2002. Google Scholar
  4. Andreas Brandstädt, Konrad K Dabrowski, Shenwei Huang, and Daniël Paulusma. Bounding the clique-width of H-free split graphs. Discrete Applied Mathematics, 211:30-39, 2016. Google Scholar
  5. Andreas Brandstädt, Konrad K Dabrowski, Shenwei Huang, and Daniël Paulusma. Bounding the Clique-Width of H-Free Chordal Graphs. Journal of Graph Theory, 86(1):42-77, 2017. Google Scholar
  6. Andreas Brandstädt, Feodor F Dragan, Hoàng-Oanh Le, and Raffaele Mosca. New graph classes of bounded clique-width. Theory of Computing Systems, 38(5):623-645, 2005. Google Scholar
  7. Andreas Brandstadt, Joost Engelfriet, Hoang-Oanh Le, and Vadim V Lozin. Clique-width for 4-vertex forbidden subgraphs. Theory of Computing Systems, 39(4):561-590, 2006. Google Scholar
  8. Andreas Brandstädt, Tilo Klembt, and Suhail Mahfud. P₆-and triangle-free graphs revisited: structure and bounded clique-width. Discrete Mathematics & Theoretical Computer Science, 8(1), 2006. Google Scholar
  9. Andreas Brandstädt, Hoàng-Oanh Le, and Raffaele Mosca. Gem-and co-gem-free graphs have bounded clique-width. International Journal of Foundations of Computer Science, 15(01):163-185, 2004. Google Scholar
  10. Andreas Brandstädt, Hoàng-Oanh Le, and Raffaele Mosca. Chordal co-gem-free and (P₅, gem)-free graphs have bounded clique-width. Discrete Applied Mathematics, 145(2):232-241, 2005. Google Scholar
  11. K. Bringmann, T. Husfeldt, and M. Magnusson. Multivariate Analysis of Orthogonal Range Searching and Graph Distances. Algorithmica, pages 1-24, 2020. Google Scholar
  12. S. Cabello. Computing the inverse geodesic length in planar graphs and graphs of bounded treewidth. Technical Report 1908.01317, arXiv, 2019. Google Scholar
  13. S. Cabello and C. Knauer. Algorithms for graphs of bounded treewidth via orthogonal range searching. Computational Geometry, 42(9):815-824, 2009. Google Scholar
  14. Derek G. Corneil, Michel Habib, Jean-Marc Lanlignel, Bruce Reed, and Udi Rotics. Polynomial Time Recognition of Clique-Width ≤ 3 Graphs. In Latin American Theoretical INformatics Symposium (LATIN), volume 1776 of Lecture Notes in Computer Science, pages 126-134. Springer, 2000. URL: https://doi.org/10.1007/10719839_14.
  15. Derek G. Corneil and Udi Rotics. On the relationship between clique-width and treewidth. SIAM Journal on Computing, 34(4):825-847, 2005. URL: https://doi.org/10.1137/S0097539701385351.
  16. D. Coudert, G. Ducoffe, and A. Popa. Fully polynomial FPT algorithms for some classes of bounded clique-width graphs. ACM Transactions on Algorithms (TALG), 15(3):1-57, 2019. Google Scholar
  17. Bruno Courcelle. The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Information and Computation, 85(1):12-75, 1990. URL: https://doi.org/10.1016/0890-5401(90)90043-H.
  18. Bruno Courcelle, Pinar Heggernes, Daniel Meister, Charis Papadopoulos, and Udi Rotics. A characterisation of clique-width through nested partitions. Discrete Applied Mathematics, 187:70-81, 2015. URL: https://doi.org/10.1016/j.dam.2015.02.016.
  19. Bruno Courcelle, Johann A. Makowsky, and Udi Rotics. Linear time solvable optimization problems on graphs of bounded clique-width. Theory of Computing Systems, 33(2):125-150, 2000. URL: https://doi.org/10.1007/s002249910009.
  20. Bruno Courcelle and Rémi Vanicat. Query efficient implementation of graphs of bounded clique-width. Discrete Applied Mathematics, 131(1):129-150, 2003. Google Scholar
  21. William H. Cunningham. Decomposition of directed graphs. SIAM Journal on Algebraic Discrete Methods, 3(2):214-228, 1982. URL: https://doi.org/10.1137/0603021.
  22. Konrad K Dabrowski and Daniël Paulusma. Classifying the clique-width of H-free bipartite graphs. Discrete Applied Mathematics, 200:43-51, 2016. Google Scholar
  23. Konrad K Dabrowski and Daniël Paulusma. Clique-width of graph classes defined by two forbidden induced subgraphs. The Computer Journal, 59(5):650-666, 2016. Google Scholar
  24. K. Das, S. Samanta, and M. Pal. Study on centrality measures in social networks: a survey. Social network analysis and mining, 8(1):1-11, 2018. Google Scholar
  25. Reinhard Diestel. Graph Theory. Graduate Texts in Mathematics. Springer, 2010. 4th edition. URL: https://doi.org/10.1007/978-3-662-53622-3.
  26. Feodor F Dragan and Chenyu Yan. Collective tree spanners in graphs with bounded parameters. Algorithmica, 57(1):22-43, 2010. Google Scholar
  27. Guillaume Ducoffe and Alexandru Popa. The b-matching problem in distance-hereditary graphs and beyond. In International Symposium on Algorithms and Computation (ISAAC), volume 123 of Leibniz International Proceedings in Informatics, pages 30:1-30:13. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.ISAAC.2018.30.
  28. Guillaume Ducoffe and Alexandru Popa. The use of a pruned modular decomposition for maximum matching algorithms on some graph classes. In International Symposium on Algorithms and Computation (ISAAC), volume 123 of Leibniz International Proceedings in Informatics, pages 6:1-6:13. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.ISAAC.2018.6.
  29. Wolfgang Espelage, Frank Gurski, and Egon Wanke. How to solve NP-hard graph problems on clique-width bounded graphs in polynomial time. In International Workshop on Graph-Theoretic Concepts in Computer Science (WG), volume 1 of Lecture Notes in Computer Science, pages 117-128. Springer, 2001. URL: https://doi.org/10.1007/3-540-45477-2_12.
  30. Michael R. Fellows, Frances A. Rosamond, Udi Rotics, and Stefan Szeider. Clique-width is NP-complete. SIAM Journal on Discrete Mathematics, 23(2):909-939, 2009. URL: https://doi.org/10.1137/070687256.
  31. Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, and Saket Saurabh. Intractability of clique-width parameterizations. SIAM Journal on Computing, 39(5):1941-1956, 2010. URL: https://doi.org/10.1137/080742270.
  32. Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, and Saket Saurabh. Almost optimal lower bounds for problems parameterized by clique-width. SIAM Journal on Computing, 43(5):1541-1563, 2014. URL: https://doi.org/10.1137/130910932.
  33. Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi. Clique-width III: Hamiltonian Cycle and the Odd Case of Graph Coloring. ACM Transactions on Algorithms, 15(1):9, 2019. URL: https://doi.org/10.1145/3280824.
  34. Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, Michal Pilipczuk, and Marcin Wrochna. Fully polynomial-time parameterized computations for graphs and matrices of low treewidth. ACM Transactions on Algorithms, 14(3):34:1-34:45, 2018. URL: https://doi.org/10.1145/3186898.
  35. Martin Fürer. A natural generalization of bounded tree-width and bounded clique-width. In Latin American Symposium on Theoretical Informatics, pages 72-83. Springer, 2014. Google Scholar
  36. C. Gavoille, D. Peleg, S. Pérennes, and R. Raz. Distance labeling in graphs. Journal of Algorithms, 53(1):85-112, 2004. Google Scholar
  37. Cyril Gavoille and Christophe Paul. Distance labeling scheme and split decomposition. Discrete Mathematics, 273(1-3):115-130, 2003. Google Scholar
  38. Archontia C. Giannopoulou, George B. Mertzios, and Rolf Niedermeier. Polynomial fixed-parameter algorithms: A case study for longest path on interval graphs. Theoretical computer science, 689:67-95, 2017. URL: https://doi.org/10.1016/j.tcs.2017.05.017.
  39. A. Goldman. Optimal center location in simple networks. Transportation science, 5(2):212-221, 1971. Google Scholar
  40. Martin Charles Golumbic and Udi Rotics. On the clique-width of some perfect graph classes. International Journal of Foundations of Computer Science, 11(03):423-443, 2000. URL: https://doi.org/10.1142/S0129054100000260.
  41. P. Hage and F. Harary. Eccentricity and centrality in networks. Social networks, 17(1):57-63, 1995. Google Scholar
  42. Torben Hagerup, Jyrki Katajainen, Naomi Nishimura, and Prabhakar Ragde. Characterizing multiterminal flow networks and computing flows in networks of small treewidth. Journal of Computer and System Sciences, 57(3):366-375, 1998. Google Scholar
  43. Dov Harel and Robert Endre Tarjan. Fast algorithms for finding nearest common ancestors. SIAM Journal on Computing, 13(2):338-355, 1984. Google Scholar
  44. Yoichi Iwata, Tomoaki Ogasawara, and Naoto Ohsaka. On the power of tree-depth for fully polynomial FPT algorithms. In International Symposium on Theoretical Aspects of Computer Science (STACS), volume 96 of Leibniz International Proceedings in Informatics, pages 41:1-41:14. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.STACS.2018.41.
  45. Shahin Kamali. Compact representation of graphs of small clique-width. Algorithmica, 80(7):2106-2131, 2018. Google Scholar
  46. Stefan Kratsch and Florian Nelles. Efficient and adaptive parameterized algorithms on modular decompositions. In European Symposia on Algorithms (ESA), pages 55:1-55:15, 2018. URL: https://doi.org/10.4230/LIPIcs.ESA.2018.55.
  47. Stefan Kratsch and Florian Nelles. Efficient Parameterized Algorithms for Computing All-Pairs Shortest Paths. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020), volume 154 of Leibniz International Proceedings in Informatics (LIPIcs), pages 38:1-38:15, Dagstuhl, Germany, 2020. Schloss Dagstuhl-Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.STACS.2020.38.
  48. V Lozin and Dieter Rautenbach. Chordal bipartite graphs of bounded tree-and clique-width. Discrete Mathematics, 283(1-3):151-158, 2004. Google Scholar
  49. Johann A. Makowsky and Udi Rotics. On the clique-width of graphs with few P₄’s. International Journal of Foundations of Computer Science, 10(03):329-348, 1999. URL: https://doi.org/10.1142/S0129054199000241.
  50. S. Oum and P. Seymour. Approximating clique-width and branch-width. Journal of Combinatorial Theory, Series B, 96(4):514-528, 2006. Google Scholar
  51. Michaël Rao. Clique-width of graphs defined by one-vertex extensions. Discrete Mathematics, 308(24):6157-6165, 2008. URL: https://doi.org/10.1016/j.disc.2007.11.039.
  52. G. Sabidussi. The centrality index of a graph. Psychometrika, 31(4):581-603, 1966. Google Scholar
  53. Karol Suchan and Ioan Todinca. On powers of graphs of bounded NLC-width (clique-width). Discrete Applied Mathematics, 155(14):1885-1893, 2007. Google Scholar
  54. Jean-Marie Vanherpe. Clique-width of partner-limited graphs. Discrete mathematics, 276(1-3):363-374, 2004. 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-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact