{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,9]],"date-time":"2026-05-09T14:06:52Z","timestamp":1778335612212,"version":"3.51.4"},"reference-count":60,"publisher":"Cambridge University Press (CUP)","issue":"5","license":[{"start":{"date-parts":[[2020,5,14]],"date-time":"2020-05-14T00:00:00Z","timestamp":1589414400000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2020,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We give an efficient algorithm that, given a graph <jats:italic>G<\/jats:italic> and a partition <jats:italic>V<\/jats:italic><jats:sub>1<\/jats:sub>,\u2026,<jats:italic>V<\/jats:italic><jats:sub><jats:italic>m<\/jats:italic><\/jats:sub> of its vertex set, finds either an <jats:italic>independent transversal<\/jats:italic> (an independent set {<jats:italic>v<\/jats:italic><jats:sub>1<\/jats:sub>,\u2026,<jats:italic>v<\/jats:italic><jats:sub><jats:italic>m<\/jats:italic><\/jats:sub>} in <jats:italic>G<\/jats:italic> such that <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" mimetype=\"image\" xlink:href=\"S0963548320000127_inline1.png\"\/><jats:tex-math>${v_i} \\in {V_i}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> for each <jats:italic>i<\/jats:italic>), or a subset <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" mimetype=\"image\" xlink:href=\"S0963548320000127_inline2.png\"\/><jats:tex-math>${\\cal B}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> of vertex classes such that the subgraph of <jats:italic>G<\/jats:italic> induced by <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" mimetype=\"image\" xlink:href=\"S0963548320000127_inline3.png\"\/><jats:tex-math>$\\bigcup\\nolimits_{\\cal B}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> has a small dominating set. A non-algorithmic proof of this result has been known for a number of years and has been used to solve many other problems. Thus we are able to give algorithmic versions of many of these applications, a few of which we describe explicitly here.<\/jats:p>","DOI":"10.1017\/s0963548320000127","type":"journal-article","created":{"date-parts":[[2020,5,14]],"date-time":"2020-05-14T11:28:02Z","timestamp":1589455682000},"page":"780-806","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":7,"title":["Finding independent transversals efficiently"],"prefix":"10.1017","volume":"29","author":[{"given":"Alessandra","family":"Graf","sequence":"first","affiliation":[]},{"given":"Penny","family":"Haxell","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2020,5,14]]},"reference":[{"key":"S0963548320000127_ref31","doi-asserted-by":"publisher","DOI":"10.1145\/3015762"},{"key":"S0963548320000127_ref27","doi-asserted-by":"publisher","DOI":"10.1137\/0403018"},{"key":"S0963548320000127_ref26","unstructured":"[26] Erd\u0151s, P. and Lov\u00e1sz, L. (1975) Problems and results on 3-chromatic hypergraphs and some related questions. In Infinite and Finite Sets (Keszthely, Hungary 1973), Vol. 10 of Colloquia Mathematica Societatis J\u00e1nos Bolyai, pp. 609\u2013627."},{"key":"S0963548320000127_ref25","unstructured":"[25] Czumaj, A. and Scheideler, C. (2000) Coloring non-uniform hypergraphs: a new algorithmic approach to the general Lov\u00e1sz local lemma. In Eleventh Annual ACM\u2013SIAM Symposium on Discrete Algorithms, pp. 30\u201339."},{"key":"S0963548320000127_ref22","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2007.07.002"},{"key":"S0963548320000127_ref7","doi-asserted-by":"publisher","DOI":"10.1007\/BF02783300"},{"key":"S0963548320000127_ref19","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240020402"},{"key":"S0963548320000127_ref49","author":"Kolipaka","year":"2012"},{"key":"S0963548320000127_ref9","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240030102"},{"key":"S0963548320000127_ref29","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548320000127"},{"key":"S0963548320000127_ref6","doi-asserted-by":"publisher","DOI":"10.1002\/1097-0118(200010)35:2<83::AID-JGT2>3.0.CO;2-V"},{"key":"S0963548320000127_ref4","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-007-2086-y"},{"key":"S0963548320000127_ref23","doi-asserted-by":"publisher","DOI":"10.1137\/100799642"},{"key":"S0963548320000127_ref47","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.20532"},{"key":"S0963548320000127_ref21","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(75)90011-4"},{"key":"S0963548320000127_ref3","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-06-03833-5"},{"key":"S0963548320000127_ref2","doi-asserted-by":"publisher","DOI":"10.1007\/s004930170001"},{"key":"S0963548320000127_ref1","doi-asserted-by":"publisher","DOI":"10.1145\/2818352"},{"key":"S0963548320000127_ref43","doi-asserted-by":"publisher","DOI":"10.1016\/S0095-8956(03)00031-5"},{"key":"S0963548320000127_ref16","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-017-3567-2"},{"key":"S0963548320000127_ref15","unstructured":"[15] Annamalai, C. (2017) Algorithmic advances in allocation and scheduling. PhD dissertation, ETH Zurich."},{"key":"S0963548320000127_ref30","unstructured":"[30] Graf, A. , Harris, D. and Haxell, P. Algorithms for weighted independent transversals and strong colouring, submitted"},{"key":"S0963548320000127_ref57","volume-title":"Perfect Graphs","author":"Reed","year":"2001"},{"key":"S0963548320000127_ref14","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch126"},{"key":"S0963548320000127_ref46","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2006.03.002"},{"key":"S0963548320000127_ref11","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548306007851"},{"key":"S0963548320000127_ref12","doi-asserted-by":"publisher","DOI":"10.1016\/S0095-8956(02)00006-0"},{"key":"S0963548320000127_ref13","doi-asserted-by":"publisher","DOI":"10.1002\/9780470277331"},{"key":"S0963548320000127_ref45","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2004.04.003"},{"key":"S0963548320000127_ref37","doi-asserted-by":"publisher","DOI":"10.1007\/BF01876928"},{"key":"S0963548320000127_ref24","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.21684"},{"key":"S0963548320000127_ref32","unstructured":"[32] Harris, D. (2018) Derandomizing the Lov\u00e1sz local lemma via log-space statistical tests. arXiv:1807.06672"},{"key":"S0963548320000127_ref5","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-002-2792-6"},{"key":"S0963548320000127_ref60","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(96)00300-7"},{"key":"S0963548320000127_ref33","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.57"},{"key":"S0963548320000127_ref36","doi-asserted-by":"publisher","DOI":"10.1007\/BF01793010"},{"key":"S0963548320000127_ref8","unstructured":"[8] Alon, N. (1991) A parallel algorithmic version of the local lemma. In Thirty-Second Annual Symposium on Foundations of Computer Science, pp. 586\u2013593, IEEE."},{"key":"S0963548320000127_ref10","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(03)00227-9"},{"key":"S0963548320000127_ref20","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548311000253"},{"key":"S0963548320000127_ref39","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548304006157"},{"key":"S0963548320000127_ref54","doi-asserted-by":"publisher","DOI":"10.1145\/1667053.1667060"},{"key":"S0963548320000127_ref38","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548301004758"},{"key":"S0963548320000127_ref40","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.20300"},{"key":"S0963548320000127_ref42","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548305007157"},{"key":"S0963548320000127_ref44","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548300000274"},{"key":"S0963548320000127_ref48","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993669"},{"key":"S0963548320000127_ref55","doi-asserted-by":"publisher","DOI":"10.1137\/110828290"},{"key":"S0963548320000127_ref51","doi-asserted-by":"publisher","DOI":"10.1007\/s004930170006"},{"key":"S0963548320000127_ref28","unstructured":"[28] Fischer, M. and Ghaffari, M. (2017) Subalgorithmic distributed algorithms for Lov\u00e1sz local lemma and the complexity hierarchy. In Thirty-First International Symposium on Distributed Computing, Vol. 91 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 18:1\u201318.16, Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik."},{"key":"S0963548320000127_ref59","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-006-0019-9"},{"key":"S0963548320000127_ref50","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(96)00310-X"},{"key":"S0963548320000127_ref52","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276866"},{"key":"S0963548320000127_ref58","unstructured":"[58] Srinivasan, A. (2008) Improved algorithmic versions of the Lov\u00e1sz local lemma. In Nineteenth Annual ACM\u2013SIAM Symposium on Discrete Algorithms, pp. 611\u2013620."},{"key":"S0963548320000127_ref53","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536462"},{"key":"S0963548320000127_ref18","doi-asserted-by":"publisher","DOI":"10.1145\/2229163.2229168"},{"key":"S0963548320000127_ref34","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.68"},{"key":"S0963548320000127_ref41","doi-asserted-by":"publisher","DOI":"10.4169\/amer.math.monthly.118.09.777"},{"key":"S0963548320000127_ref35","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2017.v013a017"},{"key":"S0963548320000127_ref17","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-85363-3_2"},{"key":"S0963548320000127_ref56","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.20487"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548320000127","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,9,14]],"date-time":"2020-09-14T12:05:50Z","timestamp":1600085150000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548320000127\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,5,14]]},"references-count":60,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2020,9]]}},"alternative-id":["S0963548320000127"],"URL":"https:\/\/doi.org\/10.1017\/s0963548320000127","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,5,14]]},"assertion":[{"value":"\u00a9 The Author(s), 2020. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}}]}}