• français
    • English
  • English 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

Parameterized Edge Hamiltonicity

Thumbnail
Date
2018
Dewey
Principes généraux des mathématiques
Sujet
Edge Hamiltonicity; Fixed parameter tractability; Structural parameterization; Polynomial kernel
Journal issue
Discrete Applied Mathematics
Volume
248
Publication date
10-2018
Article pages
68-78
Publisher
Elsevier
DOI
http://dx.doi.org/10.1016/j.dam.2017.04.045
URI
https://basepub.dauphine.fr/handle/123456789/19039
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Lampis, Michael
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Makino, Kazuhisa
130623 Research Institute for Mathematical Sciences [RIMS]
Mitsou, Valia
2003 Laboratoire d'InfoRmatique en Image et Systèmes d'information [LIRIS]
Uno, Yushi
21444 Osaka Prefecture University
Type
Article accepté pour publication ou publié
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.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.