Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | 권오정 | - |
dc.date.accessioned | 2022-11-24T01:08:32Z | - |
dc.date.available | 2022-11-24T01:08:32Z | - |
dc.date.issued | 2019-10 | - |
dc.identifier.citation | ALGORITHMICA, v. 81, no. 10, page. 3890-3935 | en_US |
dc.identifier.issn | 0178-4617; 1432-0541 | en_US |
dc.identifier.uri | https://link.springer.com/article/10.1007/s00453-019-00579-4 | en_US |
dc.identifier.uri | https://repository.hanyang.ac.kr/handle/20.500.11754/177328 | - |
dc.description.abstract | It has long been known that Feedback Vertex Set can be solved in time 2 O-(w log w) n(O(1)) on n-vertex graphs of treewidth w, but it was only recently that this running time was improved to 2(O(w))n(O(1)), that is, to single-exponential parameterized by treewidth. We investigate which generalizations of Feedback Vertex Set can be solved in a similar running time. Formally, for a class P of graphs, the Bounded P-Block Vertex Deletion problem asks, given a graph G on n vertices and positive integers k and d, whether G contains a set S of at most k vertices such that each block of G -S has at most d vertices and is in P. Assuming that P is recognizable in polynomial time and satisfies a certain natural hereditary condition, we give a sharp characterization of when single-exponential parameterized algorithms are possible for fixed values of d: - if P consists only of chordal graphs, then the problem can be solved in time 2(O(wd2))n(O(1)), - if P contains a graph with an induced cycle of length l >= 4, then the problem is not solvable in time 2(o(w log w))n(O(1)) even for fixed d = l, unless the ETH fails. We also study a similar problem, called Bounded P-Component Vertex Deletion, where the target graphs have connected components of small size rather than blocks of small size, and we present analogous results. For this problem, we also show that if d is part of the input and P contains all chordal graphs, then it cannot be solved in time f(w)n(o(w)) for some function f, unless the ETH fails. | en_US |
dc.description.sponsorship | All authors were supported by ERC Starting Grant PARAMTIGHT (No. 280152). O-joung Kwon was supported by the National Research Foundation of Korea (NRF) Grant funded by the Ministry of Education (No. NRF-2018R1D1A1B07050294). Daniel Marx was supported by ERC Consolidator Grant SYSTEMATICGRAPH (No. 725978). | en_US |
dc.language | en | en_US |
dc.publisher | SPRINGER | en_US |
dc.subject | Parameterized complexity; Feedback Vertex Set; Treewidth; Chordal graph | en_US |
dc.title | Generalized feedback vertex set problems on bounded-treewidth graphs: chordality is the key to single-exponential parameterized algorithms | en_US |
dc.type | Article | en_US |
dc.identifier.doi | 10.1007/s00453-019-00579-4 | en_US |
dc.relation.journal | ALGORITHMICA | - |
dc.contributor.googleauthor | Bonnet, Edouard | - |
dc.contributor.googleauthor | Brettell, Nick | - |
dc.contributor.googleauthor | Kwon, O-joung | - |
dc.contributor.googleauthor | Marx, Daniel | - |
dc.relation.code | 2019002602 | - |
dc.sector.campus | S | - |
dc.sector.daehak | COLLEGE OF NATURAL SCIENCES[S] | - |
dc.sector.department | DEPARTMENT OF MATHEMATICS | - |
dc.identifier.pid | ojoungkwon | - |
dc.identifier.orcid | https://orcid.org/0000-0003-1820-1962 | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.