Targeted Branching for the Maximum Independent Set Problem

DOI10.4230/LIPICS.SEA.2021.17arXiv2102.01540OpenAlexW3165090370MaRDI QIDQ6159907FDOQ6159907

Demian Hespe, Sebastian Lamm, Author name not available (Why is that?)

Publication date: 23 June 2023

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. Some of the most successful algorithms for 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, achieved substantial results, solving many previously infeasible 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 an 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. The most commonly used strategy selects vertices based on their degree and does not take into account other factors that contribute to the performance. 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. 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. Our experiments on a large set of real-world instances indicate that our strategies are able to improve the performance of the state-of-the-art branch-and-reduce algorithms. 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).

Full work available at URL: https://arxiv.org/abs/2102.01540

Recommendations

• A refined branching algorithm for the maximum satisfiability problem
• Maximizing the number of independent subsets over trees with bounded degree
• A branch-and-reduce algorithm for finding a minimum independent dominating set
• GreedyMAX-type algorithms for the maximum independent set problem
• An optimal maximal independent set algorithm for bounded-independence graphs
• scientific article; zbMATH DE number 1522948
• A Branch-and-Reduce Algorithm for Finding a Minimum Independent Dominating Set in Graphs
• Exact algorithms for maximum independent set
• Exact Algorithms for Maximum Independent Set
• Maximum independent set for intervals by divide and conquer with pruning

zbMATH Keywords

graphscombinatorial optimizationdata reductioncliqueindependent setvertex coverbranch-and-boundbranch-and-reduce

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cited In (1)

• New properties of maximum independent set problem solution truncation rules or redundant branches

This page was built for publication: Targeted Branching for the Maximum Independent Set Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6159907)