{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:22:46Z","timestamp":1760242966225,"version":"build-2065373602"},"reference-count":21,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2015,2,27]],"date-time":"2015-02-27T00:00:00Z","timestamp":1424995200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["HU 2139\/1"],"award-info":[{"award-number":["HU 2139\/1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>The NP-hard RAINBOW SUBGRAPH problem, motivated from  bioinformatics, is to find in an edge-colored graph a subgraph that  contains each edge color exactly once and has at most \\(k\\)  vertices. We examine the parameterized complexity of RAINBOW SUBGRAPH for paths, trees, and general graphs.   We show that RAINBOW SUBGRAPH  is W[1]-hard  with respect to the parameter \\(k\\) and also with respect to the dual  parameter \\(\\ell:=n-k\\) where \\(n\\) is the number of vertices. Hence, we  examine parameter combinations and show, for example, a polynomial-size  problem kernel for the combined parameter \\(\\ell\\) and ``maximum  number of colors incident with any vertex''.  Additionally, we show APX-hardness even if the input graph is a  properly edge-colored path in which every color occurs at most  twice.<\/jats:p>","DOI":"10.3390\/a8010060","type":"journal-article","created":{"date-parts":[[2015,2,27]],"date-time":"2015-02-27T10:08:39Z","timestamp":1425031719000},"page":"60-81","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["The Parameterized Complexity of the Rainbow Subgraph Problem"],"prefix":"10.3390","volume":"8","author":[{"given":"Falk","family":"H\u00fcffner","sequence":"first","affiliation":[{"name":"Institut f\u00fcr Softwaretechnik und Theoretische Informatik, TU Berlin, Ernst-Reuter-Platz 7, D-10587 Berlin, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christian","family":"Komusiewicz","sequence":"additional","affiliation":[{"name":"Institut f\u00fcr Softwaretechnik und Theoretische Informatik, TU Berlin, Ernst-Reuter-Platz 7, D-10587 Berlin, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rolf","family":"Niedermeier","sequence":"additional","affiliation":[{"name":"Institut f\u00fcr Softwaretechnik und Theoretische Informatik, TU Berlin, Ernst-Reuter-Platz 7, D-10587 Berlin, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Martin","family":"R\u00f6tzschke","sequence":"additional","affiliation":[{"name":"Institut f\u00fcr Softwaretechnik und Theoretische Informatik, TU Berlin, Ernst-Reuter-Platz 7, D-10587 Berlin, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2015,2,27]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Hajiaghayi, M.T., Jain, K., Lau, L.C., Mandoiu, I.I., Russell, A., and Vazirani, V.V. (2006, January 28\u201331). Minimum multicolored subgraph problem in multiplex PCR primer set selection and population haplotyping, Reading, UK.","DOI":"10.1007\/11758525_102"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"2666","DOI":"10.1016\/j.disc.2010.03.032","article-title":"Approximation algorithms for the minimum rainbow subgraph problem","volume":"310","author":"Schiermeyer","year":"2010","journal-title":"Discret. Math."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"128","DOI":"10.1093\/bioinformatics\/18.suppl_1.S128","article-title":"Microarray synthesis through multiple-use PCR primer design","volume":"18","author":"Fernandes","year":"2002","journal-title":"Bioinformatics"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"110","DOI":"10.1016\/j.ipl.2010.11.005","article-title":"Improved approximation bounds for the minimum rainbow subgraph problem","volume":"111","author":"Schiermeyer","year":"2011","journal-title":"Inf. Proc. Lett."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.tcs.2014.05.008","article-title":"Better lower and upper bounds for the minimum rainbow subgraph problem","volume":"543","author":"Popa","year":"2014","journal-title":"Theor. Comput. Sci."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"765","DOI":"10.1016\/j.endm.2011.10.028","article-title":"Algorithmic approaches for the minimum rainbow subgraph problem","volume":"38","author":"Koch","year":"2011","journal-title":"Electron. Notes Discret. Math."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1109\/TCBB.2006.40","article-title":"Islands of tractability for parsimony haplotyping","volume":"3","author":"Sharan","year":"2006","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Fleischer, R., Guo, J., Niedermeier, R., Uhlmann, J., Wang, Y., Weller, M., and Wu, X. (2010, January 21\u201323). Extended islands of tractability for parsimony haplotyping, New York, NY, USA.","DOI":"10.1007\/978-3-642-13509-5_20"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"1692","DOI":"10.1109\/TCBB.2010.72","article-title":"Haplotype inference constrained by plausible haplotype data","volume":"8","author":"Fellows","year":"2011","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Hassin, R., and Segev, D. (2005, January 15\u201318). The set cover with pairs problem, Hyderabad, India.","DOI":"10.1007\/11590156_13"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Williamson, D.P., and Shmoys, D.B. (2011). The Design of Approximation Algorithms, Cambridge University Press.","DOI":"10.1017\/CBO9780511921735"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Downey, R.G., and Fellows, M.R. (2013). Fundamentals of Parameterized Complexity, Springer.","DOI":"10.1007\/978-1-4471-5559-1"},{"key":"ref_13","unstructured":"Flum, J., and Grohe, M. (2006). Parameterized Complexity Theory, Springer Berlin Heidelberg."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Niedermeier, R. (2006). Invitation to Fixed-Parameter Algorithms, Oxford University Press.","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1016\/S0304-3975(98)00158-3","article-title":"Some APX-completeness results for cubic graphs","volume":"237","author":"Alimonti","year":"2000","journal-title":"Theor. Comput. Sci."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/j.tcs.2008.09.065","article-title":"On the parameterized complexity of multiple-interval graph problems","volume":"410","author":"Fellows","year":"2009","journal-title":"Theor. Comput. Sci."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Komusiewicz, C., and Sorge, M. (2012, January 12\u201314). Finding dense subgraphs of sparse graphs, Ljubljana, Slovenia.","DOI":"10.1007\/978-3-642-33293-7_23"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"546","DOI":"10.1137\/070683933","article-title":"Set partitioning via inclusion-exclusion","volume":"39","author":"Husfeldt","year":"2009","journal-title":"SIAM J. Comput."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Kaski, P., and Koivisto, M. (2007, January 11\u201313). Fourier meets M\u00f6bius: Fast subset convolution, San Diego, CA, USA.","DOI":"10.1145\/1250790.1250801"},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"F\u00fcrer, M. (2007, January 11\u201313). Faster integer multiplication, San Diego, CA, USA.","DOI":"10.1145\/1250790.1250800"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"83","DOI":"10.26493\/1855-3974.246.94d","article-title":"On the minimum rainbow subgraph number of a graph","volume":"6","author":"Schiermeyer","year":"2012","journal-title":"Ars Math. Contemp."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/8\/1\/60\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T20:43:00Z","timestamp":1760215380000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/8\/1\/60"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,2,27]]},"references-count":21,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2015,3]]}},"alternative-id":["a8010060"],"URL":"https:\/\/doi.org\/10.3390\/a8010060","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2015,2,27]]}}}