• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail - No thumbnail

An FPT Algorithm and a Polynomial Kernel for Linear Rankwidth-1 Vertex Deletion

Kanté, Mamadou Moustapha; Kim, Eun Jung; Kwon, O-joung; Paul, Christophe (2017), An FPT Algorithm and a Polynomial Kernel for Linear Rankwidth-1 Vertex Deletion, Algorithmica, 79, 1, p. 66–95. 10.1007/s00453-016-0230-z

Type
Article accepté pour publication ou publié
External document link
https://hal-lirmm.ccsd.cnrs.fr/lirmm-01692676
Date
2017
Journal name
Algorithmica
Volume
79
Number
1
Publisher
Springer
Pages
66–95
Publication identifier
10.1007/s00453-016-0230-z
Metadata
Show full item record
Author(s)
Kanté, Mamadou Moustapha cc

Kim, Eun Jung
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Kwon, O-joung

Paul, Christophe
Abstract (EN)
Linear 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.
Subjects / Keywords
Necklace graph; Thread graph; Cliquewidth; Rankwidth; Linear rankwidth

Related items

Showing items related by title and author.

  • Thumbnail
    An FPT Algorithm and a Polynomial Kernel for Linear Rankwidth-1 Vertex Deletion 
    Paul, Christophe; Kim, Eun Jung; Kanté, Mamadou Moustapha; Kwon, O-joung (2015) Communication / Conférence
  • Thumbnail
    Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions 
    Kim, Eun Jung; Langer, Alexander; Paul, Christophe; Reidl, Felix; Rossmanith, Peter; Sau Valls, Ignasi (2016) Article accepté pour publication ou publié
  • Thumbnail
    Linear Kernels and Single-Exponential Algorithms via Protrusion Decompositions 
    Kim, Eun Jung; Langer, Alexander; Paul, Christophe; Reidl, Felix; Rossmanith, Peter; Sau Valls, Ignasi; Sikdar, Somnath (2013-07) Communication / Conférence
  • Thumbnail
    A single-exponential FPT algorithm for the K4-minor cover problem 
    Philip, Geevarghese; Paul, Christophe; Kim, Eun Jung (2015) Article accepté pour publication ou publié
  • Thumbnail
    An FPT 2-Approximation for Tree-Cut Decomposition 
    Kim, Eun Jung; Oum, Sang-il; Paul, Christophe; Sau Valls, Ignasi; Thilikos, Dimitrios M. (2018) Article accepté pour publication ou publié
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo