• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Aide
  • Connexion
  • Langue 
    • Français
    • English
Consulter le document 
  •   Accueil
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • Consulter le document
  •   Accueil
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • Consulter le document
JavaScript is disabled for your browser. Some features of this site may not work without it.

Afficher

Toute la baseCentres de recherche & CollectionsAnnée de publicationAuteurTitreTypeCette collectionAnnée de publicationAuteurTitreType

Mon compte

Connexion

Enregistrement

Statistiques

Documents les plus consultésStatistiques par paysAuteurs les plus consultés
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é
Lien vers un document non conservé dans cette base
https://hal-lirmm.ccsd.cnrs.fr/lirmm-01692676
Date
2017
Nom de la revue
Algorithmica
Volume
79
Numéro
1
Éditeur
Springer
Pages
66–95
Identifiant publication
10.1007/s00453-016-0230-z
Métadonnées
Afficher la notice complète
Auteur(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
Résumé (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.
Mots-clés
Necklace graph; Thread graph; Cliquewidth; Rankwidth; Linear rankwidth

Publications associées

Affichage des éléments liés par titre et auteur.

  • Vignette de prévisualisation
    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
  • Vignette de prévisualisation
    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é
  • Vignette de prévisualisation
    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
  • Vignette de prévisualisation
    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é
  • Vignette de prévisualisation
    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
Tél. : 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo