A Reduction-Driven Local Search for the Generalized Independent Set Problem

References

• Abu-Khzam FN, Lamm S, Mnich M, Noe A, Schulz C, Strash D (2022) Recent advances in practical data reduction. Bast H, Korzen C, Meyer U, Penschuck M, eds. Algorithms for Big Data (Springer, Cham, Switzerland), 97–133.Crossref, Google Scholar
• Akiba T, Iwata Y (2016) Branch-and-reduce exponential/FPT algorithms in practice: A case study of vertex cover. Theoret. Comput. Sci. 609(Part 1):211–225.Crossref, Google Scholar
• Bai T, Xiao M (2024) Exact algorithms for maximum independent set problem on hypergraphs. Scientia Sinica Informationis 54(12):2709–2726. Crossref, Google Scholar
• Brendel W, Todorovic S (2010) Segmentation as maximum-weight independent set. Lafferty J, Williams C, Shawe-Taylor J, Zemel R, Culotta A, eds. Proc. 24th Internat. Conf. Neural Inform. Processing Systems (Curran Associates, Red Hook, NY), 307–315.Google Scholar
• Brendel W, Amer M, Todorovic S (2011) Multiobject tracking as maximum weight independent set. CVPR ‘11 Proc. 2011 IEEE Conf. Comput. Vision Pattern Recognition (IEEE Computer Society, Washington, DC), 1273–1280.Google Scholar
• Chang L, Li W, Zhang W (2017) Computing a near-maximum independent set in linear time by reducing-peeling. SIGMOD ‘17. Proc. 2017 ACM Internat. Conf. Management Data (Association for Computing Machinery, New York), 1181–1196.Google Scholar
• Colombi M, Mansini R, Savelsbergh M (2017) The generalized independent set problem: Polyhedral analysis and solution approaches. Eur. J. Oper. Res. 260(1):41–55.Crossref, Google Scholar
• Crowder H, Johnson EL, Padberg M (1983) Solving large-scale zero-one linear programming problems. Oper. Res. 31(5):803–834.Link, Google Scholar
• Cygan M, Fomin FV, Kowalik Ł, Lokshtanov D, Marx D, Pilipczuk M, Pilipczuk M, Saurabh S (2015) Parameterized Algorithms (Springer, Cham, Switzerland).Crossref, Google Scholar
• Dahlum J, Lamm S, Sanders P, Schulz C, Strash D, Werneck RF (2016) Accelerating local search for the maximum independent set problem. Goldberg A, Kulikov A, eds. Experiment. Algorithms SEA 2016 (Springer, Cham, Switzerland), 118–133.Google Scholar
• Glover F, Laguna M (1998) Tabu search. Du DZ, Pardalos PM, eds. Handbook of Combinatorial Optimization (Springer, Boston), 2093–2229.Crossref, Google Scholar
• Großmann E, Lamm S, Schulz C, Strash D (2023) Finding near-optimal weight independent sets at scale. Proc. Genetic Evolutionary Comput. Conf. (Association for Computing Machinery, New York), 293–302.Google Scholar
• Gschwind T, Irnich S, Furini F, Calvo RW (2021) A branch-and-price framework for decomposing graphs into relaxed cliques. INFORMS J. Comput. 33(3):1070–1090.Link, Google Scholar
• Hochbaum DS (2004) 50th anniversary article: Selection, provisioning, shared fixed costs, maximum closure, and implications on algorithmic methods today. Management Sci. 50(6):709–723.Link, Google Scholar
• Hochbaum DS, Pathria A (1997) Forest harvesting and minimum cuts: A new approach to handling spatial constraints. Forest Sci. 43(4):544–554.Crossref, Google Scholar
• Hosseinian S, Butenko S (2019) Algorithms for the generalized independent set problem based on a quadratic optimization approach. Optim. Lett. 13(6):1211–1222.Crossref, Google Scholar
• Koana T, Korenwein V, Nichterlein A, Niedermeier R, Zschoche P (2021) Data reduction for maximum matching on real-world graphs: Theory and experiments. J. Experiment. Algorithmics 26(1):1–30. Crossref, Google Scholar
• Kochenberger G, Alidaee B, Glover F, Wang H (2007) An effective modeling and solution approach for the generalized independent set problem. Optim. Lett. 1(1):111–117.Crossref, Google Scholar
• Lamm S, Schulz C, Strash D, Williger R, Zhang H (2019) Exactly solving the maximum weight independent set problem on large real-world graphs. Kobourov S, Meyerhenke H, eds. 2019 Proc. Meeting Algorithm Engrg. Experiments (ALENEX) (SIAM, Philadelphia), 144–158.Google Scholar
• Liu Y, Zhou Y, Xu Z, Xiao M, Hao JK (2026) A reduction-driven local search for the generalized independent set problem. https://doi.org/10.1287/ijoc.2025.1203.cd, https://github.com/INFORMSJoC/2025.1203.Google Scholar
• López-Ibáñez M, Dubois-Lacoste J, Cáceres LP, Birattari M, Stützle T (2016) The irace package: Iterated racing for automatic algorithm configuration. Oper. Res. Perspect. 3:43–58.Crossref, Google Scholar
• Lourenço HR, Martin OC, Stützle T (2019) Iterated local search: Framework and applications. Gendreau M, Potvin JY, eds. Handbook of Metaheuristics (Springer, Cham, Switzerland), 129–168.Crossref, Google Scholar
• Mauri GR, Ribeiro GM, Lorena LA (2010) A new mathematical model and a Lagrangean decomposition for the point-feature cartographic label placement problem. Comput. Oper. Res. 37(12):2164–2172.Crossref, Google Scholar
• Nogueira B, Pinheiro RG, Tavares E (2021) Iterated local search for the generalized independent set problem. Optim. Lett. 15(4):1345–1369.Crossref, Google Scholar
• Pavlik JA, Ludden IG, Jacobson SH, Sewell EC (2021) Airplane seating assignment problem. Service Sci. 13(1):1–18.Link, Google Scholar
• Puthal D, Nepal S, Paris C, Ranjan R, Chen J (2015) Efficient algorithms for social network coverage and reach. 2015 IEEE Internat. Congress Big Data (IEEE Computer Society, Washington, DC), 467–474.Google Scholar
• Sanchis LA, Jagota A (1996) Some experimental and theoretical results on test case generators for the maximum clique problem. INFORMS J. Comput. 8(2):87–102.Link, Google Scholar
• Stanovic S, Gaüzère B, Brun L (2025) Graph neural networks with maximal independent set-based pooling: Mitigating over-smoothing and over-squashing. Pattern Recognition Lett. 187:14–20.Crossref, Google Scholar
• Verma A, Buchanan A, Butenko S (2015) Solving the maximum clique and vertex coloring problems on very large sparse networks. INFORMS J. Comput. 27(1):164–177.Link, Google Scholar
• Walteros JL, Buchanan A (2020) Why is maximum clique often easy in practice? Oper. Res. 68(6):1866–1895.Link, Google Scholar
• Wu J, Li CM, Wang L, Hu S, Zhao P, Yin M (2023) On solving simplified diversified top-k s-plex problem. Comput. Oper. Res. 153:106187.Crossref, Google Scholar
• Xiao M, Nagamochi H (2017) Exact algorithms for maximum independent set. Inform. Comput. 255(Part 1):126–146.Crossref, Google Scholar
• Xiao M, Huang S, Zhou Y, Ding B (2021) Efficient reductions and a fast algorithm of maximum weighted independent set. Leskovec J, Grobelnik M, Najork M, Tang J, Zia L, eds. Proc. Web Conf. 2021 (Association for Computing Machinery, New York), 3930–3940.Google Scholar
• Zheng M, Hao JK, Wu Q (2024) Exact and heuristic solution approaches for the generalized independent set problem. Comput. Oper. Res. 164:106561.Crossref, Google Scholar
• Zhou Y, Hao JK (2017) Frequency-driven tabu search for the maximum s-plex problem. Comput. Oper. Res. 86:65–78.Crossref, Google Scholar
• Zhou Y, Hao JK, Goëffon A (2017) PUSH: A generalized operator for the maximum vertex weight clique problem. Eur. J. Oper. Res. 257(1):41–54.Crossref, Google Scholar