{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,9]],"date-time":"2026-03-09T21:52:17Z","timestamp":1773093137042,"version":"3.50.1"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2016,4,27]],"date-time":"2016-04-27T00:00:00Z","timestamp":1461715200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2016,4,27]],"date-time":"2016-04-27T00:00:00Z","timestamp":1461715200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["280152"],"award-info":[{"award-number":["280152"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003549","name":"Orsz\u00e1gos Tudom\u00e1nyos Kutat\u00e1si Alapprogramok","doi-asserted-by":"publisher","award":["NK105645"],"award-info":[{"award-number":["NK105645"]}],"id":[{"id":"10.13039\/501100003549","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CAREER 1053605"],"award-info":[{"award-number":["CAREER 1053605"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-11616226"],"award-info":[{"award-number":["CCF-11616226"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["N000141110662"],"award-info":[{"award-number":["N000141110662"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000185","name":"Defense Advanced Research Projects Agency","doi-asserted-by":"publisher","award":["FA9550-12-1-0423"],"award-info":[{"award-number":["FA9550-12-1-0423"]}],"id":[{"id":"10.13039\/100000185","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2017,5]]},"DOI":"10.1007\/s00453-016-0139-6","type":"journal-article","created":{"date-parts":[[2016,4,28]],"date-time":"2016-04-28T16:11:34Z","timestamp":1461859894000},"page":"110-146","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":16,"title":["List H-Coloring a Graph by Removing Few Vertices"],"prefix":"10.1007","volume":"78","author":[{"given":"Rajesh","family":"Chitnis","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"L\u00e1szl\u00f3","family":"Egri","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"D\u00e1niel","family":"Marx","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,4,27]]},"reference":[{"key":"139_CR1","doi-asserted-by":"crossref","unstructured":"Chen, Y., Grohe, M., Gr\u00fcber, M.: On parameterized approximability. In: Parameterized and Exact Computation, Second International Workshop, IWPEC 2006, Z\u00fcrich, Switzerland, 13\u201315 Sept 2006, Proceedings, pp. 109\u2013120 (2006)","DOI":"10.1007\/11847250_10"},{"issue":"4","key":"139_CR2","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1145\/2700209","volume":"11","author":"RH Chitnis","year":"2015","unstructured":"Chitnis, R.H., Cygan, M., Hajiaghayi, M.T., Marx, D.: Directed subset feedback vertex set is fixed-parameter tractable. ACM Trans. Algorithms 11(4), 28 (2015)","journal-title":"ACM Trans. Algorithms"},{"issue":"4","key":"139_CR3","doi-asserted-by":"publisher","first-page":"1674","DOI":"10.1137\/12086217X","volume":"42","author":"RH Chitnis","year":"2013","unstructured":"Chitnis, R.H., Hajiaghayi, M., Marx, D.: Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset. SIAM J. Comput. 42(4), 1674\u20131696 (2013)","journal-title":"SIAM J. Comput."},{"key":"139_CR4","first-page":"193","volume-title":"Handbook of Theoretical Computer Science: Volume B: Formal Models and Semantics","author":"B Courcelle","year":"1990","unstructured":"Courcelle, B.: Graph rewriting: an algebraic and logic approach. In: van Leeuwen, J. (ed.) Handbook of Theoretical Computer Science: Volume B: Formal Models and Semantics, pp. 193\u2013242. Elsevier, Amsterdam (1990)"},{"issue":"1","key":"139_CR5","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1145\/2462896.2462899","volume":"5","author":"M Cygan","year":"2013","unstructured":"Cygan, M., Pilipczuk, M., Pilipczuk, M., Wojtaszczyk, J.O.: On multiway cut parameterized above lower bounds. ACM Trans. Comput. Theory 5(1), 3 (2013)","journal-title":"ACM Trans. Comput. Theory"},{"key":"139_CR6","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of Parameterized Complexity. Texts in Computer Science","author":"RG Downey","year":"2013","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, New York (2013)"},{"key":"139_CR7","doi-asserted-by":"crossref","unstructured":"Egri, L., Hell, P., Larose, B., Rafiey, A.: Space complexity of list H-colouring: a dichotomy. In: Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, 5\u20137 Jan 2014, pp. 349\u2013365 (2014)","DOI":"10.1137\/1.9781611973402.26"},{"issue":"2","key":"139_CR8","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1007\/s00224-011-9333-8","volume":"51","author":"L Egri","year":"2012","unstructured":"Egri, L., Krokhin, A.A., Larose, B., Tesson, P.: The complexity of the list homomorphism problem for graphs. Theory Comput. Syst. 51(2), 143\u2013178 (2012)","journal-title":"Theory Comput. Syst."},{"issue":"2","key":"139_CR9","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1006\/jctb.1997.1812","volume":"72","author":"T Feder","year":"1998","unstructured":"Feder, T., Hell, P.: List homomorphisms to reflexive graphs. J. Comb. Theory Ser. B 72(2), 236\u2013250 (1998)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"4","key":"139_CR10","doi-asserted-by":"publisher","first-page":"487","DOI":"10.1007\/s004939970003","volume":"19","author":"T Feder","year":"1999","unstructured":"Feder, T., Hell, P., Huang, J.: List homomorphisms and circular arc graphs. Combinatorica 19(4), 487\u2013505 (1999)","journal-title":"Combinatorica"},{"issue":"1","key":"139_CR11","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1002\/jgt.10073","volume":"42","author":"T Feder","year":"2003","unstructured":"Feder, T., Hell, P., Huang, J.: Bi-arc graphs and the complexity of list homomorphisms. J. Graph Theory 42(1), 61\u201380 (2003)","journal-title":"J. Graph Theory"},{"key":"139_CR12","doi-asserted-by":"publisher","first-page":"386","DOI":"10.1016\/j.disc.2005.09.030","volume":"307","author":"T Feder","year":"2007","unstructured":"Feder, T., Hell, P., Huang, J.: List homomorphisms of graphs with bounded degrees. Discrete Math. 307, 386\u2013392 (2007)","journal-title":"Discrete Math."},{"issue":"1","key":"139_CR13","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":"6","key":"139_CR14","doi-asserted-by":"publisher","first-page":"716","DOI":"10.1145\/602220.602222","volume":"49","author":"J Flum","year":"2002","unstructured":"Flum, J., Frick, M., Grohe, M.: Query evaluation via tree-decompositions. J. ACM 49(6), 716\u2013752 (2002)","journal-title":"J. ACM"},{"key":"139_CR15","volume-title":"Parameterized Complexity Theory","author":"J Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, New York (2006)"},{"key":"139_CR16","doi-asserted-by":"publisher","first-page":"890","DOI":"10.1016\/j.dam.2005.11.006","volume":"154","author":"G Gutin","year":"2006","unstructured":"Gutin, G., Rafiey, A., Yeo, A.: Minimum cost and list homomorphisms to semicomplete digraphs. Discrete Appl. Math. 154, 890\u2013897 (2006)","journal-title":"Discrete Appl. Math."},{"key":"139_CR17","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198528173.001.0001","volume-title":"Graphs and Homomorphisms","author":"P Hell","year":"2004","unstructured":"Hell, P., Ne\u0161et\u0159il, J.: Graphs and Homomorphisms. Oxford University Press, Oxford (2004)"},{"key":"139_CR18","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 Ser. B 48, 92\u2013110 (1990)","journal-title":"J. Comb. Theory Ser. B"},{"key":"139_CR19","doi-asserted-by":"crossref","unstructured":"Hell, P., Rafiey, A.: The dichotomy of list homomorphisms for digraphs. In: Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, California, USA, 23\u201325 Jan 2011, pp. 1703\u20131713 (2011)","DOI":"10.1137\/1.9781611973082.131"},{"issue":"1","key":"139_CR20","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1137\/120904202","volume":"29","author":"S Kratsch","year":"2015","unstructured":"Kratsch, S., Pilipczuk, M., Pilipczuk, M., Wahlstr\u00f6m, M.: Fixed-parameter tractability of multicut in directed acyclic graphs. SIAM J. Discrete Math. 29(1), 122\u2013144 (2015)","journal-title":"SIAM J. Discrete Math."},{"key":"139_CR21","doi-asserted-by":"publisher","first-page":"278","DOI":"10.1016\/j.ic.2012.10.016","volume":"222","author":"D Lokshtanov","year":"2013","unstructured":"Lokshtanov, D., Marx, D.: Clustering with local restrictions. Inf. Comput. 222, 278\u2013292 (2013)","journal-title":"Inf. Comput."},{"issue":"2","key":"139_CR22","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1145\/2566616","volume":"11","author":"D Lokshtanov","year":"2014","unstructured":"Lokshtanov, D., Narayanaswamy, N.S., Raman, V., Ramanujan, M.S., Saurabh, S.: Faster parameterized algorithms using linear programming. ACM Trans. Algorithms 11(2), 15 (2014)","journal-title":"ACM Trans. Algorithms"},{"key":"139_CR23","doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., Ramanujan, M.S.: Parameterized tractability of multiway cut with parity constraints. In: Automata, Languages, and Programming\u201439th International Colloquium, ICALP 2012, Warwick, UK, 9\u201313 July 2012, Part I, pp. 750\u2013761 (2012)","DOI":"10.1007\/978-3-642-31594-7_63"},{"issue":"3","key":"139_CR24","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1016\/j.tcs.2005.10.007","volume":"351","author":"D Marx","year":"2006","unstructured":"Marx, D.: Parameterized graph separation problems. Theor. Comput. Sci. 351(3), 394\u2013406 (2006)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"139_CR25","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1093\/comjnl\/bxm048","volume":"51","author":"D Marx","year":"2008","unstructured":"Marx, D.: Parameterized complexity and approximation algorithms. Comput. J. 51(1), 60\u201378 (2008)","journal-title":"Comput. J."},{"issue":"4","key":"139_CR26","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1145\/2500119","volume":"9","author":"D Marx","year":"2013","unstructured":"Marx, D., O\u2019Sullivan, B., Razgon, I.: Finding small separators in linear time via treewidth reduction. ACM Trans. Algorithms 9(4), 30 (2013)","journal-title":"ACM Trans. Algorithms"},{"issue":"2","key":"139_CR27","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1137\/110855247","volume":"43","author":"D Marx","year":"2014","unstructured":"Marx, D., Razgon, I.: Fixed-parameter tractability of multicut parameterized by the size of the cutset. SIAM J. Comput. 43(2), 355\u2013388 (2014)","journal-title":"SIAM J. Comput."},{"key":"139_CR28","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to Fixed-Parameter Algorithms","author":"R Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press, Oxford (2006)"},{"issue":"8","key":"139_CR29","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. Comput. Syst. Sci. 75(8), 435\u2013450 (2009)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"139_CR30","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1016\/j.orl.2003.10.009","volume":"32","author":"BA Reed","year":"2004","unstructured":"Reed, B.A., Smith, K., Vetta, A.: Finding odd cycle transversals. Oper. Res. Lett. 32(4), 299\u2013301 (2004)","journal-title":"Oper. Res. Lett."},{"issue":"3","key":"139_CR31","doi-asserted-by":"publisher","first-page":"300","DOI":"10.1016\/0095-8956(88)90038-X","volume":"44","author":"J Spinrad","year":"1988","unstructured":"Spinrad, J.: Circular-arc graphs with clique cover number two. J. Comb. Theory Ser. B 44(3), 300\u2013306 (1988)","journal-title":"J. Comb. Theory Ser. B"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0139-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-016-0139-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0139-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0139-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,6,19]],"date-time":"2022-06-19T01:08:35Z","timestamp":1655600915000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-016-0139-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,4,27]]},"references-count":31,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,5]]}},"alternative-id":["139"],"URL":"https:\/\/doi.org\/10.1007\/s00453-016-0139-6","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,4,27]]},"assertion":[{"value":"17 January 2014","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 February 2016","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 April 2016","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}