{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:42:56Z","timestamp":1787323376529,"version":"build-2736575974"},"reference-count":28,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"DOI":"10.13039\/501100004756","name":"Emil Aaltosen S\u00e4\u00e4ti\u00f6","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100004756","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004281","name":"Narodowe Centrum Nauki","doi-asserted-by":"publisher","award":["2013\/09\/B\/ST6\/03136"],"award-info":[{"award-number":["2013\/09\/B\/ST6\/03136"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>The Rainbow $k$-Coloring problem asks whether the edges of a given graph can be colored in $k$ colors so that every pair of vertices is connected by a rainbow path, i.e., a path with all edges of different colors. Our main result states that for any $k\\ge 2$, there is no algorithm for Rainbow $k$-Coloring running in time $2^{o(n^{3\/2})}$, unless the exponential time hypothesis fails. Motivated by this negative result we consider two parameterized variants of the problem. In the Subset Rainbow $k$-Coloring problem, introduced by Chakraborty et al. [ J. Comb. Optim., 21 (2009), pp. 330--347], we are additionally given a set $S$ of pairs of vertices and we ask if there is a coloring in which all the pairs in $S$ are connected by rainbow paths. We show that Subset Rainbow $k$-Coloring is fixed parameter tractable (FPT) when parameterized by $|S|$. We also study the Maximum Rainbow $k$-Coloring problem, where we are additionally given an integer $q$, and we ask if there is a coloring in which at least $q$ anti-edges are connected by rainbow paths. We show that the problem is FPT when parameterized by $q$ and has a kernel of size $O(q)$ for every $k\\ge 2$, extending the result of Ananth, Nasre, and Sarpatwar, in FSTTCS, LIPIcs, Schloss Dagstuhl--Leibniz-Zentum f\u00fcr Informatik, Dagstuhl, Germany, 2011, pp. 241--251. We believe that our techniques used for the lower bounds may shed some light on the complexity of the classical Edge Coloring problem, where it is a major open question if a $2^{O(n)}$-time algorithm exists.<\/jats:p>","DOI":"10.1137\/16m1102690","type":"journal-article","created":{"date-parts":[[2018,7,17]],"date-time":"2018-07-17T12:02:23Z","timestamp":1531828943000},"page":"1672-1705","source":"Crossref","is-referenced-by-count":5,"title":["On the Fine-Grained Complexity of Rainbow Coloring"],"prefix":"10.1137","volume":"32","author":[{"given":"\u0141ukasz","family":"Kowalik","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Juho","family":"Lauri","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Arkadiusz","family":"Soca\u0142a","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,7,17]]},"reference":[{"key":"atypb1","unstructured":"A. Agrawal,\n                      Fine-grained complexity of rainbow coloring and its variants\n                      , in 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017), K. G. Larsen, H. L. Bodlaender, and J.F. Raskin, eds., LIPIcs Leibniz Int. Proc. Inform. 83, Schloss Dagstuhl-Leibniz-Zentrum fu\u0308r Informatik, Dagstuhl, Germany, 2017, pp. 60:1-60:14,https:\/\/doi.org\/10.4230\/LIPIcs.MFCS.2017.60."},{"key":"atypb2","unstructured":"P. Ananth, M. Nasre, and K. K. Sarpatwar,\n                      Rainbow connectivity: Hardness and tractability\n                      , in IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), S. Chakraborty and A. Kumar, eds., LIPIcs Leibniz Int. Proc. Inform. 13, Schloss Dagstuhl-Leibniz-Zentrum fu\u0308r Informatik, Dagstuhl, Germany, 2011, pp. 241-251."},{"key":"atypb3","doi-asserted-by":"crossref","first-page":"R57","DOI":"10.37236\/781","volume":"15","author":"Caro Y.","year":"2008","journal-title":"Electron. J. Combin."},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-009-9250-9"},{"key":"atypb5","first-page":"181","author":"Chandran L. S.","year":"2012","journal-title":"New York"},{"key":"atypb6","unstructured":"L. S. Chandran and D. Rajendraprasad,\n                      Inapproximability of rainbow colouring\n                      , in IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013), A. Seth and N. K. Vishnoi, eds., LIPIcs Leibniz Int. Proc. Inform. 24, Schloss Dagstuhl-Leibniz-Zentrum fu\u0308r Informatik, Dagstuhl, Germany, 2013, pp. 153-162."},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2015.05.021"},{"key":"atypb8","doi-asserted-by":"crossref","first-page":"85","DOI":"10.21136\/MB.2008.133947","volume":"133","author":"Chartrand G.","year":"2008","journal-title":"Math. Bohem."},{"key":"atypb9","doi-asserted-by":"crossref","unstructured":"G. Chartrand and P. Zhang,\n                      Chromatic Graph Theory\n                      , CRC Press, Boca Raton, FL, 2008.","DOI":"10.1201\/9781584888017"},{"key":"atypb10","first-page":"1643","author":"Cygan M.","year":"2016","journal-title":"Philadelphia"},{"key":"atypb11","doi-asserted-by":"crossref","unstructured":"M. Cygan, F. V. Fomin, \u0141. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh,\n                      Parameterized Algorithms\n                      , Springer, New York, 2015.","DOI":"10.1007\/978-3-319-21275-3"},{"key":"atypb12","doi-asserted-by":"crossref","unstructured":"R. Diestel,\n                      Graph Theory\n                      , Springer, New York, 2010.","DOI":"10.1007\/978-3-642-14279-6"},{"key":"atypb13","first-page":"209","author":"Eiben E.","year":"2015","journal-title":"New York"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1137\/0110015"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1727"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1774"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.20367"},{"key":"atypb18","first-page":"1","author":"Kowalik L.","year":"2016","journal-title":"Germany"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(76)90065-X"},{"key":"atypb20","unstructured":"V. B. Le and Z. Tuza,\n                      Finding Optimal Rainbow Connection is Hard\n                      , Tech. Report CS-03-09, Universita\u0308t Rostock, 2009."},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1007\/s00373-012-1243-2"},{"key":"atypb22","doi-asserted-by":"crossref","unstructured":"X. Li and Y. Sun,\n                      Rainbow Connections of Graphs\n                      , Springer, New York, 2012.","DOI":"10.1007\/978-1-4614-3119-0"},{"key":"atypb23","unstructured":"X. Li and Y. Sun,\n                      An updated survey on rainbow connections of graphs-a dynamic survey\n                      , Theory Appl. Graphs (2017), 3."},{"key":"atypb24","first-page":"182","author":"Naor M.","year":"1995","journal-title":"IEEE"},{"key":"atypb25","first-page":"662","author":"Soca\u0142a A.","year":"2015","journal-title":"Philadelphia"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(84)90081-7"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9689-4"},{"key":"atypb28","doi-asserted-by":"crossref","unstructured":"V. V. Vazirani,\n                      Approximation Algorithms\n                      , Springer, New York, 2013.","DOI":"10.21236\/ADA579025"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/16M1102690","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:58:35Z","timestamp":1787320715000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/16M1102690"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":28,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/16M1102690"],"URL":"https:\/\/doi.org\/10.1137\/16m1102690","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}