The Web Conference (WWW) is the premier international venue focused on understanding the current state and the evolution of the Web through the lens of computer science, computational social science, economics, policy, and many other disciplines. The 30th Web Conference (WWW 2021) will take place in Ljubljana, the capital of Slovenia. This year, the conference received 1736 submissions and accepted 357 of them as full papers. The acceptance ratio is 20.6%. Our below submission was selected to present on the conference. Congratulations to all authors!

Title: Efficient Reductions and a Fast Algorithm of Maximum Weighted Independent Set

Authors: Mingyu Xiao, Sen Huang, Yi Zhou, Bolin Ding

In this paper, we study the weighted version of the maximum independent set problem, one of the most extensively studied optimization problems in graph algorithms and social networks. By deeply studying the structural properties, we design a suite of efficient reduction rules and also propose a simple yet practical algorithm based on the reduction rules. The experimental results on known datasets show 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. Note that most of previous reduction rules were just used in theoretical analyses but not used to design fast solvers. The reviewers of this paper said that: it is quite appealing to see that a line of research which remained so far confined in the theory setting could actually lead to algorithms that can be implemented and executed on real instances, for producing non-trivial solutions, and the paper makes a very good point in this matter.