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
2018Journal name
Discrete Applied MathematicsVolume
248Publisher
Elsevier
Pages
68-78
Publication identifier
Metadata
Show full item recordAuthor(s)
Lampis, Michael
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 kernelRelated items
Showing items related by title and author.
-
Gajarsky, Jakub; Lampis, Michael; Makino, Kazuhisa; Mitsou, Valia; Ordyniak, Sebastian (2015) Communication / Conférence
-
Dell, Holger; Kim, Eun Jung; Lampis, Michael; Mitsou, Valia; Mömke, Tobias (2017) Article accepté pour publication ou publié
-
Dell, Holger; Kim, Eun Jung; Lampis, Michael; Mitsou, Valia; Mömke, Tobias (2015) Communication / Conférence
-
Belmonte, Rémy; Lampis, Michael; Mitsou, Valia (2020) Article accepté pour publication ou publié
-
Lampis, Michael; Mengel, Stefan; Mitsou, Valia (2018) Communication / Conférence