Back to search

National and Kapodistrian University of Athens

Cyclability: combinatorial properties, algorithms and complexity

Abstract

dc:description

A graph G is called k-cyclable, if for every k of its vertices there exists a cycle in G that contains them. The cyclability of G is the maximum integer k for which G is k-cyclable and it is a connectivity related graph parameter. In this doctoral thesis we study, mainly from the Parameterized Complexity point of view, the Cyclability problem: Given a graph G = (V,E) and an integer k (the parameter), decide whether the cyclability of G is equal to k. Our first result is a negative one and shows that the existence of an FPT-algorithm for solving Cyclability is unlikely (unless FPT = co-W[1], which is considered unlikely). More specifically, we prove that Cyclability is co-W[1]-hard, even if we restrict the input to be a split graph. On the other hand, we give an FPT-algorithm for the same problem when restricted to the class of planar graphs. To do this, we prove a series of combinatorial results regarding cyclability and apply a two-step version of the so called irrelevant vertex technique, which was introduced by Robertson and Seymour in their Graph Minors series (Irrelevant vertices in linkage problems) as a crucial ingredient for their algorithm solving the Disjoint Paths problem. To prove the correctness of our algorithm, we introduce notions, like the one of vital cyclic linkages, and give results of independent graph-theoretic interest.We conclude our study with a negative result: We prove that Cyclability admits no polynomial kernel, even when restricted to cubic planar graphs, unless a classical complexity theoretic assumption (that NP is a subset of co-NP/poly) fails.

Degree

thesis:*
Grantor dc:publisher
National and Kapodistrian University of Athens
Year dc:date
2018

Author and committee

dc:creator, dc:contributor.*
Authors dc:creator
  • Maniatis, Spyridon
  • Μανιάτης, Σπυρίδων

Subjects

dc:subject × 12

Rights

Language dc:language
eng

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/43502

Chain of custody

source
Harvested from
Greek National Archive of PhD Theses
Base URL
phdtheses.ekt.gr/eadd_oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Maniatis, Spyridon; Μανιάτης, Σπυρίδων. Cyclability: combinatorial properties, algorithms and complexity. National and Kapodistrian University of Athens, 2018. http://hdl.handle.net/10442/hedi/43502