Structural Parameters, Tight Bounds, and Parameterized Approximation

Read full text Summarise with VIRAT
Authors: Emmanouil Vasilakis
Cited by: 0
References: 271

Summary

No summary yet. VIRAT can read this paper and write a plain-language summary of its aim, methods, key findings and limitations.

Summarise with VIRAT Free to try with your Science Catalogs account.

Abstract

Paramètres structurels, bornes serrées et approximation paramétrée Cette thèse étudie des problèmes sur les graphes NP-difficiles au travers de la paramétrisation structurelle et d'une analyse fine. Pour les problèmes considérés, nous (i) localisons la frontière entre la tractabilité à paramètres fixes (FPT) et la W[1]-dureté, en proposant des réductions d'intractabilité améliorées et en concevant de nouveaux algorithmes FPT ; (ii) faisons correspondre des algorithmes naturels de programmation dynamique à des bornes inférieures serrées fondées sur SETHou pw-SETH ; (iii) établissons des bornes inférieures serrées sous ETH pour des paramétrisations au-delà de la largeur d'arbre ; et (iv) montrons que l'approximation permet, dans certains cas, de franchir des barrières du calcul exact, tandis que dans d'autres elle ne le peut pas. Pour atteindre ces résultats, nous développons de nouvelles techniques de réductions de dureté et de conception d'algorithmes, susceptibles d'intérêt indépendant. En particulier, nous introduisons (i) une nouvelle variante de textsc {Unary Bin Packing} qui conduit à des résultats de W[1]-dureté renforcés ; (ii) des techniques pour obtenir des bornes inférieures améliorées pour des problèmes paramétrés par la profondeur d'arbre et la couverture de sommets ; et (iii) une construction simple pour concevoir des schémas d'approximation FPT. Nous mettons à profit ces techniques pour obtenir un ensemble de nouveaux résultats sur plusieurs problèmes sur les graphes NP-difficiles bien étudiés.

Fields of Study & Subjects

Advanced Graph Theory Research Complexity and Algorithms in Graphs Limits and Structures in Graph Theory

Publication details

Publication date
1 February 2026
Language
EL
Document type
Thesis