Show simple item record

dc.contributor.authorKanté, Mamadou Moustapha
dc.contributor.authorKim, Eun Jung
dc.contributor.authorKwon, O-joung
dc.contributor.authorPaul, Christophe
dc.date.accessioned2020-05-27T13:05:48Z
dc.date.available2020-05-27T13:05:48Z
dc.date.issued2017
dc.identifier.issn0178-4617
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/20786
dc.language.isoenen
dc.subjectNecklace graphen
dc.subjectThread graphen
dc.subjectCliquewidthen
dc.subjectRankwidthen
dc.subjectLinear rankwidthen
dc.subject.ddc511en
dc.titleAn FPT Algorithm and a Polynomial Kernel for Linear Rankwidth-1 Vertex Deletionen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenLinear rankwidth is a linearized variant of rankwidth, introduced by Oum and Seymour (J Comb Theory Ser B 96(4):514–528, 2006). Motivated from recent development on graph modification problems regarding classes of graphs of bounded treewidth or pathwidth, we study the LINEAR RANKWIDTH-1 VERTEX DELETION problem (shortly, LRW1-VERTEX DELETION). In the LRW1-VERTEX DELETION problem, given an n-vertex graph G and a positive integer k, we want to decide whether there is a set of at most k vertices whose removal turns G into a graph of linear rankwidth at most 1 and find such a vertex set if one exists. While the meta-theorem of Courcelle, Makowsky, and Rotics implies that LRW1-VERTEX DELETION can be solved in time f(k)⋅n3 for some function f, it is not clear whether this problem allows a running time with a modest exponential function. We first establish that LRW1-VERTEX DELETION can be solved in time 8k⋅nO(1). The major obstacle to this end is how to handle a long induced cycle as an obstruction. To fix this issue, we define necklace graphs and investigate their structural properties. Later, we reduce the polynomial factor by refining the trivial branching step based on a cliquewidth expression of a graph, and obtain an algorithm that runs in time 2O(k)⋅n4. We also prove that the running time cannot be improved to 2o(k)⋅nO(1) under the Exponential Time Hypothesis assumption. Lastly, we show that the LRW1-VERTEX DELETION problem admits a polynomial kernel.en
dc.relation.isversionofjnlnameAlgorithmica
dc.relation.isversionofjnlvol79en
dc.relation.isversionofjnlissue1en
dc.relation.isversionofjnldate2017-09
dc.relation.isversionofjnlpages66–95en
dc.relation.isversionofdoi10.1007/s00453-016-0230-zen
dc.identifier.urlsitehttps://hal-lirmm.ccsd.cnrs.fr/lirmm-01692676en
dc.relation.isversionofjnlpublisherSpringeren
dc.subject.ddclabelPrincipes généraux des mathématiquesen
dc.relation.forthcomingnonen
dc.relation.forthcomingprintnonen
dc.description.ssrncandidatenonen
dc.description.halcandidatenonen
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewedouien
dc.relation.Isversionofjnlpeerreviewedouien
dc.date.updated2020-05-27T12:57:46Z
hal.person.labIds
hal.person.labIds989
hal.person.labIds
hal.person.labIds


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record