National and Kapodistrian University of Athens
Cyclability: combinatorial properties, algorithms and complexity
Abstract
dc:descriptionA 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 × 12Rights
- Language dc:language
- eng
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/43502