This book constitutes the refereed proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science, STACS 2005, held in Stuttgart, Germany in February 2005. The 54 revised full papers presented together with 3 invited papers were carefully reviewed and selected from 217 submissions. A broad variety of topics from theoretical computer science are addressed, in particular complexity theory, algorithmics, computational discrete mathematics, automata theory, combinatorial optimization and approximation, networking and graph theory, computational geometry, grammar systems and formal languages, etc.