{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,4]],"date-time":"2026-05-04T17:57:46Z","timestamp":1777917466407,"version":"3.51.4"},"reference-count":60,"publisher":"Wiley","issue":"4","license":[{"start":{"date-parts":[[2026,1,28]],"date-time":"2026-01-28T00:00:00Z","timestamp":1769558400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"},{"start":{"date-parts":[[2026,1,28]],"date-time":"2026-01-28T00:00:00Z","timestamp":1769558400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/doi.wiley.com\/10.1002\/tdm_license_1.1"}],"content-domain":{"domain":["onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["Networks"],"published-print":{"date-parts":[[2026,6]]},"abstract":"<jats:title>ABSTRACT<\/jats:title>\n                  <jats:p>A 2\u2010packing set for an undirected, weighted graph  is a subset  such that any two vertices  are not adjacent and have no common neighbors. The Maximum Weight 2\u2010Packing Set problem that asks for a 2\u2010packing set of maximum weight is \u2010hard. Next to 13 novel data reduction rules for this problem, we develop two new approaches to solve this problem on arbitrary graphs. First, we introduce a preprocessing routine that exploits the close relation of 2\u2010packing sets to independent sets. This makes well\u2010studied independent set solvers usable for the Maximum Weight 2\u2010Packing Set problem. Second, we propose an iterative reduce\u2010and\u2010peel approach that utilizes the new data reductions. Our experiments show that our preprocessing routine gives speedups of multiple orders of magnitude, while also improving solution quality and memory consumption compared to a naive transformation to independent set instances. Furthermore, it solves 44% of the instances tested to optimality. Our heuristic can keep up with the best\u2010performing maximum weight independent set solvers combined with our preprocessing routine. Additionally, our heuristic can find the best solution quality on the biggest instances in our data set, outperforming all other approaches. When using our data reduction rules for exact solvers, we can solve more instances to optimality and are overall multiple orders of magnitude faster.<\/jats:p>","DOI":"10.1002\/net.70028","type":"journal-article","created":{"date-parts":[[2026,1,28]],"date-time":"2026-01-28T10:03:46Z","timestamp":1769594626000},"page":"404-427","update-policy":"https:\/\/doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Finding Maximum Weight 2\u2010Packing Sets on\u00a0Arbitrary Graphs"],"prefix":"10.1002","volume":"87","author":[{"given":"Jannick","family":"Borowitz","sequence":"first","affiliation":[{"name":"Faculty of Mathematics and Informatics University Heidelberg  Heidelberg Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9678-0253","authenticated-orcid":false,"given":"Ernestine","family":"Gro\u00dfmann","sequence":"additional","affiliation":[{"name":"Faculty of Mathematics and Informatics University Heidelberg  Heidelberg Germany"}]},{"given":"Christian","family":"Schulz","sequence":"additional","affiliation":[{"name":"Faculty of Mathematics and Informatics University Heidelberg  Heidelberg Germany"}]}],"member":"311","published-online":{"date-parts":[[2026,1,28]]},"reference":[{"key":"e_1_2_12_2_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129626404001970"},{"key":"e_1_2_12_3_1","first-page":"1","article-title":"A Self\u2010Stabilizing Algorithm for Maximal 2\u2010Packing","volume":"11","author":"Gairing M.","year":"2004","journal-title":"Nordic Journal of Computing"},{"key":"e_1_2_12_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-49823-0_30"},{"key":"e_1_2_12_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2012.03.018"},{"key":"e_1_2_12_6_1","doi-asserted-by":"publisher","DOI":"10.1142\/S012905411750037X"},{"key":"e_1_2_12_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPSW.2012.106"},{"key":"e_1_2_12_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2011.12.008"},{"key":"e_1_2_12_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45032-7_4"},{"key":"e_1_2_12_10_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v37i6.25824"},{"key":"e_1_2_12_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2018.03.085"},{"key":"e_1_2_12_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/PROC.1980.11899"},{"key":"e_1_2_12_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2016.02.023"},{"key":"e_1_2_12_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2003.06.004"},{"key":"e_1_2_12_15_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.10.2.180"},{"key":"e_1_2_12_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3"},{"key":"e_1_2_12_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3035939"},{"key":"e_1_2_12_18_1","unstructured":"E.Gro\u00dfmann K.Langedal andC.Schulz \u201cAccelerating Reductions Using Graph Neural Networks and a New Concurrent Local Search for the Maximum Weight Independent Set Problem \u201d2024. arXiv Preprint arXiv:2412.14198."},{"key":"e_1_2_12_19_1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.v28i1.2997"},{"key":"e_1_2_12_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10732-017-9337-x"},{"key":"e_1_2_12_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-42634-1_28"},{"key":"e_1_2_12_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.09.023"},{"key":"e_1_2_12_23_1","volume-title":"20th International Symposium on Experimental Algorithms (SEA 2022)","author":"Langedal K.","year":"2022"},{"key":"e_1_2_12_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-020-00602-z"},{"key":"e_1_2_12_25_1","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.2014.0618"},{"key":"e_1_2_12_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-021-01570-8"},{"key":"e_1_2_12_27_1","first-page":"1689","volume-title":"Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI\u201021","author":"Jiang H.","year":"2021"},{"key":"e_1_2_12_28_1","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2017\/73"},{"key":"e_1_2_12_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1412228.1412236"},{"key":"e_1_2_12_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977042.4"},{"key":"e_1_2_12_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-21534-6_6"},{"key":"e_1_2_12_32_1","unstructured":"J.Borowitz E.Gro\u00dfmann C.Schulz andD.Schweisgut \u201cScalable Algorithms for 2\u2010Packing Sets on Arbitrary Graphs \u201d2023. arXiv Preprint arXiv:2308.15515."},{"key":"e_1_2_12_33_1","first-page":"22","volume-title":"23rd International Symposium on Experimental Algorithms","author":"Gro\u00dfmann E.","year":"2025"},{"key":"e_1_2_12_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2020.03.016"},{"key":"e_1_2_12_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2013.12.002"},{"key":"e_1_2_12_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPSW.2014.86"},{"key":"e_1_2_12_37_1","volume-title":"k\u2010Packing and k\u2010Domination on Tree Graphs","author":"Mjedle M.","year":"2004"},{"key":"e_1_2_12_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2017.11.030"},{"key":"e_1_2_12_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11590-022-01939-w"},{"key":"e_1_2_12_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/174644.174650"},{"key":"e_1_2_12_41_1","first-page":"3:1","volume-title":"LIPIcs, IPEC 2016","author":"Bacs\u00f3 G.","year":"2017"},{"key":"e_1_2_12_42_1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00621"},{"key":"e_1_2_12_43_1","doi-asserted-by":"publisher","DOI":"10.1587\/transinf.2018FCL0002"},{"key":"e_1_2_12_44_1","doi-asserted-by":"publisher","DOI":"10.34768\/amcs-2020-0014"},{"key":"e_1_2_12_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/IIAI-AAI50415.2020.00177"},{"key":"e_1_2_12_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0055051"},{"key":"e_1_2_12_47_1","first-page":"144","volume-title":"Proceedings of the Twenty\u2010First Workshop on Algorithm Engineering and Experiments, ALENEX 2019","author":"Lamm S.","year":"2019"},{"key":"e_1_2_12_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/3447548.3467232"},{"key":"e_1_2_12_49_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11590\u2010017\u20101128\u20107"},{"key":"e_1_2_12_50_1","doi-asserted-by":"crossref","unstructured":"E.Gro\u00dfmann K.Langedal andC.Schulz \u201cA Comprehensive Survey of Data Reduction Rules for the Maximum Weighted Independent Set Problem \u201d2024. arXiv Preprint arXiv:2412.09303.","DOI":"10.1137\/1.9781611979084.12"},{"key":"e_1_2_12_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/s12532-020-00175-6"},{"key":"e_1_2_12_52_1","doi-asserted-by":"publisher","DOI":"10.1007\/s101070100263"},{"key":"e_1_2_12_53_1","unstructured":"J.LeskovecandA.Krevl \u201cSNAP Datasets: Stanford Large Network Dataset Collection \u201d(2014) http:\/\/snap.stanford.edu\/data."},{"key":"e_1_2_12_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/2049662.2049670"},{"key":"e_1_2_12_55_1","unstructured":"C.Walshaw \u201cGraph Partitioning Archive \u201d(2000) https:\/\/chriswalshaw.co.uk\/partition\/."},{"key":"e_1_2_12_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/1409060.1409097"},{"key":"e_1_2_12_57_1","unstructured":"Openstreetmap https:\/\/www.openstreetmap.org."},{"key":"e_1_2_12_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/2996913.2996957"},{"key":"e_1_2_12_59_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976472.10"},{"key":"e_1_2_12_60_1","volume-title":"Encyclopedia of Social Network Analysis and Mining","author":"Sanders P.","year":"2014"},{"key":"e_1_2_12_61_1","volume-title":"The SCIP Optimization Suite 9.0","author":"Bolusani S.","year":"2024"}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.70028","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/full-xml\/10.1002\/net.70028","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.70028","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T18:14:17Z","timestamp":1777659257000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.70028"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,1,28]]},"references-count":60,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2026,6]]}},"alternative-id":["10.1002\/net.70028"],"URL":"https:\/\/doi.org\/10.1002\/net.70028","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,1,28]]},"assertion":[{"value":"2025-03-04","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-12-28","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-01-28","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}