{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,8]],"date-time":"2026-06-08T21:31:53Z","timestamp":1780954313931,"version":"3.54.1"},"reference-count":48,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2019,9,23]],"date-time":"2019-09-23T00:00:00Z","timestamp":1569196800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"European Research Council","award":["340506"],"award-info":[{"award-number":["340506"]}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["SCHU 2567\/1-2"],"award-info":[{"award-number":["SCHU 2567\/1-2"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Helmholtz Association","award":["Large-Scale Data Management and Analysis"],"award-info":[{"award-number":["Large-Scale Data Management and Analysis"]}]},{"name":"Gottfried Wilhelm Leibniz Prize 2012"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2019,12,17]]},"abstract":"<jats:p>\n            The most efficient algorithms for finding maximum independent sets in both theory and practice use reduction rules to obtain a much smaller problem instance called a\n            <jats:italic>kernel<\/jats:italic>\n            . The kernel can then be solved quickly using exact or heuristic algorithms\u2014or by repeatedly kernelizing recursively in the branch-and-reduce paradigm. Current algorithms are either slow but produce a small kernel or fast and give a large kernel. Yet it is of critical importance for these algorithms that kernelization is fast and returns a small kernel. We attempt to accomplish both of these goals simultaneously by giving an efficient parallel kernelization algorithm based on graph partitioning and parallel bipartite maximum matching.\n          <\/jats:p>\n          <jats:p>We combine our parallelization techniques with two techniques to accelerate kernelization further: dependency checking that prunes reductions that cannot be applied, and reduction tracking that allows us to stop kernelization when reductions become less fruitful. Our algorithm produces kernels that are orders of magnitude smaller than the fastest kernelization methods while having a similar execution time. Furthermore, our algorithm is able to compute kernels with size comparable to the smallest known kernels but up to two orders of magnitude faster than possible previously. Finally, we show that our kernelization algorithm can be used to accelerate existing state-of-the-art heuristic algorithms, allowing us to find larger independent sets faster on large real-world networks and synthetic instances.<\/jats:p>","DOI":"10.1145\/3355502","type":"journal-article","created":{"date-parts":[[2019,9,23]],"date-time":"2019-09-23T12:10:12Z","timestamp":1569240612000},"page":"1-22","source":"Crossref","is-referenced-by-count":23,"title":["Scalable Kernelization for Maximum Independent Sets"],"prefix":"10.1145","volume":"24","author":[{"given":"Demian","family":"Hespe","sequence":"first","affiliation":[{"name":"Karlsruhe Institute of Technology, Karlsruhe, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2823-3506","authenticated-orcid":false,"given":"Christian","family":"Schulz","sequence":"additional","affiliation":[{"name":"University of Vienna, Vienna, Austria"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Darren","family":"Strash","sequence":"additional","affiliation":[{"name":"Hamilton College, Clinton, NY, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2019,9,23]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-007-1328-0"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.09.023"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10732-012-9196-4"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2016.2546258"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 26th International Parallel and Distributed Processing Symposium (IPDPS\u201912)","author":"Azad Ariful","year":"2012","unstructured":"Ariful Azad , Mahantesh Halappanavar , Sivasankaran Rajamanickam , Erik G. Boman , Arif Khan , and Alex Pothen . 2012 . Multithreaded algorithms for maximum matching in bipartite graphs . In Proceedings of the 26th International Parallel and Distributed Processing Symposium (IPDPS\u201912) . IEEE, Los Alamitos, CA, 860--872. DOI:https:\/\/doi.org\/10.1109\/IPDPS. 2012.82 Ariful Azad, Mahantesh Halappanavar, Sivasankaran Rajamanickam, Erik G. Boman, Arif Khan, and Alex Pothen. 2012. Multithreaded algorithms for maximum matching in bipartite graphs. In Proceedings of the 26th International Parallel and Distributed Processing Symposium (IPDPS\u201912). IEEE, Los Alamitos, CA, 860--872. DOI:https:\/\/doi.org\/10.1109\/IPDPS.2012.82"},{"key":"e_1_2_1_6_1","volume-title":"Encyclopedia of Social Network Analysis and Mining","author":"Bader David A.","unstructured":"David A. Bader , Henning Meyerhenke , Peter Sanders , Christian Schulz , Andrea Kappes , and Dorothea Wagner . 2014. Benchmarking for graph clustering and partitioning . In Encyclopedia of Social Network Analysis and Mining . Springer , 73--82. DOI:https:\/\/doi.org\/10.1007\/978-1-4614-6170-8_23 David A. Bader, Henning Meyerhenke, Peter Sanders, Christian Schulz, Andrea Kappes, and Dorothea Wagner. 2014. Benchmarking for graph clustering and partitioning. In Encyclopedia of Social Network Analysis and Mining. Springer, 73--82. DOI:https:\/\/doi.org\/10.1007\/978-1-4614-6170-8_23"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-012-9592-6"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.587"},{"key":"e_1_2_1_9_1","volume-title":"Optimization: Structure and Applications","author":"Butenko Sergiy","unstructured":"Sergiy Butenko , Panos Pardalos , Ivan Sergienko , Vladimir Shylo , and Petro Stetsyuk . 2009. Estimating the size of correcting codes using extremal graph problems . In Optimization: Structure and Applications , C. Pearce and E. Hunt (Eds.). Springer , 227--243. https:\/\/doi.org\/10.1007\/978-0-387-98096-6_12 Sergiy Butenko, Panos Pardalos, Ivan Sergienko, Vladimir Shylo, and Petro Stetsyuk. 2009. Estimating the size of correcting codes using extremal graph problems. In Optimization: Structure and Applications, C. Pearce and E. Hunt (Eds.). Springer, 227--243. https:\/\/doi.org\/10.1007\/978-0-387-98096-6_12"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/508791.508897"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2006.07.004"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3035939"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2001.1186"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3097983.3098031"},{"key":"e_1_2_1_15_1","volume-title":"Werneck","author":"Dahlum Jakob","year":"2016","unstructured":"Jakob Dahlum , Sebastian Lamm , Peter Sanders , Christian Schulz , Darren Strash , and Renato F . Werneck . 2016 . Accelerating local search for the maximum independent set problem. In Experimental Algorithms. Lecture Notes in Computer Science, Vol. 9685 . Springer , 118--133. DOI:https:\/\/doi.org\/10.1007\/978-3-319-38851-9_9 Jakob Dahlum, Sebastian Lamm, Peter Sanders, Christian Schulz, Darren Strash, and Renato F. Werneck. 2016. Accelerating local search for the maximum independent set problem. In Experimental Algorithms. Lecture Notes in Computer Science, Vol. 9685. Springer, 118--133. DOI:https:\/\/doi.org\/10.1007\/978-3-319-38851-9_9"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-007-1345-z"},{"key":"e_1_2_1_17_1","volume-title":"Johnson","author":"Demetrescu Camil","year":"2009","unstructured":"Camil Demetrescu , Andrew V. Goldberg , and David S . Johnson . 2009 . The Shortest Path Problem: Ninth DIMACS Implementation Challenge. Vol. 74 . AMS. Camil Demetrescu, Andrew V. Goldberg, and David S. Johnson. 2009. The Shortest Path Problem: Ninth DIMACS Implementation Challenge. Vol. 74. AMS."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/3230521.3230526"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.42.5.860"},{"key":"e_1_2_1_20_1","volume-title":"Fomin and Dieter Kratsch","author":"Fedor","year":"2010","unstructured":"Fedor V. Fomin and Dieter Kratsch . 2010 . Exact Exponential Algorithms. Springer . DOI:https:\/\/doi.org\/10.1007\/978-3-642-16533-7 Fedor V. Fomin and Dieter Kratsch. 2010. Exact Exponential Algorithms. Springer. DOI:https:\/\/doi.org\/10.1007\/978-3-642-16533-7"},{"key":"e_1_2_1_21_1","volume-title":"Fernando S\u00e1nchez Villaamil, and Somnath Sikdar","author":"Gajarsk\u00fd Jakub","year":"2013","unstructured":"Jakub Gajarsk\u00fd , Petr Hlin\u011bn\u00fd , Jan Obdr\u017e\u00e1lek , Sebastian Ordyniak , Felix Reidl , Peter Rossmanith , Fernando S\u00e1nchez Villaamil, and Somnath Sikdar . 2013 . Kernelization using structural parameters on sparse graph classes. In Algorithms. Lecture Notes in Computer Science, Vol. 8125 . Springer , 529--540. DOI:https:\/\/doi.org\/10.1007\/978-3-642-40450-4_45 Jakub Gajarsk\u00fd, Petr Hlin\u011bn\u00fd, Jan Obdr\u017e\u00e1lek, Sebastian Ordyniak, Felix Reidl, Peter Rossmanith, Fernando S\u00e1nchez Villaamil, and Somnath Sikdar. 2013. Kernelization using structural parameters on sparse graph classes. In Algorithms. Lecture Notes in Computer Science, Vol. 8125. Springer, 529--540. DOI:https:\/\/doi.org\/10.1007\/978-3-642-40450-4_45"},{"key":"e_1_2_1_22_1","volume-title":"Johnson","author":"Garey Michael R.","year":"1979","unstructured":"Michael R. Garey and David S . Johnson . 1979 . Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman . Michael R. Garey and David S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman."},{"key":"e_1_2_1_23_1","series-title":"Lecture Notes in Computer Science","volume-title":"Experimental Algorithms","author":"Gemsa Andreas","unstructured":"Andreas Gemsa , Martin N\u00f6llenburg , and Ignaz Rutter . 2014. Evaluation of labeling strategies for rotating maps . In Experimental Algorithms . Lecture Notes in Computer Science , Vol. 8504 . Springer , 235--246. DOI:https:\/\/doi.org\/10.1007\/978-3-319-07959-2_20 Andreas Gemsa, Martin N\u00f6llenburg, and Ignaz Rutter. 2014. Evaluation of labeling strategies for rotating maps. In Experimental Algorithms. Lecture Notes in Computer Science, Vol. 8504. Springer, 235--246. DOI:https:\/\/doi.org\/10.1007\/978-3-319-07959-2_20"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1233481.1233493"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975055.19"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2010.5470485"},{"key":"e_1_2_1_27_1","unstructured":"Yoichi Iwata. 2016. Personal communication. August 24.  Yoichi Iwata. 2016. Personal communication. August 24."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.127"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2013.08.005"},{"key":"e_1_2_1_30_1","volume-title":"Proceedings of the 22nd Annual Symposium on Foundations of Computer Science (SFCS\u201981)","author":"Richard","year":"1981","unstructured":"Richard M. Karp and Michael Sipser. 1981. Maximum matching in sparse random graphs . In Proceedings of the 22nd Annual Symposium on Foundations of Computer Science (SFCS\u201981) . IEEE, Los Alamitos, CA, 364--375. DOI:https:\/\/doi.org\/10.1109\/SFCS. 1981 .21 Richard M. Karp and Michael Sipser. 1981. Maximum matching in sparse random graphs. In Proceedings of the 22nd Annual Symposium on Foundations of Computer Science (SFCS\u201981). IEEE, Los Alamitos, CA, 364--375. DOI:https:\/\/doi.org\/10.1109\/SFCS.1981.21"},{"key":"e_1_2_1_31_1","series-title":"Lecture Notes in Computer Science","volume-title":"Experimental Algorithms","author":"Kieritz Tim","unstructured":"Tim Kieritz , Dennis Luxen , Peter Sanders , and Christian Vetter . 2010. Distributed time-dependent contraction hierarchies . In Experimental Algorithms . Lecture Notes in Computer Science , Vol. 6049 . Springer , 83--93. DOI:https:\/\/doi.org\/10.1007\/978-3-642-13193-6_8 Tim Kieritz, Dennis Luxen, Peter Sanders, and Christian Vetter. 2010. Distributed time-dependent contraction hierarchies. In Experimental Algorithms. Lecture Notes in Computer Science, Vol. 6049. Springer, 83--93. DOI:https:\/\/doi.org\/10.1007\/978-3-642-13193-6_8"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10732-017-9337-x"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICTAI.2013.143"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10732-016-9315-8"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2017.2671868"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580444"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2015.07.013"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1409060.1409097"},{"key":"e_1_2_1_39_1","series-title":"Lecture Notes in Computer Science","volume-title":"Experimental Algorithms","author":"Sanders Peter","unstructured":"Peter Sanders and Christian Schulz . 2013. Think locally, act globally: Highly balanced graph partitioning . In Experimental Algorithms . Lecture Notes in Computer Science , Vol. 7933 . Springer . DOI:https:\/\/doi.org\/10.1007\/978-3-642-38527-8_16 Peter Sanders and Christian Schulz. 2013. Think locally, act globally: Highly balanced graph partitioning. In Experimental Algorithms. Lecture Notes in Computer Science, Vol. 7933. Springer. DOI:https:\/\/doi.org\/10.1007\/978-3-642-38527-8_16"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11590-011-0431-y"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2010.07.019"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-42634-1_28"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1137\/0206038"},{"key":"e_1_2_1_44_1","series-title":"Lecture Notes in Computer Science","volume-title":"Algorithms and Computation","author":"Tomita Etsuji","unstructured":"Etsuji Tomita , Yoichi Sutani , Takanori Higashi , Shinya Takahashi , and Mitsuo Wakatsuki . 2010. A simple and faster branch-and-bound algorithm for finding a maximum clique . In Algorithms and Computation . Lecture Notes in Computer Science , Vol. 5942 . Springer , 191--203. DOI:https:\/\/doi.org\/10.1007\/978-3-642-11440-3_18 Etsuji Tomita, Yoichi Sutani, Takanori Higashi, Shinya Takahashi, and Mitsuo Wakatsuki. 2010. A simple and faster branch-and-bound algorithm for finding a maximum clique. In Algorithms and Computation. Lecture Notes in Computer Science, Vol. 5942. Springer, 191--203. DOI:https:\/\/doi.org\/10.1007\/978-3-642-11440-3_18"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.5555\/3214408.3214409"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/HPEC.2016.7761644"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.09.022"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2017.06.001"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3355502","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3355502","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:23:34Z","timestamp":1750202614000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3355502"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,9,23]]},"references-count":48,"alternative-id":["10.1145\/3355502"],"URL":"https:\/\/doi.org\/10.1145\/3355502","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"value":"1084-6654","type":"print"},{"value":"1084-6654","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,9,23]]}}}