Show simple item record

Parameterized Edge Hamiltonicity

hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorLampis, Michael
HAL ID: 182546
ORCID: 0000-0002-5791-0887
hal.structure.identifierResearch Institute for Mathematical Sciences [RIMS]
dc.contributor.authorMakino, Kazuhisa
hal.structure.identifierLaboratoire d'InfoRmatique en Image et Systèmes d'information [LIRIS]
dc.contributor.authorMitsou, Valia
hal.structure.identifier
dc.contributor.authorUno, Yushi
dc.date.accessioned2019-06-26T09:45:36Z
dc.date.available2019-06-26T09:45:36Z
dc.date.issued2018
dc.identifier.issn0166-218X
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/19039
dc.language.isoenen
dc.subjectEdge Hamiltonicityen
dc.subjectFixed parameter tractabilityen
dc.subjectStructural parameterizationen
dc.subjectPolynomial kernelen
dc.subject.ddc511en
dc.titleParameterized Edge Hamiltonicityen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenWe 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.en
dc.relation.isversionofjnlnameDiscrete Applied Mathematics
dc.relation.isversionofjnlvol248en
dc.relation.isversionofjnldate2018-10
dc.relation.isversionofjnlpages68-78en
dc.relation.isversionofdoi10.1016/j.dam.2017.04.045en
dc.relation.isversionofjnlpublisherElsevieren
dc.subject.ddclabelPrincipes généraux des mathématiquesen
dc.relation.forthcomingnonen
dc.relation.forthcomingprintnonen
dc.description.ssrncandidatenonen
dc.description.halcandidateouien
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewedouien
dc.relation.Isversionofjnlpeerreviewedouien
dc.date.updated2019-03-31T15:01:38Z
hal.identifierhal-02165855*
hal.version1*
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record