This volume contains the papers presented at ICALP 2018, the 45th edition of the International Colloquium on Automata, Languages and Programming, held in Prague, Czech Republic during July 9–13, 2018. ICALP is a series of annual conferences of the European Association for Theoretical Computer Science (EATCS), which first took place in 1972. This year, the ICALP program consisted of three tracks: Track A: Algorithms, Complexity, and Games, Track B: Logic, Semantics, automata and Theory of Programming, Track C: Foundations of Networked Computation: Models, Algorithms, and Information Management. In response to the call for papers, a total 502 submissions were received: 346 for track A, 96 for track B, and 60 for track C. Each submission was assigned to at least three Program Committee members, aided by many subreviewers. Out of these, the committee decided to accept 147 papers for inclusion in the scientific program: 98 papers for Track A, 30 for Track B, and 19 for Track C. The selection was made by the Program Committees based on originality, quality, and relevance to theoretical computer science. The quality of the manuscripts was very high, and many deserving papers could not be selected. This year ICALP also solicitated brief announcements of work in progress with substantial interest for the community. In total 14 brief announcements were accepted for publication: 10 for Track A and 4 for Track C. The selection of the brief announcements was made by the Program Committees. The EATCS sponsored awards for both a best paper and a best student paper for each of the three tracks, selected by the Program Committees. The best paper awards were given to the following papers: Track A: Heng Guo and Mark Jerrum. “A polynomial-time approximation algorithm for all-terminal network reliability”. Track B: Dirk Nowotka and Aleksi Saarela. “An optimal bound on the solution sets of one-variable word equations and its consequences”. Track C: Dariusz Kowalski and Miguel A. Mosteiro. “Polynomial Counting in Anonymous Dynamic Networks with Applications to Anonymous Dynamic Algebraic Computations”. The best student paper awards, for papers that are solely authored by students, were given to the following papers: Track A: Shashwat Garg. “Quasi-PTAS for Scheduling with Precedences using LP Hierarchies”. Track B: Sarah Winter. “Uniformization problems for synchronizations of automatic relations on words”. Apart from the contributed talks and the brief announcements, ICALP 2018 included invited presentations by Jaroslav Nešetril, Alexander Schwarzmann, Sam Staton and Ryan Williams. This volume of the proceedings contains all contributed papers and brief announcements presented at the conference together with the papers and abstracts of the invited speakers. The program of ICALP 2018 also included presentation of the EATCS Award 2018 to Noam Nisan, the Gödel Prize 2018 to Oded Regev, the Presburger Award 2018 to Aleksander EATC S 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Editors: Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, and Donald Sannella Leibniz International Proceedings in Informatics Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany 107:xvi Preface Madry, and the EATCS Distinguished Dissertation Award to Bas Ketsman, Ilya Razenshteyn and Aviad Rubinstein. The program also included a memorial session for Maurice Nivat, the founder of ICALP and EATCS, who passed away in September 2017. Six satellite events of ICALP were held on 9 July, 2018: Modern Online Algorithms (MOLI) Game Solving: Theory and Practice Parameterized Approximation Algorithms Workshop (PAAW) Infinity Algorithmic Aspects of Temporal Graphs Constrained Recognition Problems The Summer School on Algorithms and Lower Bounds was organized immediately before ICALP during 6-9 July, 2018, with a follow-up workshop on Monday afternoon. The workshop was a satellite ICALP workshop devoted to presentations by selected participants of the school. The Summer School on Discrete Mathematics was organized after the conference during 16-20 July, 2018. The event was organized by the Institute of Mathematics of the Czech Academy of Sciences and the Computer Science Institute of Charles University