A single-exponential FPT algorithm for the K4-minor cover problem
Philip, Geevarghese; Paul, Christophe; Kim, Eun Jung (2015), A single-exponential FPT algorithm for the K4-minor cover problem, Journal of Computer and System Sciences, 81, 1, p. 186-207. 10.1016/j.jcss.2014.05.001
TypeArticle accepté pour publication ou publié
External document linkhttp://arxiv.org/abs/1204.1417v1
Journal nameJournal of Computer and System Sciences
MetadataShow full item record
Kim, Eun Jung
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)Given an input graph G and an integer k, the parameterized K4 -minor cover problem asks whether there is a set S of at most k vertices whose deletion results in a K4 -minor-free graph, or equivalently in a graph of treewidth at most 2. This problem is inspired by two well-studied parameterized vertex deletion problems, Vertex Cover and Feedback Vertex Set , which can also be expressed as Treewidth- t Vertex Deletion problems: t = 0 for Vertex Cover and t = 1 for Feedback Vertex Set . While a single-exponential FPT algorithm has been known for a long time for Vertex Cover , such an algorithm for Feedback Vertex Set was devised comparatively recently. While it is known to be unlikely that Treewidth- t Vertex Deletion can be solved in time co ( k ) nO (1) , it was open whether the K4 -minor cover could be solved in single-exponential FPT time, i.e. in ck nO (1) time. This paper answers this question in the a rmative.
Subjects / KeywordsVertex Cover; FPT time
Showing items related by title and author.
Kim, Eun Jung; Langer, Alexander; Paul, Christophe; Reidl, Felix; Rossmanith, Peter; Sau Valls, Ignasi; Sikdar, Somnath (2013-07) Communication / Conférence
Kim, Eun Jung; Langer, Alexander; Paul, Christophe; Reidl, Felix; Rossmanith, Peter; Sau Valls, Ignasi (2016) Article accepté pour publication ou publié
Kanté, Mamadou Moustapha; Kim, Eun Jung; Kwon, O-joung; Paul, Christophe (2017) Article accepté pour publication ou publié