Sparse instances of hard problems [Elektronische Ressource] / Holger Dell. Gutachter: Martin Grohe ; Johannes Köbler ; Dieter van Melkebeek

Sparse Instances of Hard ProblemsD I SS E R TAT I O Nzur Erlangung des akademischen Gradesdoctor rerum naturaliumim Fach Informatikeingereicht an derMathematisch–Naturwissenschaftlichen Fakultät IIHumboldt–Universität zu BerlinvonM.Sc. Holger DellGefördert durch die Deutsche Forschungsgemeinschaft im Rahmen des Graduiertenkollegs’Methods for Discrete Structures’ (GRK 1408)Präsident der Humboldt–Universität zu Berlin:Prof. Dr. Jan-Hendrik OlbertzDekan der Mathematisch–Naturwissenschaftlichen Fakultät II:Prof. Dr. Elmar KulkeGutachter:1. Prof. Dr. Martin Grohe2. Prof. Dr. Johannes Köbler3. Prof. Dr. Dieter van MelkebeekTag der mündlichen Prüfung: 15. Juli 2011AbstractIn this thesis, we use and refine methods of computational complexity theory toanalyzethecomplexityofsparseinstances, suchasgraphswithfewedgesorformulaswith few constraints of bounded width. Two natural questions arise in this context:• Is there an efficient algorithm that reduces arbitrary instances of an NP-hardproblem to equivalent, sparse instances?• Is there an algorithm that solves sparse instances of an NP-hard problemsignificantly faster than general instances can be solved?We formalize these questions for different problems and show that positive answersfor these formalizations would lead to consequences in complexity theory that areconsidered unlikely.