Dear all, happy new year to everyone! The DFG Research Unit ADYN invites you to their next online seminar session on Zoom: *Monday, January 13th, 17:00 CET*. Link: https://rwth.zoom-x.de/j/68837156442?pwd=H4OW7bUYYAMXSPiqvxXuEMuTTmk7VY.1 Meeting-ID: 688 3715 6442 Kenncode: 593098 The following talks will be given: (1) "Chromatic Number of Randomly Augmented Graphs" by Anand Srivastav (Kiel University) (2) "Insights into (k, ρ)-Shortcutting Algorithms" by Alexander Leonhardt (Goethe University Frankfurt) Abstracts: (1) An extension of the Erdős-Renyi random graph model $G_{n,p}$ is the model of perturbed graphs introduced by Bohman, Frieze and Martin (2003). This is a special case of the randomly augmented graphs studied in this paper. An augmented graph is the union of a deterministic host graph and a random graph. Among the first problems in perturbed graphs has been the question how many random edges are needed to ensure Hamiltonicity of the graph. This question was answered in the paper by Bohman, Frieze and Martin. The host graph is often chosen to be a dense graph. In recent years several papers on combinatorial functions of perturbed graphs were published, e.g. on the emergence of powers of Hamiltonian cycles (Dudek, Reiher, Ruciński, Schacht 2020), the properties of Positional Games played on perturbed graphs (Clemens, Hamann, Mogge, Parczyk, 2020) and the emergence of multiple invariants e.g. fixed clique size (Bohman, Frieze, Krivelevich, Martin, 2004). In this paper we study the chromatic number of randomly augmented graphs. We concentrate on a host graph $H$ with chromatic number $o(n)$, augmented by a $G_{n,p}$ with $n^{-\frac{1}{3} + \delta}\leq p(n) \leq 1-\delta$ for some $\delta \in (0,1)$. We denote such a graph by $\pert_{H,p}$. Our main result is an upper bound for the chromatic number of such a randomly augmented graph $\pert_{H,p}: we show that for any $\epsilon>0$ there is a $n(\epsilon) \in \N$ such that for $n \geq n(\epsilon)$ with high probability $\chromaticOf{\pert_{H,p}} \leq (1+o(1)) \cdot \frac{n \log(b)}{2 (\log(n) - \log(\chromaticOf{H}))}$. This result collapses to the famous theorem of Bollobás (1988), when $H$ is the empty host graph, thus our result can be regarded as a generalization of the latter. Our proof is not constructive. To give the reader an impression of a coloring strategy, we give a constructive proof of the upper bound for the chromatic number of $\pert_{H,p}$ where the chromatic number of the host grah is at most $\frac{n}{\log(n)^{\alpha}}$ where $\alpha>\frac{1}{2}$. (2) A graph is called a (k, ρ)-graph iff every node can reach ρ of its nearest neighbors in at most k hops. This property has proven useful in the analysis and design of parallel shortest-path algorithms [Blelloch et al., 2016; Dong et al., 2021]. Any graph can be transformed into a (k, ρ)-graph by adding shortcuts. Formally, the (k,ρ)-Minimum-Shortcut-Problem (kρ-MSP) asks to find an appropriate shortcut set of minimal cardinality. We show that kρ-MSP is NP-complete in the practical regime of k ≥ 3 and ρ = Θ(n^ε) for ε > 0. With a related construction, we bound the approximation factor of known kρ-MSP heuristics [Blelloch et al., 2016] from below and propose algorithmic countermeasures improving the approximation quality. Further, we describe an integer linear problem (ILP) that optimally solves kρ-MSP. Finally, we compare the practical performance and quality of all algorithms empirically. This is joint work with Manuel Penschuck and Ulrich Meyer. For more information on ADYN and the seminar series, visit our website using the link https://adyn.informatik.rwth-aachen.de/ . Best, Tim