Back to search

Institutes outside Greece

Structural parameters, tight bounds, and parameterized approximation

Abstract

dc:description

This 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

Rights

Language dc:language
eng

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/62460

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

Vasilakis, Emmanouil; Βασιλάκης, Εμμανουήλ. Structural parameters, tight bounds, and parameterized approximation. Institutes outside Greece, 2026. http://hdl.handle.net/10442/hedi/62460