Unit:
Department of MathematicsLibrary of the School of Science
Author:
Maniatis Spyridon
Dissertation committee:
Χρήστος Α. Αθανασιάδης, Καθηγητής, Τμήμα Μαθηματικών, Εθνικόν και Καποδιστριακόν Πανεπιστήμιον Αθηνών
Μιχάλης Δρακόπουλος, Επίκουρος Καθηγητής, Τμήμα Μαθηματικών, Εθνικόν και Καποδιστριακόν Πανεπιστήμιον Αθηνών
Λευτέρης Κυρούσης, Καθηγητής, Τμήμα Μαθηματικών, Εθνικόν και Καποδιστριακόν Πανεπιστήμιον Αθηνών
Σταύρος Κολλιόπουλος, Καθηγητής, Τμήμα Πληροφορικής και Τηλεπικοινωνιών, Εθνικόν και Καποδιστριακόν Πανεπιστήμιον Αθηνών
Ιωάννης Μούρτος, Αναπληρωτής Καθηγητής, Τμήμα Διοικητικής Επιστήμης και Τεχνολογίας, Οικονομικό Πανεπιστήμιο Αθηνών
Ευάγγελος Ράπτης, Καθηγητής, Τμήμα Μαθηματικών, Εθνικόν και Καποδιστριακόν Πανεπιστήμιον Αθηνών
Δημήτριος Μ. Θηλυκός, Καθηγητής, Τμήμα Μαθηματικών, Εθνικόν και Καποδιστριακόν Πανεπιστήμιον Αθηνών
Original Title:
Cyclability: Combinatorial Properties, Algorithms and Complexity
Translated title:
Cyclability: Combinatorial Properties, Algorithms and Complexity
Summary:
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.
Main subject category:
Science
Keywords:
cyclability, parameterized, complexity, kernel, treewidth
