dc.contributor.author | Jaffke, Lars | |
dc.contributor.author | Kwon, O-Joung | |
dc.contributor.author | Telle, Jan Arne | |
dc.date.accessioned | 2020-05-25T10:58:33Z | |
dc.date.available | 2020-05-25T10:58:33Z | |
dc.date.issued | 2020 | |
dc.Published | Jaffke, Kwon, Telle. Mim-Width II. The Feedback Vertex Set Problem. Algorithmica. 2020;82:118-145 | eng |
dc.identifier.issn | 0178-4617 | en_US |
dc.identifier.issn | 1432-0541 | en_US |
dc.identifier.uri | https://hdl.handle.net/1956/22364 | |
dc.description.abstract | We give a first polynomial-time algorithm for (WEIGHTED) FEEDBACK VERTEX SET on graphs of bounded maximum induced matching width (mim-width). Explicitly, given a branch decomposition of mim-width w, we give an nO(w)-time algorithm that solves FEEDBACK VERTEX SET. This provides a unified polynomial-time algorithm for many well-known classes, such as INTERVAL graphs, PERMUTATION graphs, and LEAF POWER graphs (given a leaf root), and furthermore, it gives the first polynomial-time algorithms for other classes of bounded mim-width, such as CIRCULAR PERMUTATION and CIRCULAR k-TRAPEZOID graphs (given a circular k-trapezoid model) for fixed k. We complement our result by showing that FEEDBACK VERTEX SET is W[1]-hard when parameterized by w and the hardness holds even when a linear branch decomposition of mim-width w is given. | en_US |
dc.language.iso | eng | eng |
dc.publisher | Springer | en_US |
dc.title | Mim-Width II. The Feedback Vertex Set Problem | en_US |
dc.type | Peer reviewed | |
dc.type | Journal article | |
dc.date.updated | 2020-02-19T10:44:39Z | |
dc.description.version | acceptedVersion | en_US |
dc.rights.holder | Copyright 2019 Springer | en_US |
dc.identifier.doi | https://doi.org/10.1007/s00453-019-00607-3 | |
dc.identifier.cristin | 1795778 | |
dc.source.journal | Algorithmica | |
dc.source.pagenumber | 118-145 | |
dc.identifier.citation | Algorithmica. 2020;82:118-145 | |
dc.source.volume | 82 | |