Parameterized Edge Hamiltonicity

DOI DOI DOI Web Site Web Site View 1 Remaining Hide 37 References

Bibliographic Information

Published
2018-10
Resource Type
journal article
Rights Information
  • https://www.elsevier.com/tdm/userlicense/1.0/
  • https://www.elsevier.com/legal/tdmrep-license
  • http://www.elsevier.com/open-access/userlicense/1.0/
  • https://doi.org/10.15223/policy-017
  • https://doi.org/10.15223/policy-037
  • https://doi.org/10.15223/policy-012
  • https://doi.org/10.15223/policy-029
  • https://doi.org/10.15223/policy-004
DOI
  • 10.1016/j.dam.2017.04.045
  • 10.1007/978-3-319-12340-0_29
  • 10.48550/arxiv.1403.2041
Publisher
Elsevier BV

Search this article

Description

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. 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. 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-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.

Journal

References(37)*help

See more

Related Projects

See more

Keywords

Report a problem

Back to top