NuMVC: An Efficient Local Search Algorithm for Minimum Vertex Cover

TIVC: An Efficient Local Search Algorithm for Minimum Vertex Cover in Large Graphs

The minimum vertex cover (MVC) problem is a canonical NP-hard combinatorial optimization problem aiming to find the smallest set of vertices such that every edge has at least one endpoint in the set. This problem has extensive applications in cybersecurity, scheduling, and monitoring link failures in wireless sensor networks (WSNs). Numerous local search algorithms have been proposed to obtain "good" vertex coverage. However, due to the NP-hard nature, it is challenging to efficiently solve the MVC problem, especially on large graphs. In this paper, we propose an efficient local search algorithm for MVC called TIVC, which is based on two main ideas: a 3-improvements (TI) framework with a tiny perturbation and edge selection strategy. We conducted experiments on real-world large instances of a massive graph benchmark. Compared with three state-of-the-art MVC algorithms, TIVC shows superior performance in accuracy and possesses a remarkable ability to identify significantly smaller vertex covers on many graphs.

Improved Memetic Algorithm for Solving the Minimum Weight Vertex Independent Dominating Set

The minimum weight vertex independent dominating set (MWVIDS) problem is an important version of the minimum independent dominating set. The MWVIDS problem has a number of applications in many fields. However, the MWVIDS problem is known to be NP-hard and thus computationally challenging. In this work, we present the improved memetic algorithm called MSSAS for solving the MWVIDS problem. The proposed MSSAS algorithm combines probability-based dynamic optimization (PDO) (to generate good and diverse offspring solutions by assembling elements of existing good solutions) as well as a local search phase named C_LS (to seek high-quality local optima by combining the idea of constrained-based two-level configuration checking strategy and tabu mechanism). The extensive results on popular DIMACS and BHOLIB benchmarks demonstrate that MSSAS competes favorably with the state-of-the-art algorithms. In addition, we analyze the benefits of the newly raised components including two above proposed ideas with our memetic framework. It is worth mentioning that the combination of both components has excellent effects for the MWVIDS problem.

Applying aspiration in local search for satisfiability

The Boolean Satisfiability problem (SAT) is a prototypical NP-complete problem, which has been widely studied due to its significant importance in both theory and applications. Stochastic local search (SLS) algorithms are among the most efficient approximate methods available for solving certain types of SAT instances. The quantitative configuration checking (QCC) heuristic is an effective approach for improving SLS algorithms on solving the SAT problem, resulting in an efficient SLS solver for SAT named Swqcc. In this paper, we focus on combining the QCC heuristic with an aspiration mechanism, and then design a new heuristic called QCCA. On the top of Swqcc, we utilize the QCCA heuristic to develop a new SLS solver dubbed AspiSAT. Through extensive experiments, the results illustrate that, on random 3-SAT instances, the performance of AspiSAT is much better than that of Swqcc and Sparrow, which is an influential and efficient SLS solver for SAT. In addition, we further enhance the original clause weighting schemes employed in Swqcc and AspiSAT, and thus obtain two new SLS solvers called Ptwqcc and AspiPT, respectively. The eperimental results present that both Ptwqcc and AspiPT outperform Swqcc and AspiSAT on random 5-SAT instances, indicating that both QCC and QCCA heuristics are able to cooperate effectively with different clause weighting schemes.

A Novel Hybrid Algorithm for Minimum Total Dominating Set Problem

The minimum total dominating set (MTDS) problem is a variant of the classical dominating set problem. In this paper, we propose a hybrid evolutionary algorithm, which combines local search and genetic algorithm to solve MTDS. Firstly, a novel scoring heuristic is implemented to increase the searching effectiveness and thus get better solutions. Specially, a population including several initial solutions is created first to make the algorithm search more regions and then the local search phase further improves the initial solutions by swapping vertices effectively. Secondly, the repair-based crossover operation creates new solutions to make the algorithm search more feasible regions. Experiments on the classical benchmark DIMACS are carried out to test the performance of the proposed algorithm, and the experimental results show that our algorithm performs much better than its competitor on all instances.