Document Open Access Logo

Correlating Theory and Practice in Finding Clubs and Plexes

Authors Aleksander Figiel, Tomohiro Koana, André Nichterlein, Niklas Wünsche

PDF
Thumbnail PDF

File

LIPIcs.ESA.2023.47.pdf
  • Filesize: 1.06 MB
  • 18 pages

Document Identifiers

Author Details

Aleksander Figiel
  • Algorithmics and Computational Complexity, Technische Universität Berlin, Germany
Tomohiro Koana
  • Algorithmics and Computational Complexity, Technische Universität Berlin, Germany
André Nichterlein
  • Algorithmics and Computational Complexity, Technische Universität Berlin, Germany
Niklas Wünsche
  • Unaffiliated Researcher, Berlin, Germany

Funding

  • Figiel, Aleksander: Supported by the Deutsche Forschungsgemeinschaft (DFG) project MaMu (NI 369/19).
  • Koana, Tomohiro: Supported by the Deutsche Forschungsgemeinschaft (DFG) project DiPa (NI 369/21).

Cite As Get BibTex

Aleksander Figiel, Tomohiro Koana, André Nichterlein, and Niklas Wünsche. Correlating Theory and Practice in Finding Clubs and Plexes. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 47:1-47:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.ESA.2023.47

Abstract

For solving NP-hard problems there is often a huge gap between theoretical guarantees and observed running times on real-world instances. As a first step towards tackling this issue, we propose an approach to quantify the correlation between theoretical and observed running times.
We use two NP-hard problems related to finding large "cliquish" subgraphs in a given graph as demonstration of this measure. More precisely, we focus on finding maximum s-clubs and s-plexes, i. e., graphs of diameter s and graphs where each vertex is adjacent to all but s vertices. Preprocessing based on Turing kernelization is a standard tool to tackle these problems, especially on sparse graphs. We provide a parameterized analysis for the Turing kernelization and demonstrate their usefulness in practice. Moreover, we demonstrate that our measure indeed captures the correlation between these new theoretical and the observed running times.

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • Preprocessing
  • Turing kernelization
  • Pearson correlation coefficient

Metrics

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

Related Versions

Supplementary Materials

