Cyclability in Graph Classes
Báo cáo viên: Christophe Crespelle

Thời gian: 9h30, Thứ 5, ngày 12 tháng 12 năm 2019
Địa điểm: Phòng 611-612, Nhà A6, Viện Toán học

Tóm tắt: A subset T 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 set of vertices 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.