{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:42:05Z","timestamp":1740109325135,"version":"3.37.3"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2022,1,4]],"date-time":"2022-01-04T00:00:00Z","timestamp":1641254400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,1,4]],"date-time":"2022-01-04T00:00:00Z","timestamp":1641254400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100009935","name":"Indo-French Centre for Applied Mathematics","doi-asserted-by":"crossref","award":["MA\/IFCAM\/18\/39"],"award-info":[{"award-number":["MA\/IFCAM\/18\/39"]}],"id":[{"id":"10.13039\/100009935","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,5]]},"DOI":"10.1007\/s00453-021-00918-4","type":"journal-article","created":{"date-parts":[[2022,1,4]],"date-time":"2022-01-04T14:05:19Z","timestamp":1641305119000},"page":"1183-1212","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Graph Modification for Edge-Coloured and Signed Graph Homomorphism Problems: Parameterized and Classical Complexity"],"prefix":"10.1007","volume":"84","author":[{"given":"Florent","family":"Foucaud","sequence":"first","affiliation":[]},{"given":"Herv\u00e9","family":"Hocquard","sequence":"additional","affiliation":[]},{"given":"Dimitri","family":"Lajou","sequence":"additional","affiliation":[]},{"given":"Valia","family":"Mitsou","sequence":"additional","affiliation":[]},{"given":"Th\u00e9o","family":"Pierron","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,1,4]]},"reference":[{"issue":"1","key":"918_CR1","first-page":"21","volume":"29","author":"Z Bawar","year":"2005","unstructured":"Bawar, Z., Brewster, R.C., Marcotte, D.A.: Homomorphism duality in edge-coloured graphs. Annales des sciences math\u00e9matiques du Qu\u00e9bec 29(1), 21\u201334 (2005)","journal-title":"Annales des sciences math\u00e9matiques du Qu\u00e9bec"},{"key":"918_CR2","unstructured":"Bok, J., Brewster, R. C., Feder, T., Hell, P., and Jedlickov\u00e1, N.: List homomorphism problems for signed graphs. Proceedings of the 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020), Leibniz International Proceedings in Informatics (LIPIcs) 170, 20:1\u201320:14, (2020)"},{"key":"918_CR3","unstructured":"Brewster, R. C.: Vertex colourings of edge-coloured graphs, PhD thesis, Simon Fraser University, Canada,(1993)"},{"issue":"1\u20133","key":"918_CR4","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/0166-218X(94)90203-8","volume":"49","author":"RC Brewster","year":"1994","unstructured":"Brewster, R.C.: The complexity of colouring symmetric relational systems. Discrete Appl. Math. 49(1\u20133), 95\u2013105 (1994)","journal-title":"Discrete Appl. Math."},{"key":"918_CR5","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/j.disc.2004.10.026","volume":"297","author":"RC Brewster","year":"2005","unstructured":"Brewster, R.C., Dedi\u0107, R., Huard, F., Queen, J.: The recognition of bound quivers using edge-coloured homomorphisms. Discrete Math. 297, 13\u201325 (2005)","journal-title":"Discrete Math."},{"issue":"2","key":"918_CR6","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1016\/j.disc.2016.08.005","volume":"340","author":"RC Brewster","year":"2017","unstructured":"Brewster, R.C., Foucaud, F., Hell, P., Naserasr, R.: The complexity of signed and edge-coloured graph homomorphisms. Discrete Math. 340(2), 223\u2013235 (2017)","journal-title":"Discrete Math."},{"issue":"10","key":"918_CR7","doi-asserted-by":"publisher","first-page":"2768","DOI":"10.1016\/j.disc.2018.06.026","volume":"341","author":"RC Brewster","year":"2018","unstructured":"Brewster, R.C., Siggers, M.H.: A complexity dichotomy for signed $$H$$-colouring. Discrete Math. 341(10), 2768\u20132773 (2018)","journal-title":"Discrete Math."},{"key":"918_CR8","doi-asserted-by":"crossref","unstructured":"Bulatov, A. A.: A dichotomy theorem for nonuniform CSPs. Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science (FOCS 2017), IEEE Computer Society, pp. 319\u2013330, (2017)","DOI":"10.1109\/FOCS.2017.37"},{"issue":"2","key":"918_CR9","doi-asserted-by":"publisher","first-page":"573","DOI":"10.1137\/120882160","volume":"43","author":"AA Bulatov","year":"2014","unstructured":"Bulatov, A.A., Marx, D.: Constraint satisfaction parameterized by solution size. SIAM J. Comput. 43(2), 573\u2013616 (2014)","journal-title":"SIAM J. Comput."},{"key":"918_CR10","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1016\/j.ejc.2017.10.001","volume":"69","author":"J Bul\u00edn","year":"2018","unstructured":"Bul\u00edn, J.: On the complexity of H-coloring for special oriented trees. Eur. J. Comb. 69, 54\u201375 (2018)","journal-title":"Eur. J. Comb."},{"key":"918_CR11","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/0020-0190(96)00050-6","volume":"58","author":"L Cai","year":"1996","unstructured":"Cai, L.: Fixed parameter tractability of graph modification problem for hereditary properties. Information Process. Lett. 58, 171\u2013176 (1996)","journal-title":"Information Process. Lett."},{"key":"918_CR12","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1007\/s00453-016-0139-6","volume":"78","author":"R Chitnis","year":"2017","unstructured":"Chitnis, R., Egri, L., Marx, D.: List H-Coloring a graph by removing few vertices. Algorithmica 78, 110\u2013146 (2017)","journal-title":"Algorithmica"},{"issue":"8","key":"918_CR13","doi-asserted-by":"publisher","first-page":"1346","DOI":"10.1016\/j.jcss.2006.04.007","volume":"72","author":"J Chen","year":"2006","unstructured":"Chen, J., Huang, X., Kanj, I.A., Xia, G.: Strong computational lower bounds via parameterized complexity. J. Computer Syst. Sci. 72(8), 1346\u20131367 (2006)","journal-title":"J. Computer Syst. Sci."},{"key":"918_CR14","doi-asserted-by":"publisher","first-page":"415","DOI":"10.1016\/S0166-218X(02)00242-1","volume":"127","author":"L Cai","year":"2003","unstructured":"Cai, L.: Parameterized complexity of vertex colouring. Discrete Appl. Math. 127, 415\u2013429 (2003)","journal-title":"Discrete Appl. Math."},{"key":"918_CR15","unstructured":"Crespelle, C., Drange, P. G., Fomin, F. V., and Golovach, P. A.: A survey of parameterized algorithms and the complexity of edge modification problems. Manuscript, (2020). https:\/\/arxiv.org\/abs\/2001.06867"},{"key":"918_CR16","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, New York (2015)"},{"key":"918_CR17","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of Parameterized Complexity","author":"RG Downey","year":"2013","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Springer, New York (2013)"},{"key":"918_CR18","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1016\/j.dam.2020.03.029","volume":"284","author":"F Dross","year":"2020","unstructured":"Dross, F., Foucaud, F., Mitsou, V., Ochem, P., Pierron, T.: Complexity of planar signed graph homomorphisms to cycles. Discrete Appl. Math. 284, 166\u2013178 (2020)","journal-title":"Discrete Appl. Math."},{"key":"918_CR19","doi-asserted-by":"crossref","unstructured":"Ehrenfeucht, A., Hage, J., Harju, T., and Rozenberg, G.: Complexity issues in switching of graphs. Proceedings of the International Workshop on Theory and Application of Graph Transformations, TAGT\u201998, Lecture Notes in Computer Science 1764:59\u201370, (2000)","DOI":"10.1007\/978-3-540-46464-8_5"},{"issue":"1","key":"918_CR20","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1137\/S0097539794266766","volume":"28","author":"T Feder","year":"1998","unstructured":"Feder, T., Vardi, M.Y.: The computational structure of monotone monadic SNP and constraint satisfaction: a study through datalog and group theory. SIAM J. Comput. 28(1), 57\u2013104 (1998)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"918_CR21","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/j.tcs.2008.09.065","volume":"40","author":"MR Fellows","year":"2009","unstructured":"Fellows, M.R., Hermelin, D., Rosamond, F., Vialette, S.: On the parameterized complexity of multiple-interval graph problems. Theor. Computer Sci. 40(1), 53\u201361 (2009)","journal-title":"Theor. Computer Sci."},{"key":"918_CR22","unstructured":"Foucaud, F., Hocquard, H., Lajou, D., Mitsou, V., and Pierron, T.: Parameterized complexity of edge-coloured and signed graph homomorphism problems. Proceedings of the 14th International Symposium on Parameterized and Exact Computation (IPEC 2019). Leibniz International Proceedings in Informatics (LIPIcs) 148,15:1-15:16, (2019)"},{"key":"918_CR23","doi-asserted-by":"crossref","unstructured":"Foucaud, F., and Naserasr, R.: The complexity of homomorphisms of signed graphs and signed constraint satisfaction. Proceedings of the 11th Latin American Symposium on Theoretical Informatics 2014, LATIN\u201914. Lecture Notes in Computer Science 8392:526\u2013537, (2014)","DOI":"10.1007\/978-3-642-54423-1_46"},{"key":"918_CR24","doi-asserted-by":"crossref","unstructured":"Harary, F.: On the notion of balance of a signed graph. Mich. Math. J. 2(2):143\u2013146, 1953-1954","DOI":"10.1307\/mmj\/1028989917"},{"issue":"1","key":"918_CR25","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1016\/0095-8956(90)90132-J","volume":"48","author":"P Hell","year":"1990","unstructured":"Hell, P., Ne\u0161et\u0159il, J.: On the complexity of $$H$$-coloring. J. Comb. Theory Series B 48(1), 92\u2013110 (1990)","journal-title":"J. Comb. Theory Series B"},{"issue":"4","key":"918_CR26","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1007\/s10878-009-9212-2","volume":"20","author":"F H\u00fcffner","year":"2010","unstructured":"H\u00fcffner, F., Betzler, N., Niedermeier, R.: Separator-based data reduction for signed graph balancing. J. Comb. Optim. 20(4), 335\u2013360 (2010)","journal-title":"J. Comb. Optim."},{"issue":"4","key":"918_CR27","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. Computer Syst. Sci. 63(4), 512\u2013530 (2001)","journal-title":"J. Computer Syst. Sci."},{"key":"918_CR28","doi-asserted-by":"crossref","unstructured":"Jaffke, L., and Jansen, B. M. P.: Fine-grained parameterized complexity analysis of graph coloring problems. Proceedings of the 10th International Conference on Algorithms and Complexity (CIAC 2017). Lecture Notes in Computer Science 10236:345\u2013356, (2017)","DOI":"10.1007\/978-3-319-57586-5_29"},{"issue":"2","key":"918_CR29","first-page":"19","volume":"13","author":"E Jel\u00ednkov\u00e1","year":"2011","unstructured":"Jel\u00ednkov\u00e1, E., Such\u00fd, O., Hlin\u011bn\u00fd, P., Kratochv\u00edl, J.: Parameterized problems related to Seidel\u2019s switching. Discrete Math. Theor. Computer Sci. 13(2), 19\u201342 (2011)","journal-title":"Discrete Math. Theor. Computer Sci."},{"key":"918_CR30","doi-asserted-by":"crossref","unstructured":"Khanna, S., Sudan, M., Trevisan, L., and Williamson, D. P.: The approximability of constraint satisfaction problems. SIAM J. Comput. 30(6):1863\u20131920, 2006. 91:103215, (2021)","DOI":"10.1137\/S0097539799349948"},{"issue":"2","key":"918_CR31","doi-asserted-by":"publisher","first-page":"997","DOI":"10.1016\/S0304-3975(01)00414-5","volume":"289","author":"S Khot","year":"2002","unstructured":"Khot, S., Raman, V.: Parameterized complexity of finding subgraphs with hereditary properties. Theor. Computer Sci. 289(2), 997\u20131008 (2002)","journal-title":"Theor. Computer Sci."},{"issue":"2","key":"918_CR32","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/0022-0000(80)90060-4","volume":"20","author":"JM Lewis","year":"1980","unstructured":"Lewis, J.M., Yannakakis, M.: The node-deletion problem for hereditary properties is NP-complete. J. Computer Syst. Sci. 20(2), 219\u2013230 (1980)","journal-title":"J. Computer Syst. Sci."},{"issue":"3","key":"918_CR33","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1016\/j.tcs.2005.10.008","volume":"351","author":"D Marx","year":"2006","unstructured":"Marx, D.: Parameterized coloring problems on chordal graphs. Theor. Computer Sci. 351(3), 407\u2013424 (2006)","journal-title":"Theor. Computer Sci."},{"issue":"3","key":"918_CR34","doi-asserted-by":"publisher","first-page":"178","DOI":"10.1002\/jgt.21817","volume":"79","author":"R Naserasr","year":"2015","unstructured":"Naserasr, R., Rollov\u00e1, E., Sopena, \u00c9.: Homomorphisms of signed graphs. J. Graph Theory 79(3), 178\u2013212 (2015)","journal-title":"J. Graph Theory"},{"key":"918_CR35","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1016\/j.jcss.2019.12.004","volume":"109","author":"K Okrasa","year":"2020","unstructured":"Okrasa, K., Rz\u0105\u017cewski, P.: Subexponential algorithms for variants of the homomorphism problem in string graphs. J. Computer Syst. Sci. 109, 126\u2013144 (2020)","journal-title":"J. Computer Syst. Sci."},{"issue":"4","key":"918_CR36","doi-asserted-by":"publisher","first-page":"757","DOI":"10.1016\/S0022-0000(03)00078-3","volume":"67","author":"K Pietrzak","year":"2003","unstructured":"Pietrzak, K.: On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems. J. Computer Syst. Sci. 67(4), 757\u2013771 (2003)","journal-title":"J. Computer Syst. Sci."},{"issue":"8","key":"918_CR37","doi-asserted-by":"publisher","first-page":"435","DOI":"10.1016\/j.jcss.2009.04.002","volume":"75","author":"I Razgon","year":"2009","unstructured":"Razgon, I., O\u2019Sullivan, B.: Almost 2-SAT is fixed-parameter tractable. J. Computer Syst. Sci. 75(8), 435\u2013450 (2009)","journal-title":"J. Computer Syst. Sci."},{"key":"918_CR38","doi-asserted-by":"crossref","unstructured":"Takenaga, Y., and Higashide, K.: Vertex coloring of comparability $$+ke$$ and $$-ke$$ graphs. Proceedings of the 32nd International Worksop on Graph-Theoretic Concepts in Computer Science, WG\u201906. Lecture Notes in Computer Science 4271:102\u2013112, (2006)","DOI":"10.1007\/11917496_10"},{"issue":"2","key":"918_CR39","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1137\/0210021","volume":"10","author":"M Yannakakis","year":"1981","unstructured":"Yannakakis, M.: Edge-deletion problems. SIAM J. Comput. 10(2), 297\u2013309 (1981)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"918_CR40","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/0166-218X(82)90033-6","volume":"4","author":"T Zaslavsky","year":"1982","unstructured":"Zaslavsky, T.: Signed graphs. Discrete Appl. Math. 4(1), 47\u201374 (1982)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"918_CR41","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/j.akcej.2018.01.011","volume":"15","author":"T Zaslavsky","year":"2018","unstructured":"Zaslavsky, T.: Negative (and positive) circles in signed graphs: a problem collection. AKCE Int. J. Graphs Comb. 15(1), 31\u201348 (2018)","journal-title":"AKCE Int. J. Graphs Comb."},{"key":"918_CR42","doi-asserted-by":"crossref","unstructured":"Zhuk, D.: A Proof of the CSP Dichotomy Conjecture. J. ACM 67(5), 30:1\u201330:78, (2020)","DOI":"10.1145\/3402029"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00918-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-021-00918-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00918-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,4,28]],"date-time":"2022-04-28T05:03:36Z","timestamp":1651122216000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-021-00918-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,4]]},"references-count":42,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2022,5]]}},"alternative-id":["918"],"URL":"https:\/\/doi.org\/10.1007\/s00453-021-00918-4","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2022,1,4]]},"assertion":[{"value":"6 March 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 December 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 January 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}