References

  1. Maria Teresa Almeida and Filipa D. Carvalho. The k-club problem: new results for k= 3. CIO - Centro de Investigação Operacional, CIO - Working Paper 3/2008, 2008. Google Scholar
  2. Maria Teresa Almeida and Filipa D. Carvalho. An analytical comparison of the lp relaxations of integer models for the k-club problem. European Journal of Operational Research, 232(3):489-498, 2014. URL: https://doi.org/10.1016/j.ejor.2013.08.004.
  3. Balabhaskar Balasundaram, Sergiy Butenko, and Illya V. Hicks. Clique relaxations in social network analysis: The maximum k-plex problem. Operations Research, 59(1):133-142, 2011. URL: https://doi.org/10.1287/opre.1100.0851.
  4. Thomas Bläsius, Tobias Friedrich, David Stangl, and Christopher Weyand. An efficient branch-and-bound solver for hitting set. In Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX '22), pages 209-220. SIAM, 2022. URL: https://doi.org/10.1137/1.9781611977042.17.
  5. Jean-Marie Bourjolly, Gilbert Laporte, and Gilles Pesant. Heuristics for finding k-clubs in an undirected graph. Computers & Operations Research, 27(6):559-569, 2000. Google Scholar
  6. Jean-Marie Bourjolly, Gilbert Laporte, and Gilles Pesant. An exact algorithm for the maximum k-club problem in an undirected graph. European Journal of Operational Research, 138(1):21-28, 2002. URL: https://doi.org/10.1016/S0377-2217(01)00133-3.
  7. Austin Buchanan and Hosseinali Salemi. Parsimonious formulations of low-diameter clusters. Optimization Online Eprints, 2017. Google Scholar
  8. Lijun Chang. Efficient maximum clique computation over large sparse graphs. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD 2019), pages 529-538. ACM, 2019. URL: https://doi.org/10.1145/3292500.3330986.
  9. Maw-Shang Chang, Ling-Ju Hung, Chih-Ren Lin, and Ping-Chen Su. Finding large k-clubs in undirected graphs. Computing, 95(9):739-758, 2013. URL: https://doi.org/10.1007/s00607-012-0263-3.
  10. Jianer Chen, Iyad A. Kanj, and Ge Xia. Improved upper bounds for vertex cover. Theoretical Computer Science, 411(40-42):3736-3756, 2010. URL: https://doi.org/10.1016/j.tcs.2010.06.026.
  11. Alessio Conte, Donatella Firmani, Caterina Mordente, Maurizio Patrignani, and Riccardo Torlone. Cliques are too strict for representing communities: Finding large k-plexes in real networks. In Proceedings of the 26th Italian Symposium on Advanced Database Systems, volume 2161 of CEUR Workshop Proceedings. CEUR-WS.org, 2018. URL: http://ceur-ws.org/Vol-2161/paper41.pdf.
  12. Alessio Conte, Tiziano De Matteis, De Sensi, Roberto Grossi, Andrea Marino, and Luca Versari. D2K: scalable community detection in massive networks via small-diameter k-plexes. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD '18), pages 1272-1281. ACM, 2018. URL: https://doi.org/10.1145/3219819.3220093.
  13. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-21275-3.
  14. David Eppstein, Maarten Löffler, and Darren Strash. Listing all maximal cliques in large sparse real-world graphs. ACM J. Exp. Algorithmics, 18, 2013. URL: https://doi.org/10.1145/2543629.
  15. Sepp Hartung, Christian Komusiewicz, and André Nichterlein. Parameterized algorithmics and computational experiments for finding 2-clubs. Journal of Graph Algorithms and Applications, 19(1):155-190, 2015. URL: https://doi.org/10.7155/jgaa.00352.
  16. Sepp Hartung, Christian Komusiewicz, André Nichterlein, and Ondrej Suchý. On structural parameterizations for the 2-club problem. Discrete Applied Mathematics, 185:79-92, 2015. URL: https://doi.org/10.1016/j.dam.2014.11.026.
  17. Frank Hutter, Holger H. Hoos, and Kevin Leyton-Brown. Automated configuration of mixed integer programming solvers. In Proceedings of the 7th International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR 2010), volume 6140 of Lecture Notes in Computer Science, pages 186-202. Springer, 2010. URL: https://doi.org/10.1007/978-3-642-13520-0_23.
  18. Richard M. Karp. Reducibility among combinatorial problems. In Raymond E. Miller and James W. Thatcher, editors, Complexity of Computer Computations, pages 85-103. Plenum Press, 1972. Google Scholar
  19. Subhash Khot and Venkatesh Raman. Parameterized complexity of finding subgraphs with hereditary properties. Theoretical Computer Science, 289(2):997-1008, 2002. URL: https://doi.org/10.1016/S0304-3975(01)00414-5.
  20. Tomohiro Koana, Christian Komusiewicz, and Frank Sommer. Computing dense and sparse subgraphs of weakly closed graphs. In Procedings of the 31st International Symposium on Algorithms and Computation (ISAAC 2020), pages 20:1-20:17, 2020. URL: https://doi.org/10.4230/LIPIcs.ISAAC.2020.20.
  21. Tomohiro Koana, Viatcheslav Korenwein, André Nichterlein, Rolf Niedermeier, and Philipp Zschoche. Data reduction for maximum matching on real-world graphs: Theory and experiments. ACM Journal of Experimental Algorithmics, 26:1.3:1-1.3:30, 2021. URL: https://doi.org/10.1145/3439801.
  22. Christian Komusiewicz. Multivariate algorithmics for finding cohesive subnetworks. Algorithms, 9(1):21, 2016. URL: https://doi.org/10.3390/a9010021.
  23. Christian Komusiewicz, Falk Hüffner, Hannes Moser, and Rolf Niedermeier. Isolation concepts for efficiently enumerating dense subgraphs. Theoretical Computer Science, 410(38-40):3640-3654, 2009. URL: https://doi.org/10.1016/j.tcs.2009.04.021.
  24. Yajun Lu, Esmaeel Moradi, and Balabhaskar Balasundaram. Correction to: Finding a maximum k-club using the k-clique formulation and canonical hypercube cuts. Optimization Letters, 12(8):1959-1969, 2018. URL: https://doi.org/10.1007/s11590-018-1273-7.
  25. Esmaeel Moradi and Balabhaskar Balasundaram. Finding a maximum k-club using the k-clique formulation and canonical hypercube cuts. Optimization Letters, 12(8):1947-1957, 2018. URL: https://doi.org/10.1007/s11590-015-0971-7.
  26. Todd Mytkowicz, Amer Diwan, Matthias Hauswirth, and Peter F. Sweeney. Producing wrong data without doing anything obviously wrong! In Mary Lou Soffa and Mary Jane Irwin, editors, Proceedings of the 14th International Conference on Architectural Support for Programming Languages and Operating Systems(ASPLOS 2009), pages 265-276. ACM, 2009. URL: https://doi.org/10.1145/1508244.1508275.
  27. Mohammad Javad Naderi, Austin Buchanan, and Jose L. Walteros. Worst-case analysis of clique mips. Mathematical Programming, 195(1):517-551, 2022. URL: https://doi.org/10.1007/s10107-021-01706-2.
  28. F. Mahdavi Pajouh and B. Balasundaram. On inclusionwise maximal and maximum cardinality k-clubs in graphs. Discrete Optimization, 9:84-97, 2012. Google Scholar
  29. Foad Mahdavi Pajouh, Esmaeel Moradi, and Balabhaskar Balasundaram. Detecting large risk-averse 2-clubs in graphs with random edge failures. Annals of Operations Research, 249(1-2):55-73, 2017. URL: https://doi.org/10.1007/s10479-016-2279-0.
  30. Ryan A. Rossi and Nesreen K. Ahmed. The network data repository with interactive graph analytics and visualization. In AAAI, 2015. accessed 01.01.2022. URL: https://networkrepository.com.
  31. Ryan A. Rossi, David F. Gleich, and Assefaw Hadish Gebremedhin. Parallel maximum clique algorithms with applications to network analysis. SIAM J. Sci. Comput., 37(5), 2015. URL: https://doi.org/10.1137/14100018X.
  32. Hosseinali Salemi and Austin Buchanan. Parsimonious formulations for low-diameter clusters. Mathematical Programming Computation, 12(3):493-528, 2020. URL: https://doi.org/10.1007/s12532-020-00175-6.
  33. Alexander Schäfer, Christian Komusiewicz, Hannes Moser, and Rolf Niedermeier. Parameterized computational complexity of finding small-diameter subgraphs. Optimization Letters, 6(5):883-891, 2012. URL: https://doi.org/10.1007/s11590-011-0311-5.
  34. Stephen B Seidman and Brian L Foster. A graph-theoretic generalization of the clique concept. Journal of Mathematical Sociology, 6(1):139-154, 1978. Google Scholar
  35. Darren Strash and Louise Thompson. Effective data reduction for the vertex clique cover problem. In Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX '22), pages 41-53. SIAM, 2022. URL: https://doi.org/10.1137/1.9781611977042.4.
  36. Svyatoslav Trukhanov, Chitra Balasubramaniam, Balabhaskar Balasundaram, and Sergiy Butenko. Algorithms for detecting optimal hereditary structures in graphs, with application to clique relaxations. Computational Optimization and Applications, 56(1):113-130, 2013. URL: https://doi.org/10.1007/s10589-013-9548-5.
  37. Alexander Veremyev, Oleg A. Prokopyev, and Eduardo L. Pasiliao. Critical nodes for distance‐based connectivity and related problems in graphs. Networks, 66, 2015. URL: https://doi.org/10.1002/net.21622.
  38. Anurag Verma, Austin Buchanan, and Sergiy Butenko. Solving the maximum clique and vertex coloring problems on very large sparse networks. INFORMS J. Comput., 27(1):164-177, 2015. URL: https://doi.org/10.1287/ijoc.2014.0618.
  39. Jose L. Walteros and Austin Buchanan. Why is maximum clique often easy in practice? Operations Research, 68(6):1866-1895, 2020. URL: https://doi.org/10.1287/opre.2019.1970.
  40. Qinghua Wu and Jin-Kao Hao. A review on algorithms for maximum clique problems. European Journal of Operational Research, 242(3):693-709, 2015. URL: https://doi.org/10.1016/j.ejor.2014.09.064.
  41. Mingyu Xiao and Hiroshi Nagamochi. Exact algorithms for maximum independent set. Information and Computation, 255:126-146, 2017. URL: https://doi.org/10.1016/j.ic.2017.06.001.
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 About DROPS Imprint Privacy Contact