dc.contributor.author Crespelle, Christophe Dominique dc.contributor.author Feghali, Carl dc.contributor.author Golovach, Petr dc.date.accessioned 2020-08-14T11:04:38Z dc.date.available 2020-08-14T11:04:38Z dc.date.issued 2019 dc.Published Crespelle CD, Feghali C, Golovach P. Cyclability in Graph Classes. Leibniz International Proceedings in Informatics. 2019;149:16:1-16:13 eng dc.identifier.issn 1868-8969 en_US dc.identifier.uri https://hdl.handle.net/1956/23763 dc.description.abstract A subset T subseteq V(G) of vertices of a graph G is said to be cyclable if G has a cycle C containing every vertex of T, and for a positive integer k, a graph G is k-cyclable if every subset of vertices of G of size at most k is cyclable. The Terminal Cyclability problem asks, given a graph G and a set T of vertices, whether T is cyclable, and the k-Cyclability problem asks, given a graph G and a positive integer k, whether G is k-cyclable. These problems are generalizations of the classical Hamiltonian Cycle problem. We initiate the study of these problems for graph classes that admit polynomial algorithms for Hamiltonian Cycle. We show that Terminal Cyclability can be solved in linear time for interval graphs, bipartite permutation graphs and cographs. Moreover, we construct certifying algorithms that either produce a solution, that is, a cycle, or output a graph separator that certifies a no-answer. We use these results to show that k-Cyclability can be solved in polynomial time when restricted to the aforementioned graph classes. en_US dc.language.iso eng eng dc.publisher Dagstuhl Publishing en_US dc.rights Attribution CC BY eng dc.rights.uri http://creativecommons.org/licenses/by/3.0 eng dc.title Cyclability in Graph Classes en_US dc.type Peer reviewed dc.type Journal article dc.date.updated 2020-01-17T14:44:05Z dc.description.version publishedVersion en_US dc.rights.holder Copyright 2019 The Author(s) en_US dc.identifier.doi https://doi.org/10.4230/lipics.isaac.2019.16 dc.identifier.cristin 1774909 dc.source.journal Leibniz International Proceedings in Informatics dc.relation.project Norges forskningsråd: 249994 dc.relation.project Norges forskningsråd: 263317
﻿

### This item appears in the following Collection(s)

Except where otherwise noted, this item's license is described as Attribution CC BY