Institutes outside Greece
Structural parameters, tight bounds, and parameterized approximation
Abstract
dc:descriptionThis thesis studies NP-hard graph problems through structural parameterization andfine-grained analysis. For our problems of study we (i) locate the boundary betweenfixed-parameter tractability and W[1]-hardness, by giving improved hardness reductionsand designing new FPT algorithms; (ii) match natural DP algorithms with tight SETHor pw-SETH-lower bounds; (iii) obtain tight ETH-lower bounds for parameterizationsbeyond treewidth; and (iv) show that adding approximation into the mix can in somecases overcome exact barriers, yet in some other cases it cannot. On our way to theseresults we develop new techniques for both hardness reductions and algorithm designthat may be of independent interest. In particular, we introduce (i) a new variant ofUnary Bin Packing that allows for improved W[1]-hardness results; (ii) techniques forobtaining improved lower bounds for problems parameterized by tree-depth and vertexcover; and (iii) a simple construction for designing FPT approximation schemes. Weleverage these techniques to obtain a number of new results for several well-studiedNP-hard graph problems.
Degree
thesis:*- Grantor dc:publisher
- Institutes outside Greece
- Year dc:date
- 2026
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Vasilakis, Emmanouil
- Βασιλάκης, Εμμανουήλ
Subjects
dc:subject × 18- Παραμετρική πολυπλοκότητα
- Λεπτομερής πολυπλοκότητα
- Προσεγγιστικοί αλγόριθμοι
- Δενδροπλάτος
- Parameterized complexity
- Fine-grained complexity
- Approximation algorithms
- Treewidth
- Complexité paramétrée
- Complexité fine
- Algorithmes d’approximation
- Largeur d’arbre
- Επιστήμη Ηλεκτρονικών Υπολογιστών και Πληροφορική
- Φυσικές Επιστήμες
- Επιστήμη ηλεκτρονικών υπολογιστών, θεωρία και μέθοδοι
- Computer and Information Sciences
- Natural Sciences
- Computer science, theory and methods
Rights
- Language dc:language
- eng
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/62460