Colloquia and Seminars

Dominating Set is a fundamental problem in graph theory: given a graph, find a minimum-weight subset of vertices such that every vertex is either selected or shares an edge with a selected vertex.

In online settings where vertices arrive sequentially, comparing algorithms against an offline optimum with full knowledge of the input leads to extremely strong lower bounds, where even a simple star graph shows that any online algorithm must have competitive ratio Ω(n), with n being the number of vertices, matching the trivial strategy of selecting all vertices.

We study the incremental dominating set problem, where the optimal algorithm is constrained to the same choices available to online algorithms. This introduces a benchmark that enables a meaningful comparison between algorithms.

We present the first results for vertex-weighted graphs and randomized algorithms in this model. For incremental dominating set, we give an O(Δ)-competitive deterministic algorithm and an O(log²Δ)-competitive randomized algorithm, where Δ is the maximum degree in the graph.

We extend these results to the Connected Dominating Set problem, which requires the dominating set to be connected. When the neighborhood of each arriving vertex is known in advance, we can improve the competitive ratio of deterministic algorithms to be polylogarithmic.

Finally, we establish matching lower bounds, showing that all our results are optimal up to constant factors.

Distributed asynchronous systems often require explicit synchronization to ensure the correct implementation of shared objects. In this talk, I introduce the Delaying the Future approach for reasoning about the ordering of events in distributed executions. Its key idea is that, under certain conditions, events can be postponed without any process noticing the change.

I will show how this technique leads to characterizations of communication requirements in asynchronous message-passing systems and in shared-memory systems under the TSO memory model. The Delaying the Future approach provides a unified way to understand the synchronization required by linearizable implementations of common objects such as registers, stacks, and snapshots.

The study of spectral graph determination is a central and fascinating topic in spectral graph theory and algebraic combinatorics. This area investigates the spectral characterization of various classes of graphs, develops methods for constructing and distinguishing cospectral nonisomorphic graphs, and analyzes the conditions under which the spectrum of a graph uniquely determines its structure. In the first part of the seminar, we present both classical results and recent advances in spectral graph determination.

The study of graph symmetries and different notions of transitivity is also of fundamental interest in algebraic graph theory. In the second part of the talk, we examine transitivity properties of Gilbert graphs and their complements, and discuss the main ideas underlying these results.