{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:35:47Z","timestamp":1760243747880,"version":"build-2065373602"},"reference-count":17,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2012,12,27]],"date-time":"2012-12-27T00:00:00Z","timestamp":1356566400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/3.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>The problem of finding the maximum number of vertex-disjoint uni-color paths in an edge-colored graph has been recently introduced in literature, motivated by applications in social network analysis. In this paper we investigate the approximation and parameterized complexity of the problem. First, we show that, for any constant \u03b5 &gt; 0, the problem is not approximable within factor c1-\u03b5, where c is the number of colors, and that the corresponding decision problem is W[1]-hard when parametrized by the number of disjoint paths. Then, we present a fixed-parameter algorithm for the problem parameterized by the number and the length of the disjoint paths.<\/jats:p>","DOI":"10.3390\/a6010001","type":"journal-article","created":{"date-parts":[[2012,12,27]],"date-time":"2012-12-27T11:08:31Z","timestamp":1356606511000},"page":"1-11","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Maximum Disjoint Paths on Edge-Colored Graphs: Approximability and Tractability"],"prefix":"10.3390","volume":"6","author":[{"given":"Paola","family":"Bonizzoni","sequence":"first","affiliation":[{"name":"Department of Computer Systems and Communication, University of Milan-Bicocca, Viale Sarca 336, Milan, Italy"}]},{"given":"Riccardo","family":"Dondi","sequence":"additional","affiliation":[{"name":"Department of Humanities and Social Sciences, University of Bergamo, Via Donizzetti 3, Bergamo, Italy"}]},{"given":"Yuri","family":"Pirola","sequence":"additional","affiliation":[{"name":"Department of Computer Systems and Communication, University of Milan-Bicocca, Viale Sarca 336, Milan, Italy"}]}],"member":"1968","published-online":{"date-parts":[[2012,12,27]]},"reference":[{"key":"ref_1","unstructured":"Scott, J., and Carrington, P.J. (2011). The SAGE Handbook of Social Network Analysis, SAGE Publications Ltd."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Wasserman, S., and Faust, K. (1994). Social Network Analysis: Methods and Applications (Structural Analysis in the Social Sciences), Cambridge University Press.","DOI":"10.1017\/CBO9780511815478"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1016\/j.disopt.2012.01.002","article-title":"On the maximum disjoint paths problem on edge-colored graphs","volume":"9","author":"Wu","year":"2012","journal-title":"Discret. Optim."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Ausiello, G., Crescenzi, P., Gambosi, V., Kann, G., Marchetti-Spaccamela, A., and Protasi, M. (1999). Complexity and Approximation: Combinatorial Optimization Problems and their Approximability Properties, Springer-Verlag.","DOI":"10.1007\/978-3-642-58412-1"},{"key":"ref_5","unstructured":"Zuckerman, D. Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number. Proceedings of the 38th Annual ACM Symposium on Theory of Computing."},{"key":"ref_6","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_7","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1016\/0304-3975(94)00097-3","article-title":"Fixed-parameter tractability and completeness II: On completeness for W[1]","volume":"141","author":"Downey","year":"1995","journal-title":"Theor. Comput. Sci."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"844","DOI":"10.1145\/210332.210337","article-title":"Color-coding","volume":"42","author":"Alon","year":"1995","journal-title":"J. ACM"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"799","DOI":"10.1016\/j.jcss.2010.07.003","article-title":"Upper and lower bounds for finding connected motifs in vertex-colored graphs","volume":"77","author":"Fellows","year":"2011","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"1296","DOI":"10.1109\/TCBB.2011.19","article-title":"Parameterized algorithmics for finding connected motifs in biological networks","volume":"8","author":"Betzler","year":"2011","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinf."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"82","DOI":"10.1016\/j.jda.2010.09.002","article-title":"Complexity issues in vertex-colored graph pattern matching","volume":"9","author":"Dondi","year":"2011","journal-title":"J. Discret. Algorithms"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1007\/s00453-007-9008-7","article-title":"Algorithm engineering for color-coding with applications to signaling pathway detection","volume":"52","author":"Wernicke","year":"2008","journal-title":"Algorithmica"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"877","DOI":"10.1016\/j.ipl.2010.07.015","article-title":"Variants of constrained longest common subsequence","volume":"110","author":"Bonizzoni","year":"2010","journal-title":"Inf. Process. Lett."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1016\/j.ipl.2004.12.005","article-title":"A faster parameterized algorithm for set packing","volume":"94","author":"Koutis","year":"2005","journal-title":"Inf. Process. Lett."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1007\/s00453-007-9146-y","article-title":"Faster fixed-parameter tractable algorithms for matching and packing problems","volume":"52","author":"Fellows","year":"2008","journal-title":"Algorithmica"},{"key":"ref_16","unstructured":"Bansal, N., Pruhs, K., and Stein, C. (2007). SODA, SIAM."},{"key":"ref_17","first-page":"1","article-title":"Balanced Hashing, Color Coding and Approximate Counting","volume":"Volume 5917","author":"Chen","year":"2009","journal-title":"IWPEC"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/6\/1\/1\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T21:54:32Z","timestamp":1760219672000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/6\/1\/1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,12,27]]},"references-count":17,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2013,3]]}},"alternative-id":["a6010001"],"URL":"https:\/\/doi.org\/10.3390\/a6010001","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2012,12,27]]}}}