The maximum independent set problem is one of the most extensively studied optimization problems in graph algorithms and social networks. The weighted version of this problem, where each vertex will be assigned a nonnegative weight, also receives a lot of attention due to its potential applications in many areas. However, many nice properties and fast algorithms for the unweighted version can not be extended to the weighted version. In this paper, we study the structural properties of this problem, giving some sufficient conditions for a vertex being or not being in a maximum weighted independent set. These properties provide a suite of reduction rules that includes and generalizes almost all frequently used reduction rules for this problem. These rules can efficiently find partial solutions and greatly reduce the instances, especially for sparse graphs. Based on them, we also propose a simple exact yet practical algorithm. To demonstrate the efficiency of our algorithm, we compare it with state-of-the-art algorithms on several well known datasets from the real world. The experimental results reveal that our exact algorithm is not only faster than existing algorithms but also can exactly solve more hard instances with 1,000 seconds. For remaining infeasible instances, our reduction rules can also improve existing heuristic algorithms by producing higher-quality solutions using less time.

2021 THE WEB CONFERENCE NEWSLETTER
The Web Conference is announcing latest news and developments biweekly or on a monthly basis. We respect The General Data Protection Regulation 2016/679.