{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,2]],"date-time":"2025-12-02T06:16:57Z","timestamp":1764656217592,"version":"3.37.3"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2022,9,22]],"date-time":"2022-09-22T00:00:00Z","timestamp":1663804800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,9,22]],"date-time":"2022-09-22T00:00:00Z","timestamp":1663804800000},"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":["KO 3669\/5-1"],"award-info":[{"award-number":["KO 3669\/5-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["KO 3669\/6-1"],"award-info":[{"award-number":["KO 3669\/6-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100008967","name":"Philipps-Universit\u00e4t Marburg","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100008967","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2022,10]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In the NP-hard <jats:sc>Colored<\/jats:sc> (<jats:italic>s<\/jats:italic>,<jats:italic>t<\/jats:italic>)-<jats:sc>Cut<\/jats:sc> problem, the input is a graph <jats:italic>G<\/jats:italic> = (<jats:italic>V<\/jats:italic>,<jats:italic>E<\/jats:italic>) together with an edge-coloring <jats:italic>\u2113<\/jats:italic> : <jats:italic>E<\/jats:italic> \u2192 <jats:italic>C<\/jats:italic>, two vertices <jats:italic>s<\/jats:italic> and <jats:italic>t<\/jats:italic>, and a number <jats:italic>k<\/jats:italic>. The question is whether there is a set <jats:inline-formula><jats:alternatives><jats:tex-math>$S\\subseteq C$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>S<\/mml:mi>\n                  <mml:mo>\u2286<\/mml:mo>\n                  <mml:mi>C<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> of at most <jats:italic>k<\/jats:italic> colors such that deleting every edge with a color from <jats:italic>S<\/jats:italic> destroys all paths between <jats:italic>s<\/jats:italic> and <jats:italic>t<\/jats:italic> in <jats:italic>G<\/jats:italic>. We continue the study of the parameterized complexity of <jats:sc>Colored<\/jats:sc> (<jats:italic>s<\/jats:italic>,<jats:italic>t<\/jats:italic>)-<jats:sc>Cut<\/jats:sc>. First, we consider parameters related to the structure of <jats:italic>G<\/jats:italic>. For example, we study parameterization by the number <jats:italic>\u03be<\/jats:italic><jats:sub><jats:italic>i<\/jats:italic><\/jats:sub> of edge deletions that are needed to transform <jats:italic>G<\/jats:italic> into a graph with maximum degree <jats:italic>i<\/jats:italic>. We show that <jats:sc>Colored<\/jats:sc> (<jats:italic>s<\/jats:italic>,<jats:italic>t<\/jats:italic>)-<jats:sc>Cut<\/jats:sc> is W[2]-hard when parameterized by <jats:italic>\u03be<\/jats:italic><jats:sub>3<\/jats:sub>, but fixed-parameter tractable when parameterized by <jats:italic>\u03be<\/jats:italic><jats:sub>2<\/jats:sub>. Second, we consider parameters related to the coloring <jats:italic>\u2113<\/jats:italic>. We show fixed-parameter tractability for three parameters that are potentially smaller than the total number of colors |<jats:italic>C<\/jats:italic>| and provide a linear-size problem kernel for a parameter related to the number of edges with rare edge colors.<\/jats:p>","DOI":"10.1007\/s00224-022-10101-z","type":"journal-article","created":{"date-parts":[[2022,9,22]],"date-time":"2022-09-22T03:32:06Z","timestamp":1663817526000},"page":"1019-1045","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Refined Parameterizations for Computing Colored Cuts in Edge-Colored Graphs"],"prefix":"10.1007","volume":"66","author":[{"given":"Nils","family":"Morawietz","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6789-2918","authenticated-orcid":false,"given":"Niels","family":"Gr\u00fcttemeier","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0829-7032","authenticated-orcid":false,"given":"Christian","family":"Komusiewicz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4034-525X","authenticated-orcid":false,"given":"Frank","family":"Sommer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,9,22]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"Birmel\u00e9, E., Ferreira, R.A., Grossi, R., Marino, A., Pisanti, N., Rizzi, R., Sacomoto, G.: Optimal listing of cycles and st-paths in undirected graphs. In: Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA \u201913), pp. 1884\u20131896. SIAM (2013)","key":"10101_CR1","DOI":"10.1137\/1.9781611973105.134"},{"issue":"5","key":"10101_CR2","doi-asserted-by":"publisher","first-page":"1868","DOI":"10.1111\/itor.12494","volume":"26","author":"A Bordini","year":"2019","unstructured":"Bordini, A., Protti, F., da Silva, T.G., de Sousa Filho, G.F.: New algorithms for the minimum coloring cut problem. Int. Trans. Oper. Res. 26(5), 1868\u20131883 (2019)","journal-title":"Int. Trans. Oper. Res."},{"issue":"2","key":"10101_CR3","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1142\/S0129626407002958","volume":"17","author":"D Coudert","year":"2007","unstructured":"Coudert, D., Datta, P., Perennes, S., Rivano, H., Voge, M.: Shared risk resource group complexity and approximability issues. Parallel Processing Letters 17(2), 169\u2013184 (2007)","journal-title":"Parallel Processing Letters"},{"doi-asserted-by":"crossref","unstructured":"Coudert, D., P\u00e9rennes, S., Rivano, H., Voge, M.: Combinatorial optimization in networks with shared risk link groups. Discrete Mathematics & Theoretical Computer Science 18(3) (2016)","key":"10101_CR4","DOI":"10.46298\/dmtcs.1297"},{"issue":"3","key":"10101_CR5","first-page":"41,1","volume":"12","author":"M Cygan","year":"2016","unstructured":"Cygan, M., Dell, H., Lokshtanov, D., Marx, D., Nederlof, J., Okamoto, Y., Paturi, R., Saurabh, S., Wahlstr\u00f6m, M.: On problems as hard as CNF-SAT. ACM Trans. Algor. 12(3), 41,1\u201341,24 (2016)","journal-title":"ACM Trans. Algor."},{"doi-asserted-by":"crossref","unstructured":"Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer (2015)","key":"10101_CR6","DOI":"10.1007\/978-3-319-21275-3"},{"issue":"2","key":"10101_CR7","first-page":"13,1","volume":"11","author":"M Dom","year":"2014","unstructured":"Dom, M., Lokshtanov, D., Saurabh, S.: Kernelization lower bounds through colors and IDs. ACM Trans. Algor. 11(2), 13,1\u201313,20 (2014)","journal-title":"ACM Trans. Algor."},{"doi-asserted-by":"crossref","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity Texts in Computer Science. Springer (2013)","key":"10101_CR8","DOI":"10.1007\/978-1-4471-5559-1"},{"unstructured":"Farag\u00f3, A.: A graph theoretic model for complex network failure scenarios. In: Proceedings of the 8th INFORMS Telecommunications Conference (INFORMS \u201908) (2006)","key":"10101_CR9"},{"issue":"8","key":"10101_CR10","doi-asserted-by":"publisher","first-page":"727","DOI":"10.1016\/j.jcss.2010.02.012","volume":"76","author":"MR Fellows","year":"2010","unstructured":"Fellows, M.R., Guo, J., Kanj, I.A.: The parameterized complexity of some minimum label problems. J. Comput. Syst. Sci. 76(8), 727\u2013740 (2010)","journal-title":"J. Comput. Syst. Sci."},{"unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Texts in Theoretical Computer Science An EATCS Series. Springer (2006)","key":"10101_CR11"},{"doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Kratsch, D., Woeginger, G.J.: Exact (exponential) algorithms for the dominating set problem. In: Proceedings of the 30th International Workshop on Graph-Theoretic Concepts in Computer Science (WG \u201904), volume 3353 of Lecture Notes in Computer Science, pp. 245\u2013256. Springer (2004)","key":"10101_CR12","DOI":"10.1007\/978-3-540-30559-0_21"},{"issue":"4","key":"10101_CR13","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63(4), 512\u2013530 (2001)","journal-title":"J. Comput. Syst. Sci."},{"unstructured":"Jha, S., Sheyner, O., Wing, J.: Two formal analyses of attack graphs. In: Proceedings ot the 15th IEEE Computer Security Foundations Workshop (CSWF \u201902), pp. 49\u201363. IEEE (2002)","key":"10101_CR14"},{"issue":"2","key":"10101_CR15","doi-asserted-by":"publisher","first-page":"424","DOI":"10.1016\/j.jctb.2011.07.004","volume":"102","author":"K Kawarabayashi","year":"2012","unstructured":"Kawarabayashi, K., Kobayashi, Y., Reed, B.A.: The disjoint paths problem in quadratic time. J. Comb. Theory. Series B 102(2), 424\u2013435 (2012)","journal-title":"J. Comb. Theory. Series B"},{"doi-asserted-by":"crossref","unstructured":"Klein, S., Faria, L., Sau, I., Sucupira, R., Souza, U.: On colored edge cuts in graphs. In: Proceedings of the 1st Encontro de Teoria da Computa\u010bao (ETC \u201916), Sociedade Brasileira de Computa\u00e7ao, pp. 780\u2013783. CSBC (2016)","key":"10101_CR16","DOI":"10.5753\/etc.2016.9764"},{"key":"10101_CR17","volume-title":"Computational Complexity of Network Robustness in Edge-colored Graphs","author":"N Morawietz","year":"2019","unstructured":"Morawietz, N.: Computational Complexity of Network Robustness in Edge-colored Graphs. Master\u2019s thesis, Philipps-Universit\u00e4t Marburg (2019)"},{"unstructured":"Morawietz, N., Gr\u00fcttemeier, N., Komusiewicz, C., Sommer, F.: Colored cut games. In: Proceedings of the 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS \u201920), volume 182 of LIPIcs, pp. 30:1\u201330:17. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2020)","key":"10101_CR18"},{"doi-asserted-by":"crossref","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press (2006)","key":"10101_CR19","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001"},{"doi-asserted-by":"crossref","unstructured":"Pi\u00f3ro, M., Medhi, D.: Routing, Flow, and Capacity Design in Communication and Computer Networks. Morgan Kaufmann (2004)","key":"10101_CR20","DOI":"10.1016\/B978-012557189-0\/50011-1"},{"issue":"1","key":"10101_CR21","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1007\/s10626-006-6187-3","volume":"16","author":"K Rohloff","year":"2006","unstructured":"Rohloff, K., Khuller, S., Kortsarz, G.: Approximating the minimal sensor selection for supervisory control. Discret. Event Dyn. Syst. 16 (1), 143\u2013170 (2006)","journal-title":"Discret. Event Dyn. Syst."},{"unstructured":"Sheyner, O., Haines, J.W., Jha, S., Lippmann, R., Wing, J.M.: Automated generation and analysis of attack graphs. In: Proceedings ot the 23rd Symposium on Security and Privacy (IEEE \u201902), pp. 273\u2013284. IEEE Computer Society (2002)","key":"10101_CR22"},{"key":"10101_CR23","volume-title":"Problemas de cortes de arestas maximos e m\u00ednimos em grafos","author":"RA Sucupira","year":"2017","unstructured":"Sucupira, R.A.: Problemas de cortes de arestas maximos e m\u00ednimos em grafos. Universidade Federal do Rio de Janeiro, PhD thesis (2017)"},{"issue":"13","key":"10101_CR24","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1016\/j.ipl.2011.03.017","volume":"111","author":"Y Wang","year":"2011","unstructured":"Wang, Y., Desmedt, Y.: Edge-colored graphs with applications to homogeneous faults. Inf. Process. Lett. 111(13), 634\u2013641 (2011)","journal-title":"Inf. Process. Lett."},{"unstructured":"Zhang, P.: Approximating the weighted minimum label s-t cut problem. arXiv:2011.06204 (2020)","key":"10101_CR25"},{"issue":"2","key":"10101_CR26","doi-asserted-by":"publisher","first-page":"192","DOI":"10.1007\/s10878-009-9222-0","volume":"21","author":"P Zhang","year":"2011","unstructured":"Zhang, P., Cai, J., Tang, L., Zhao, W.: Approximation and hardness results for label cut and related problems. J. Comb. Optim. 21(2), 192\u2013208 (2011)","journal-title":"J. Comb. Optim."},{"key":"10101_CR27","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1016\/j.tcs.2016.08.006","volume":"648","author":"P Zhang","year":"2016","unstructured":"Zhang, P., Fu, B.: The label cut problem with respect to path length and label frequency. Theor. Comput. Sci. 648, 72\u201383 (2016)","journal-title":"Theor. Comput. Sci."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-022-10101-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-022-10101-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-022-10101-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,29]],"date-time":"2022-09-29T07:03:45Z","timestamp":1664435025000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-022-10101-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,9,22]]},"references-count":27,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2022,10]]}},"alternative-id":["10101"],"URL":"https:\/\/doi.org\/10.1007\/s00224-022-10101-z","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2022,9,22]]},"assertion":[{"value":"10 August 2022","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 September 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}