Document Open Access Logo

Targeted Branching for the Maximum Independent Set Problem

Authors Demian Hespe , Sebastian Lamm , Christian Schorr

PDF
Thumbnail PDF

File

LIPIcs.SEA.2021.17.pdf
  • Filesize: 0.8 MB
  • 21 pages

Document Identifiers

Author Details

Demian Hespe
  • Karlsruhe Institute of Technology, Institute for Theoretical Informatics, Germany
Sebastian Lamm
  • Karlsruhe Institute of Technology, Institute for Theoretical Informatics, Germany
Christian Schorr
  • Karlsruhe Institute of Technology, Institute for Theoretical Informatics, Germany

Cite AsGet BibTex

Demian Hespe, Sebastian Lamm, and Christian Schorr. Targeted Branching for the Maximum Independent Set Problem. In 19th International Symposium on Experimental Algorithms (SEA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 190, pp. 17:1-17:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.SEA.2021.17

Abstract

Finding a maximum independent set is a fundamental NP-hard problem that is used in many real-world applications. Given an unweighted graph, this problem asks for a maximum cardinality set of pairwise non-adjacent vertices. In recent years, some of the most successful algorithms for solving this problem are based on the branch-and-bound or branch-and-reduce paradigms. In particular, branch-and-reduce algorithms, which combine branch-and-bound with reduction rules, have been able to achieve substantial results, solving many previously infeasible real-world instances. These results were to a large part achieved by developing new, more practical reduction rules. However, other components that have been shown to have a significant impact on the performance of these algorithms have not received as much attention. One of these is the branching strategy, which determines what vertex is included or excluded in a potential solution. Even now, the most commonly used strategy selects vertices solely based on their degree and does not take into account other factors that contribute to the performance of the algorithm. In this work, we develop and evaluate several novel branching strategies for both branch-and-bound and branch-and-reduce algorithms. Our strategies are based on one of two approaches which are motivated by existing research. They either (1) aim to decompose the graph into two or more connected components which can then be solved independently, or (2) try to remove vertices that hinder the application of a reduction rule which can lead to smaller graphs. Our experimental evaluation on a large set of real-world instances indicates that our strategies are able to improve the performance of the state-of-the-art branch-and-reduce algorithm by Akiba and Iwata. To be more specific, our reduction-based packing branching rule is able to outperform the default branching strategy of selecting a vertex of highest degree on 65% of all instances tested. Furthermore, our decomposition-based strategy based on edge cuts is able to achieve a speedup of 2.29 on sparse networks (1.22 on all instances).

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
  • Theory of computation → Branch-and-bound
  • Mathematics of computing → Combinatorial optimization
Keywords
  • Graphs
  • Combinatorial Optimization
  • Independent Set
  • Vertex Cover
  • Clique
  • Branch-and-Reduce
  • Branch-and-Bound
  • Data Reduction

Metrics

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

Related Versions

Supplementary Materials

References

  1. Takuya Akiba and Yoichi Iwata. Branch-and-reduce exponential/FPT algorithms in practice: A case study of vertex cover. Theoretical Computer Science, 609:211-225, 2016. URL: https://doi.org/10.1016/j.tcs.2015.09.023.
  2. Maram Alsahafy and Lijun Chang. Computing maximum independent sets over large sparse graphs. In International Conference on Web Information Systems Engineering, pages 711-727. Springer, 2020. Google Scholar
  3. Nicolas Bourgeois, Bruno Escoffier, Vangelis Th. Paschos, and Johan M. M. van Rooij. Fast algorithms for max independent set. Algorithmica, 62(1-2):382-415, 2012. URL: https://doi.org/10.1007/s00453-010-9460-7.
  4. Sergiy Butenko and Wilbert E Wilhelm. Clique-detection models in computational biochemistry and genomics. European Journal of Operational Research, 173(1):1-17, 2006. Google Scholar
  5. Randy Carraghan and Panos M. Pardalos. An exact algorithm for the maximum clique problem. Operations Research Letters, 9(6):375–382, 1990. URL: https://doi.org/10.1016/0167-6377(90)90057-C.
  6. Lijun Chang, Wei Li, and Wenjie Zhang. Computing A near-maximum independent set in linear time by reducing-peeling. In Proceedings of the 2017 ACM International Conference on Management of Data, pages 1181-1196. ACM, 2017. URL: https://doi.org/10.1145/3035918.3035939.
  7. 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.
  8. Tammy M. K. Cheng, Yu-En Lu, Michele Vendruscolo, Pietro Liò, and Tom L. Blundell. Prediction by graph theoretic measures of structural effects in proteins arising from non-synonymous single nucleotide polymorphisms. PLoS Computational Biology, 4(7), 2008. URL: https://doi.org/10.1371/journal.pcbi.1000135.
  9. Jakob Dahlum, Sebastian Lamm, Peter Sanders, Christian Schulz, Darren Strash, and Renato F Werneck. Accelerating local search for the maximum independent set problem. In International symposium on experimental algorithms, pages 118-133. Springer, 2016. Google Scholar
  10. Camil Demetrescu, Andrew V Goldberg, and David S Johnson. The Shortest Path Problem: Ninth DIMACS Implementation Challenge, volume 74. American Mathematical Soc., 2009. Google Scholar
  11. Elizabeth D Dolan and Jorge J Moré. Benchmarking optimization software with performance profiles. Mathematical programming, 91(2):201-213, 2002. Google Scholar
  12. M. Ayaz Dzulfikar, Johannes K. Fichte, and Markus Hecher. The PACE 2019 Parameterized Algorithms and Computational Experiments Challenge: The Fourth Iteration. In 14th International Symposium on Parameterized and Exact Computation (IPEC 2019), volume 148, pages 25:1-25:23, 2019. URL: https://doi.org/10.4230/LIPIcs.IPEC.2019.25.
  13. Fedor V. Fomin, Fabrizio Grandoni, and Dieter Kratsch. A measure & conquer approach for the analysis of exact algorithms. J. ACM, 56(5):25:1-25:32, 2009. URL: https://doi.org/10.1145/1552285.1552286.
  14. Jian Gao, Jiejiang Chen, Minghao Yin, Rong Chen, and Yiyuan Wang. An exact algorithm for maximum k-plexes in massive graphs. In IJCAI, pages 1449-1455, 2018. Google Scholar
  15. M. R. Garey, D. S. Johnson, and L. Stockmeyer. Some Simplified NP-Complete Problems. In Proceedings of the 6th ACM Symposium on Theory of Computing, STOC '74, pages 47-63. ACM, 1974. Google Scholar
  16. Alan George. Nested dissection of a regular finite element mesh. SIAM Journal on Numerical Analysis, 10(2):345-363, 1973. Google Scholar
  17. Andrew V Goldberg and Robert E Tarjan. A new approach to the maximum-flow problem. Journal of the ACM (JACM), 35(4):921-940, 1988. Google Scholar
  18. Lars Gottesbüren, Michael Hamann, Tim Niklas Uhl, and Dorothea Wagner. Faster and better nested dissection orders for customizable contraction hierarchies. Algorithms, 12(9):196, 2019. Google Scholar
  19. Demian Hespe, Sebastian Lamm, Christian Schulz, and Darren Strash. Wegotyoucovered: The winning solver from the PACE 2019 challenge, vertex cover track. In Proceedings of the SIAM Workshop on Combinatorial Scientific Computing, pages 1-11. SIAM, 2020. URL: https://doi.org/10.1137/1.9781611976229.1.
  20. Demian Hespe, Christian Schulz, and Darren Strash. Scalable kernelization for maximum independent sets. Journal of Experimental Algorithmics (JEA), 24(1):1-22, 2019. Google Scholar
  21. John Hopcroft and Robert Tarjan. Algorithm 447: efficient algorithms for graph manipulation. Communications of the ACM, 16(6):372-378, 1973. Google Scholar
  22. John E Hopcroft and Richard M Karp. An n^5/2 algorithm for maximum matchings in bipartite graphs. SIAM Journal on computing, 2(4):225-231, 1973. Google Scholar
  23. David S Johnson. Cliques, coloring, and satisfiability: second dimacs implementation challenge. DIMACS series in discrete mathematics and theoretical computer science, 26:11-13, 1993. Google Scholar
  24. Tim Kieritz, Dennis Luxen, Peter Sanders, and Christian Vetter. Distributed time-dependent contraction hierarchies. In Experimental Algorithms, 9th International Symposium, volume 6049, pages 83-93. Springer, 2010. URL: https://doi.org/10.1007/978-3-642-13193-6_8.
  25. Jure Leskovec and Andrej Krevl. SNAP Datasets: Stanford large network dataset collection. http://snap.stanford.edu/data, 2014.
  26. Chu-Min Li, Zhiwen Fang, and Ke Xu. Combining maxsat reasoning and incremental upper bound for the maximum clique problem. In 25th IEEE International Conference on Tools with Artificial Intelligence, pages 939-946. IEEE Computer Society, 2013. URL: https://doi.org/10.1109/ICTAI.2013.143.
  27. Chu-Min Li, Hua Jiang, and Felip Manyà. On minimization of the number of branches in branch-and-bound algorithms for the maximum clique problem. Computers & Operations Research, 84:1-15, 2017. URL: https://doi.org/10.1016/j.cor.2017.02.017.
  28. Chu-Min Li, Hua Jiang, and Ruchu Xu. Incremental maxsat reasoning to reduce branches in a branch-and-bound algorithm for maxclique. In Learning and Intelligent Optimization - 9th International Conference, volume 8994, pages 268-274. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-19084-6_26.
  29. Chu Min Li and Zhe Quan. An efficient branch-and-bound algorithm based on maxsat for the maximum clique problem. In Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence. AAAI Press, 2010. URL: http://www.aaai.org/ocs/index.php/AAAI/AAAI10/paper/view/1611.
  30. Rick Plachetta and Alexander van der Grinten. Sat-and-reduce for vertex cover: Accelerating branch-and-reduce by sat solving. In 2021 Proceedings of the Workshop on Algorithm Engineering and Experiments (ALENEX), pages 169-180. SIAM, 2021. Google Scholar
  31. Deepak Puthal, Surya Nepal, Cécile Paris, Rajiv Ranjan, and Jinjun Chen. Efficient algorithms for social network coverage and reach. In IEEE International Congress on Big Data, pages 467-474. IEEE Computer Society, 2015. URL: https://doi.org/10.1109/BigDataCongress.2015.75.
  32. Ryan A. Rossi and Nesreen K. Ahmed. The network data repository with interactive graph analytics and visualization. In AAAI, 2015. URL: http://networkrepository.com.
  33. Pedro V. Sander, Diego Nehab, Eden Chlamtac, and Hugues Hoppe. Efficient traversal of mesh edges using adjacency primitives. ACM Trans. Graph., 27(5):144, 2008. URL: https://doi.org/10.1145/1409060.1409097.
  34. Peter Sanders and Christian Schulz. Think locally, act globally: Highly balanced graph partitioning. In Experimental Algorithms, 12th International Symposium, SEA 2013, Rome, Italy, June 5-7, 2013. Proceedings, volume 7933, pages 164-175. Springer, 2013. Google Scholar
  35. Christian Schorr. Improved branching strategies for maximum independent sets. Master’s thesis, Karlsruhe Institute of Technology, 2020. Google Scholar
  36. Pablo San Segundo and Cristóbal Tapia. Relaxed approximate coloring in exact maximum clique search. Computers & Operations Research, 44:185-192, 2014. URL: https://doi.org/10.1016/j.cor.2013.10.018.
  37. Etsuji Tomita, Yoichi Sutani, Takanori Higashi, and Mitsuo Wakatsuki. A simple and faster branch-and-bound algorithm for finding a maximum clique with computational experiments. IEICE Trans. Inf. Syst., 96-D(6):1286-1298, 2013. URL: https://doi.org/10.1587/transinf.E96.D.1286.
  38. Mingyu Xiao and Hiroshi Nagamochi. Confining sets and avoiding bottleneck cases: A simple maximum independent set algorithm in degree-3 graphs. Theoretical Computer Science, 469:92-104, 2013. URL: https://doi.org/10.1016/j.tcs.2012.09.022.
  39. Mingyu Xiao and Hiroshi Nagamochi. Exact algorithms for maximum independent set. Inf. Comput., 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 Imprint Privacy Contact