Maximum Weighted Independent Set: Effective Reductions and Fast Algorithms on Sparse Graphs

• Published in: Algorithmica 2024-05, Vol.86 (5), p.1293-1334
• Main Authors: Xiao, Mingyu, Huang, Sen, Chen, Xiaoyu
• Format: Article
• Language: English
• Subjects: Algorithm Analysis and Problem Complexity; Algorithms; Apexes; Computer Science; Computer Systems Organization and Communication Networks; Data Structures and Information Theory; Graph theory; Graphs; Mathematics of Computing; Polynomials; Theory of Computation; Weight reduction
• ISSN: 0178-4617; 1432-0541
• DOI: 10.1007/s00453-023-01197-x

The maximum independent set problem is one of the most important problems in graph algorithms and has been extensively studied in the line of research on the worst-case analysis of exact algorithms for NP-hard problems. In the weighted version, each vertex in the graph is associated with a weight and we are going to find an independent set of maximum total vertex weight. Many reduction rules for the unweighted version have been developed that can be used to effectively reduce the input instance without loss the optimality. However, it seems that reduction rules for the weighted version have not been systemically studied. In this paper, we design a series of reduction rules for the maximum weighted independent set problem and also design a fast exact algorithm based on the reduction rules. By using the measure-and-conquer technique to analyze the algorithm, we show that the algorithm runs in O ∗ ( 1 . 1443 ( 0.624 x - 0.872 ) n ′ ) time and polynomial space, where n ′ is the number of vertices of degree at least 2 and x is the average degree of these vertices in the graph. When the average degree is small, our running-time bound beats previous results. For example, on graphs with the minimum degree at least 2 and average degree at most 3.68, our running time bound is better than that of previous polynomial-space algorithms for graphs with maximum degree at most 4.