Structural Parameters, Tight Bounds, and Parameterized Approximation
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