Prof. Dr. Tobias Friedrich

# Research Seminar (Winter Term 2021)

<previous seminar | next seminar>

## COVID-19 and virtual seminars

Due to the current situation we are not hosting seminars at the HPI anymore. Instead, we host virtual seminars via zoom. If you want to join the seminar on short notice or if you do not want to subscribe to the mailing list, please send an email to Katrin.Casel(at)hpi.de or to Andreas.Goebel(at)hpi.de.

## Description

A series of talks on current research and interesting topics in algorithm engineering and theoretical computer science. Everyone is welcome to attend talks.

If you want to give a talk about a topic in algorithm engineering or theoretical computer science, please write an e-mail to Katrin Casel or to Andreas Göbel.

## Announcements

For announcements of talks, subscribe to our mailing list.

## Talks (click on title to show abstract)

DateRoom SpeakerTitle
15.10. 11:00virtualJatin Batra

We study the generalized min sum set cover (GMSSC) problem, wherein given a collection of hyperedges E with arbitrary covering requirements k_e, the goal is to find an ordering of the vertices to minimize the total cover time of the hyperedges; a hyperedge e is considered covered by the first time when k_e many of its vertices appear in the ordering. We give a 4.642 approximation algorithm for GMSSC, coming close to the best possible bound of 4, already for the classical special case (with all k_e=1) of min sum set cover (MSSC) studied by Feige, Lovász and Tetali, and improving upon the previous best known bound of 12.4 due to Im, Sviridenko and van der Zwaan. Our algorithm is based on transforming the LP solution by a suitable kernel and applying randomized rounding. This also gives an LP-based 4 approximation for MSSC. As part of the analysis of our algorithm, we also derive an inequality on the lower tail of a sum of independent Bernoulli random variables, which might be of independent interest and broader utility.

Another well-known special case is the min sum vertex cover (MSVC) problem, in which the input hypergraph is a graph and k_e=1, for every edge. We give a 16/9 approximation for MSVC, and show a matching integrality gap for the natural LP relaxation. This improves upon the previous best 1.999946 approximation of Barenholz, Feige and Peleg. Finally, we revisit MSSC and consider the ell_p norm of cover-time of the hyperedges. Using a dual fitting argument, we show that the natural greedy algorithm achieves tight, up to NP-hardness, approximation guarantees of (p+1)^{1+1/p}, for all p>=1. For p=1, this gives yet another proof of the 4 approximation for MSSC.

29.10. 11:00virtualMartin Schirneck

An upper dominating set in a graph is an inclusion-wise minimal dominating set of maximum cardinality. Berge and Duchet in 1975 showed how to compute the upper domination number $$k^*$$ of an $$n$$-vertex graph in time $$O(n^{k^*+3})$$. Conversely, Bazgan et al. [TCS 2018] proved that $$k^*$$ cannot be computed in time $$f(k^*) n^{o(\sqrt{k^*})}$$ for any computable function $$f$$, unless the Exponential Time Hypothesis (ETH) fails. Very recently and independently of each other, Araújo et al. [ArXiv 2021] as well as Dublois, Lampis, and Paschos [CIAC 2021] closed this gap in ruling out any algorithm running in time $$f(k^*) n^{o(k^*)}$$ under ETH.

In the talk, we walk through the proof of Araújo et al. and discuss some open problems regarding the transversal rank of a hypergraph.

5.11. 11:00virtualNico Klodt
Contact processes are used to model various phenomena such as the spread of viruses and information through a network. An interesting aspect of a contact process is whether such an 'infection' becomes epidemic or dies out fast. In the SIS model for contact processes, the underlying network is represented by a graph. Each vertex of that graph can either be healthy or infected. Infected vertices can randomly infect their neighbors and become susceptible to the infection again when they heal. The infection rate λ of the process indicates how frequently vertices infect their neighbors. We analyze the survival time of the contact processes depending on λ on stars and clique stars. Clique stars are stars with additional edges, that connect the leaves to multiple cliques of equal size. We show a smooth transition between fast die out and long survival on stars and clique stars and prove that the additional edges of a clique star only impact the survival time notably if the cliques are sufficiently large.
12.11. 10:00virtualGeorge Skretas
Dynamic networks is a research area in the field of theoretical computer science tasked with investigating the algorithmic and structural properties of networked systems whose structure changes over time. The algorithmic theory of dynamic networks has risen in popularity due to the multitude of motivating systems that exist such as wireless systems, reconfigurable robotics and biological systems. Most of the work focuses on passively dynamic networks where the dynamic changes are decided by an external scheduler. In the past few years, there is a growing interest in actively dynamic networks where the changes are controlled by the network itself. This allows the network to reconfigure its own structure in order to more efficiently solve different tasks. In this talk, I will briefly introduce different models in the area of actively dynamic networks and continue by focusing on one such model where given an initial network G_s, the goal is to program the nodes with a distributed algorithm in order to reconfigure themselves, via edge activations/deactivations into a target network G_t with a small diameter.
19.11. 11:00virtualHans Gawendowicz
During a pandemic, people have to find a trade-off between meeting others and staying at home. While meeting others is pleasant, it also increases the risk of infection. We consider this dilemma by introducing a game-theoretic network creation model in which selfish agents can form bilateral connections. They benefit from their neighbors but at the same time they want to keep large distances to all the other agents. We look at two variants of this model. In the first variant, there are no restrictions on the connections being formed. In the second variant, we restrict which connections can be formed by introducing a host network defining the possible connections. We characterize optimal and equilibrium networks and give bounds on the Price of Anarchy and Price of Stability. For that, we also introduce the concept of Maximum Routing-Cost Spanning Trees, which are spanning trees maximizing the sum of distances between all pairs of nodes.
26.11. 11:00virtualWilhelm Friedemann
While last week was about responsible social distancing, this week will be about the opposite: Hosting the best parties in town. The question is - given a graph representing friendship relationships and a weight function representing each friend's coolness - how to select the group of friends who know each other (are connected) and maximize their summed coolness. Apart from party planning, the problem appears as the 'Maximum-Weight Connected Subgraph Problem (MWCS)' in many real-world domains, ranging from biological network analysis, where one wants to find signaling pathways in protein networks, to video-processing. In the talk, I present the results of my Master's thesis: a variety of fixed-parameter intractability results for the MWCS with respect to the weight and cardinality of the solution. But don't worry, I also provide two FPT algorithms, if you know (due to current pandemic constraints) the maximum number of friends you are allowed to invite.
17.12. 10:00virtualMichael Vaichenker,
Bashini Mahaarachchi
TBA

TBA
21.01. 11:00virtualMerlin Haye
TBA