License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2019.16
URN: urn:nbn:de:0030-drops-115128
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11512/
Go to the corresponding LIPIcs Volume Portal

Crespelle, Christophe ; Feghali, Carl ; Golovach, Petr A.

Cyclability in Graph Classes

pdf-format:
LIPIcs-ISAAC-2019-16.pdf (0.6 MB)

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.

BibTeX - Entry

@InProceedings{crespelle_et_al:LIPIcs:2019:11512,
  author =	{Christophe Crespelle and Carl Feghali and Petr A. Golovach},
  title =	{{Cyclability in Graph Classes}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{16:1--16:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-130-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{149},
  editor =	{Pinyan Lu and Guochuan Zhang},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2019/11512},
  URN =		{urn:nbn:de:0030-drops-115128},
  doi =		{10.4230/LIPIcs.ISAAC.2019.16},
  annote =	{Keywords: Cyclability, interval graphs, bipartite permutation graphs, cographs}
}

Keywords: Cyclability, interval graphs, bipartite permutation graphs, cographs
Collection: 30th International Symposium on Algorithms and Computation (ISAAC 2019)
Issue Date: 2019
Date of publication: 28.11.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI