• 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 - Request a copy

Parameterized Edge Hamiltonicity

Lampis, Michael; Makino, Kazuhisa; Mitsou, Valia; Uno, Yushi (2018), Parameterized Edge Hamiltonicity, Discrete Applied Mathematics, 248, p. 68-78. 10.1016/j.dam.2017.04.045

Type
Article accepté pour publication ou publié
Date
2018
Journal name
Discrete Applied Mathematics
Volume
248
Publisher
Elsevier
Pages
68-78
Publication identifier
10.1016/j.dam.2017.04.045
Metadata
Show full item record
Author(s)
Lampis, Michael cc
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Makino, Kazuhisa
Research Institute for Mathematical Sciences [RIMS]
Mitsou, Valia
Laboratoire d'InfoRmatique en Image et Systèmes d'information [LIRIS]
Uno, Yushi
Abstract (EN)
We study the parameterized complexity of the classical Edge Hamiltonian Path problem and give several fixed-parameter tractability results. First, we settle an open question of Demaine et al. (2014) by showing that Edge Hamiltonian Path is FPT parameterized by vertex cover, and that it also admits a cubic kernel. We then show fixed-parameter tractability even for a generalization of the problem to arbitrary hypergraphs, parameterized by the size of a (supplied) hitting set. As an interesting consequence, we show that this implies an FPT algorithm for (Vertex) Hamiltonian Path parameterized by (vertex) clique cover. We also consider the problem parameterized by treewidth or clique-width. Surprisingly, we show that the problem is FPT for both of these standard parameters, in contrast to its vertex version, which is W[1]-hard for clique-width. Our technique, which may be of independent interest, relies on a structural characterization of clique-width in terms of treewidth and complete bipartite subgraphs due to Gurski and Wanke.
Subjects / Keywords
Edge Hamiltonicity; Fixed parameter tractability; Structural parameterization; Polynomial kernel

Related items

Showing items related by title and author.

  • Thumbnail
    Parameterized Algorithms for Parity Games 
    Gajarsky, Jakub; Lampis, Michael; Makino, Kazuhisa; Mitsou, Valia; Ordyniak, Sebastian (2015) Communication / Conférence
  • Thumbnail
    Complexity and Approximability of Parameterized MAX-CSPs 
    Dell, Holger; Kim, Eun Jung; Lampis, Michael; Mitsou, Valia; Mömke, Tobias (2017) Article accepté pour publication ou publié
  • Thumbnail
    Complexity and Approximability of Parameterized MAX-CSPs 
    Dell, Holger; Kim, Eun Jung; Lampis, Michael; Mitsou, Valia; Mömke, Tobias (2015) Communication / Conférence
  • Thumbnail
    Parameterized (Approximate) Defective Coloring 
    Belmonte, Rémy; Lampis, Michael; Mitsou, Valia (2020) Article accepté pour publication ou publié
  • Thumbnail
    QBF as an Alternative to Courcelle’s Theorem 
    Lampis, Michael; Mengel, Stefan; Mitsou, Valia (2018) Communication / Conférence
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