{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,13]],"date-time":"2026-03-13T20:20:19Z","timestamp":1773433219873,"version":"3.50.1"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2019,7,18]],"date-time":"2019-07-18T00:00:00Z","timestamp":1563408000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,7,18]],"date-time":"2019-07-18T00:00:00Z","timestamp":1563408000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100006475","name":"Bergens Forskningsstiftelse","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100006475","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["648527"],"award-info":[{"award-number":["648527"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003725","name":"National Research Foundation of Korea","doi-asserted-by":"publisher","award":["NRF-2018R1D1A1B07050294"],"award-info":[{"award-number":["NRF-2018R1D1A1B07050294"]}],"id":[{"id":"10.13039\/501100003725","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2020,1]]},"DOI":"10.1007\/s00453-019-00607-3","type":"journal-article","created":{"date-parts":[[2019,7,18]],"date-time":"2019-07-18T06:02:51Z","timestamp":1563429771000},"page":"118-145","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":23,"title":["Mim-Width II. The Feedback Vertex Set Problem"],"prefix":"10.1007","volume":"82","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4856-5863","authenticated-orcid":false,"given":"Lars","family":"Jaffke","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"O-joung","family":"Kwon","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jan Arne","family":"Telle","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,7,18]]},"reference":[{"key":"607_CR1","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1016\/j.tcs.2013.01.011","volume":"511","author":"R Belmonte","year":"2013","unstructured":"Belmonte, R., Vatshelle, M.: Graph classes with structured neighborhoods and algorithmic applications. Theor. Comput. Sci. 511, 54\u201365 (2013)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"607_CR2","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1142\/S0129054194000049","volume":"5","author":"HL Bodlaender","year":"1994","unstructured":"Bodlaender, H.L.: On disjoint cycles. Int. J. Found. Comput. Sci. 5(1), 59\u201368 (1994)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"607_CR3","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/j.ic.2014.12.008","volume":"243","author":"HL Bodlaender","year":"2015","unstructured":"Bodlaender, H.L., Cygan, M., Kratsch, S., Nederlof, J.: Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. Inf. Comput. 243, 86\u2013111 (2015)","journal-title":"Inf. Comput."},{"key":"607_CR4","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719796","volume-title":"Graph Classes: A Survey","author":"A Brandst\u00e4dt","year":"1999","unstructured":"Brandst\u00e4dt, A., Le, V.B., Spinrad, J.P.: Graph Classes: A Survey. SIAM, Philadelphia (1999)"},{"issue":"3","key":"607_CR5","doi-asserted-by":"publisher","first-page":"666","DOI":"10.1016\/j.ejc.2012.07.023","volume":"34","author":"BM Bui-Xuan","year":"2013","unstructured":"Bui-Xuan, B.M., Such\u1ef3, O., Telle, J.A., Vatshelle, M.: Feedback vertex set on graphs of low clique-width. Eur. J. Comb. 34(3), 666\u2013679 (2013)","journal-title":"Eur. J. Comb."},{"issue":"7","key":"607_CR6","doi-asserted-by":"publisher","first-page":"1188","DOI":"10.1016\/j.jcss.2008.05.002","volume":"74","author":"J Chen","year":"2008","unstructured":"Chen, J., Fomin, F.V., Liu, Y., Lu, S., Villanger, Y.: Improved algorithms for feedback vertex set problems. J. Comput. Syst. Sci. 74(7), 1188\u20131198 (2008)","journal-title":"J. Comput. Syst. Sci."},{"key":"607_CR7","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, \u0141., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Berlin (2015)"},{"key":"607_CR8","doi-asserted-by":"crossref","unstructured":"Dehne, F.K.H.A., Fellows, M.R., Langston, M.A., Rosamond, F.A., Stevens, K.: An $$\\cal{O}(2^{O(k)}n^3)$$ fpt algorithm for the undirected feedback vertex set problem. In: Proceedings of the 11th COCOON. LNCS, vol. 3595, pp. 859\u2013869. Springer (2005)","DOI":"10.1007\/11533719_87"},{"issue":"4","key":"607_CR9","doi-asserted-by":"publisher","first-page":"873","DOI":"10.1137\/S0097539792228228","volume":"24","author":"RG Downey","year":"1995","unstructured":"Downey, R.G., Fellows, M.R.: Fixed-parameter tractability and completeness I: basic results. SIAM J. Comput. 24(4), 873\u2013921 (1995)","journal-title":"SIAM J. Comput."},{"key":"607_CR10","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"RG Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Berlin (1999)"},{"key":"607_CR11","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, Berlin (2013)"},{"issue":"4","key":"607_CR12","doi-asserted-by":"publisher","first-page":"1231","DOI":"10.1137\/S0097539798340047","volume":"30","author":"G Even","year":"2000","unstructured":"Even, G., Naor, J., Zosin, L.: An 8-approximation algorithm for the subset feedback vertex set problem. SIAM J. Comput. 30(4), 1231\u20131252 (2000)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"607_CR13","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/j.tcs.2008.09.065","volume":"410","author":"MR Fellows","year":"2009","unstructured":"Fellows, M.R., Hermelin, D., Rosamond, F.A., Vialette, S.: On the parameterized complexity of multiple-interval graph problems. Theor. Comput. Sci. 410(1), 53\u201361 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"607_CR14","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1007\/978-1-4757-3023-4_4","volume-title":"Handbook of Combinatorial Optimization","author":"P Festa","year":"1999","unstructured":"Festa, P., Pardalos, P.M., Resende, M.G.C.: Feedback set problems. In: Du, D.-Z., Pardalos, P.M. (eds.) Handbook of Combinatorial Optimization, pp. 209\u2013258. Springer, New York (1999)"},{"key":"607_CR15","unstructured":"Flotow, C.: Potenzen von Graphen. Ph.D. thesis, Universit\u00e4t Hamburg (1995)"},{"key":"607_CR16","unstructured":"Fomin, F.V., Golovach, P.A., Raymond, J.F.: On the tractability of optimization problems on H-graphs. In: Proceedings of the 26th ESA. LIPIcs, vol. 112, pp. 30:1\u201330:14. Schloss Dagstuhl. ArXiv:1709.09737 (2018)"},{"issue":"03","key":"607_CR17","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1142\/S0129054100000260","volume":"11","author":"MC Golumbic","year":"2000","unstructured":"Golumbic, M.C., Rotics, U.: On the clique-width of some perfect graph classes. Int. J. Found. Comput. Sci. 11(03), 423\u2013443 (2000)","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"8","key":"607_CR18","doi-asserted-by":"publisher","first-page":"1386","DOI":"10.1016\/j.jcss.2006.02.001","volume":"72","author":"J Guo","year":"2006","unstructured":"Guo, J., Gramm, J., H\u00fcffner, F., Niedermeier, R., Wernicke, S.: Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization. J. Comput. Syst. Sci. 72(8), 1386\u20131396 (2006)","journal-title":"J. Comput. Syst. Sci."},{"key":"607_CR19","unstructured":"Jaffke, L., Kwon, O., Str\u00f8mme, T.J.F., Telle, J.A.: Generalized distance domination problems and their complexity on graphs of bounded mim-width. In: Proceedings of the 13th IPEC. LIPIcs, vol. 115, pp. 6:1\u20136:14 (2018)"},{"key":"607_CR20","unstructured":"Jaffke, L., Kwon, O., Telle, J.A.: A note on the complexity of feedback vertex set parameterized by mim-width. ArXiv:1711.05157 (2017)"},{"key":"607_CR21","unstructured":"Jaffke, L., Kwon, O., Telle, J.A.: Polynomial-time algorithms for the longest induced path and induced disjoint paths problems on graphs of bounded mim-width. In: Proceedings of the 12th IPEC. LIPIcs, vol.\u00a089, pp. 21:1\u201321:13. Schloss Dagstuhl (2017)"},{"key":"607_CR22","doi-asserted-by":"crossref","unstructured":"Jaffke, L., Kwon, O., Telle, J.A.: Mim-width I. Induced path problems (2019). To appear in Discrete Applied Mathematics","DOI":"10.1016\/j.dam.2019.06.026"},{"key":"607_CR23","unstructured":"Jaffke, L., Kwon, O., Telle, J.A.: A unified polynomial-time algorithm for feedback vertex set on graphs of bounded mim-width. In: Proceedings of the 35th STACS. LIPIcs, vol.\u00a096, pp. 42:1\u201342:14. Schloss Dagstuhl (2018)"},{"issue":"4","key":"607_CR24","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1109\/TST.2014.6867520","volume":"19","author":"BMP Jansen","year":"2014","unstructured":"Jansen, B.M.P., Raman, V., Vatshelle, M.: Parameter ecology for feedback vertex set. Tsinghua Sci. Technol. 19(4), 387\u2013409 (2014)","journal-title":"Tsinghua Sci. Technol."},{"key":"607_CR25","doi-asserted-by":"crossref","unstructured":"Kanj, I., Pelsmajer, M., Schaefer, M.: Parameterized algorithms for feedback vertex set. In: Proceedings of the 1st IWPEC. LNCS, vol. 3162, pp. 235\u2013247. Springer (2004)","DOI":"10.1007\/978-3-540-28639-4_21"},{"key":"607_CR26","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"RM Karp","year":"1972","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W., Bohlinger, J.D. (eds.) Complexity of Computer Computations, pp. 85\u2013103. Springer, Boston (1972)"},{"issue":"10","key":"607_CR27","doi-asserted-by":"publisher","first-page":"1936","DOI":"10.1016\/j.dam.2007.10.006","volume":"156","author":"D Kratsch","year":"2008","unstructured":"Kratsch, D., M\u00fcller, H., Todinca, I.: Feedback vertex set on AT-free graphs. Discrete Appl. Math. 156(10), 1936\u20131947 (2008)","journal-title":"Discrete Appl. Math."},{"key":"607_CR28","doi-asserted-by":"crossref","unstructured":"Papadopoulos, C., Tzimas, S.: Polynomial-time algorithms for the subset feedback vertex set problem on interval graphs and permutation graphs. In: Proceedings of the 21st FCT. LNCS, vol. 10472, pp. 381\u2013394. Springer (2017)","DOI":"10.1007\/978-3-662-55751-8_30"},{"key":"607_CR29","unstructured":"Papadopoulos, C., Tzimas, S.: Subset feedback vertex set on graphs of bounded independent set size. In: Proceedings of the 13th IPEC. LIPIcs, vol. 115, pp. 20:1\u201320:14 (2018)"},{"issue":"4","key":"607_CR30","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. Comput. Syst. Sci. 67(4), 757\u2013771 (2003)","journal-title":"J. Comput. Syst. Sci."},{"key":"607_CR31","doi-asserted-by":"crossref","unstructured":"Raman, V., Saurabh, S., Subramanian, C.R.: Faster fixed parameter tractable algorithms for undirected feedback vertex set. In: Proceedings of the 13th ISAAC. LNCS, vol. 2518, pp. 241\u2013248. Springer (2002)","DOI":"10.1007\/3-540-36136-7_22"},{"issue":"3","key":"607_CR32","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1145\/1159892.1159898","volume":"2","author":"V Raman","year":"2006","unstructured":"Raman, V., Saurabh, S., Subramanian, C.R.: Faster fixed parameter tractable algorithms for finding feedback vertex sets. ACM Trans. Algorithms 2(3), 403\u2013415 (2006)","journal-title":"ACM Trans. Algorithms"},{"key":"607_CR33","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/j.dam.2017.09.016","volume":"248","author":"L Stewart","year":"2018","unstructured":"Stewart, L., Valenzano, R.: On polygon numbers of circle graphs and distance hereditary graphs. Discrete Appl. Math. 248, 3\u201317 (2018)","journal-title":"Discrete Appl. Math."},{"key":"607_CR34","unstructured":"Vatshelle, M.: New width parameters of graphs. Ph.D. thesis, University of Bergen (2012)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00607-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-019-00607-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00607-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,24]],"date-time":"2022-09-24T03:46:10Z","timestamp":1663991170000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-019-00607-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,7,18]]},"references-count":34,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,1]]}},"alternative-id":["607"],"URL":"https:\/\/doi.org\/10.1007\/s00453-019-00607-3","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,7,18]]},"assertion":[{"value":"24 September 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 July 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 July 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}