Julien Baste (University of Lille, France)
Temporal matchings
Abstract: A temporal graph describes the evolution of a graph with time. In this presentation we introduce the notion of gamma-edges in a temporal graph, with gamma being an integer, that are edges that appear during gamma consecutive fractions of time and the notion of temporal matchings, that are independent gamma-edge set belonging to the temporal graph. In this talk, we will discuss the NP-hardness of computing a temporal matching when gamma > 1. We will also present a kernalisation of the problem parameterized by the solution size as well as the 2-approximation to solve it.
Binh-Minh Bui-Xuan (LIP6 and University Pierre and Marie Curie, France)
Near-optimal computation of temporal matching
Abstract: Temporal graphs are the modeling of pairwise and historical interaction in recordings of a dataset. A temporal matching formalizes the planning of pair working sessions of a required duration. Unlike the static case of graph matchings, computing temporal matchings turns out to be (very) hard. Nonetheless, we present in this talk techniques for finding near-optimal temporal matchings, including a PTAS, an exact algorithm, and a greedy algorithm outperforming the PTAS in practice. All these three algorithms have been implemented with opensource code, and confronted to artificial and real-world datasets.
Markus Chimani (Osnabrück University, Germany)
Approximating multistage matching problems
Abstract:
In multistage perfect matching problems, we are given a sequence of graphs on the same vertex set
and are asked to find a sequence of perfect matchings, corresponding to the sequence of graphs, such that
consecutive matchings are as similar as possible. More precisely, we aim to maximize the intersections,
or minimize the unions between consecutive matchings.
These problems are NP-hard even in very restricted scenarios, and we will concentrate on approximation algorithms:
On the one hand, we show a tight 2-stage approximation. On the other hand, we discuss general methods to deduce
multistage approximations from blackbox 2-stage approximations.
We will conclude with pointing out how to extend these results to a wider range of subgraph problems.
Frank Kammer (TH Mittelhessen University of Applied Sciences, Germany)
Multistage graph problems on a global budget
Abstract:
Time-evolving or temporal graphs gain more and more popularity when studying the behavior of complex networks.
In this context, the multistage view on computational problems is among the most natural frameworks.
Roughly speaking, herein one studies the different (time) layers of a temporal graph (effectively meaning that the edge set
may change over time, but the vertex set remains unchanged), and one searches for a solution of a given graph problem for each layer.
The twist in the multistage setting is that the solutions found must not differ too much between subsequent layers.
We relax on this already established notion by introducing a global instead of the local budget view studied so far.
More specifically, we allow for few disruptive changes between subsequent layers but request that overall, that is,
summing over all layers, the degree of change is moderate. Studying several classical graph problems (both NP-hard and
polynomial-time solvable ones) from a parameterized complexity angle, we encounter both fixed-parameter tractability
and parameterized hardness results. Surprisingly, we find that sometimes the global multistage versions of NP-hard problems
such as VERTEX COVER turn out to be computationally more tractable than the ones of polynomial-time solvable problems such as MATCHING.
This is joint work with Klaus Heeger, Anne-Sophie Himmel, Rolf Niedermeier, Malte Renken, and Andrej Sajenko.
Kitty Meeks (University of Glasgow, UK)
A new temporal interpretation of cluster editing
Abstract:
Given an input graph G, how many edges must we add or delete to transform G into a disjoint union of cliques?
This problem for static graphs is known as Cluster Editing, and has been studied extensively in the literature.
But what if our input graph changes over time? One interpretation of this problem – in which the goal is to obtain
a disjoint union of cliques at every timestep – has recently been addressed in the temporal graphs community.
Here we consider a different temporal analogue of the static Cluster Editing problem: our goal is to transform
the input temporal graph in to a union of temporal cliques (that is, subsets of vertices within which each pair
is connected frequently over a given time interval, but not necessarily at every step) which are pairwise disjoint
in at least one of space (having disjoint vertex sets) and time (the intervals over which they exist being far apart).
Perhaps unsurprisingly, this problem turns out to be very challenging computationally, and is NP-hard even when
the underlying graph is a path; we are, however, are able to obtain efficient parameterised algorithms for a number of special cases.
In this talk I will give an overview of recent work on this problem, as well as highlighting some promising directions for future research.
This is joint work with Cristiano Bocci (University of Siena), Chiara Capresi (University of Siena) and John Sylvester (University of Glasgow).
Francesco Gullo (UniCredit, Italy)
Temporal core decomposition
Abstract:
Core decomposition is a well-established graph primitive, whose goal is to find dense subgraphs organized into a hierarchical structure.
In this talk we show how to extend the notion of core decomposition to the context of temporal graphs.
We introduce the notion of 'span-core', which is defined as a subgraph associated to its temporal span, i.e., the time
interval where that subgraph is recognized as a core, and focus on challenges, algorithms and applications of computing
the span-core decomposition (i.e., the set of all span-cores) of a temporal graph.
Hendrik Molter (Ben-Gurion University of the Negev, Israel)
Temporal reachability minimization: delaying vs. deleting
Abstract:
We study spreading processes in temporal graphs, i. e., graphs whose connections change over time.
These processes naturally model real-world phenomena such as infectious diseases or information flows.
More precisely, we investigate how such a spreading process, emerging from a given set of sources, can be contained
to a small part of the graph. To this end we consider two ways of modifying the graph, which are (1) deleting connections and
(2) delaying connections. We show a close relationship between the two associated problems and give a polynomial time algorithm
when the graph has tree structure. For the general version, we consider parameterization by the number of vertices to which the
spread is contained. Surprisingly, we prove W[1]-hardness for the deletion variant but fixed-parameter tractability for the delaying variant.
Based on joint work with Malte Renken and Philipp Zschoche.
Mathias Weller (Gustave Eiffel University, France)
Parameterized cops'n'robbers on edge-periodic temporal graphs
Abstract:
The cops-and-robbers chase game is one of the fundamental concepts in (static) graph theory,
modeling multiple important width parameters and computational problems. We review a recent series
of papers that analyzes the game on temporal graphs in which each edge blinks into and out of existence
in its own periodic pattern. While it is to be expected that it is, in general, NP-hard to decide the winner
of the game, the sheer amount of restrictions under which this problem remains intractable may be more astonishing.
We discuss the parameterized complexity of deciding the winner of the pursuit evasion game with one cop
and one robber parameterized by properties of the periodic occurrence-patterns as well as structural parameters
of the underlying static graph, discovering algorithms for the chase game as well as surprising relations
to automata theory and static graph theory.
Vincent Froese (Technical University Berlin, Germany)
Two influence maximization games on graphs made temporal
Abstract:
To address the dynamic nature of real-world networks, we generalize competitive diffusion games and Voronoi
games from static to temporal graphs, where edges may appear or disappear over time. This establishes a new direction
of studies in the area of graph games, motivated by applications such as influence spreading. As a first step,
we investigate the existence of Nash equilibria in temporal competitive diffusion and Voronoi games on different
temporal graph classes. Even when restricting our studies to temporal paths and cycles, this turns out to be a
challenging undertaking, revealing significant differences between the two games in the temporal setting.
Notably, both games are equivalent on static paths and cycles. Our two main results are proofs for the existence
of Nash equilibria in temporal competitive diffusion and Voronoi games when the edges are restricted not to disappear over time.
Joint work with Niclas Boehmer, Julia Henkel, Yvonne Lasars, Rolf Niedermeier, and Malte Renken.
Neven Villani (LaBRI and ENS Paris-Saclay, France)
Some thoughts on dynamic analogs of unit disk graphs
Abstract:
In this talk, we will present some preliminary results on the study of dynamic analogs of unit disk graphs (UDGs).
In particular, we are interested in deciding if a given temporal graph admits a sequence of embeddings such that each snapshot
is consistent with the UDG model (i.e., an edge exists between two vertices iff their distance is less than a given threshold)
and the positions vary in a limited way from one embedding to the next. In other words, can the graph result from the movements
of a set of mobile entities?
This is a joint work with Arnaud Casteigts.
Antonio Fernandez-Anta (IMDEA Networks Institute, Spain)
Routing in generalized geometric random graphs
Abstract: In this talk, we present a new random graph model that we denote (κ,π)-KG and two new greedy routing algorithms (of deterministic and probabilistic nature). The (κ,π)-KG graphs have power-law degree distribution and small-world properties. (κ,π)-KG roots on the Geometric Inhomogeneous Random Graph (GIRG) model. To construct (κ,π)-KG graph, we introduce two parameters κ and π in the process. With these parameters, we can generate Kleinberg and power-law networks as special cases of (κ,π)-KG. Also, we propose two new greedy routing algorithms to reduce the fail ratio and maintain a good routing performance. The first algorithm is deterministic, the second is, in essence,a weighted random walk. We use simulation techniques to test our network model and the new routing algorithms on the two graph models (GIRG and (κ,π)-KG). In our simulations, we evaluate the number of hops to reach a destination from a source and the routing fail ratio. Also, we measure the impact of the parameters (κ and π) on the performance of the new routing algorithms. We observe that our graph model(κ,π)-KG is more flexible than GIRG, and the new routing algorithms have better behavior than the routing algorithms previously proposed.
Petter Holme (Tokyo Institute of Technology, Japan)
Temporal network epidemiology: Subtleties and algorithms
Abstract: The SIR and SIS models are the canonical model of epidemics of infections that make people immune upon recovery. Many open questions in computational epidemiology concern the underlying contact structure’s impact on models like the SIR or SIS. Temporal networks constitute a theoretical framework capable of encoding structures both in the networks of who could infect whom and when these contacts happen. In this talk, we discuss the detailed assumptions behind such simulations—how to make them comparable with analytically tractable formulations of the SIR model, and at the same time, as realistic as possible. We also discuss fast algorithms for such simulations and the challenges in improving them.
Workshop organizers*
George B. Mertzios (Durham University, UK)
Paul G. Spirakis (University of Liverpool, UK and University of Patras, Greece)
Eleni C. Akrida (Durham University, UK)
Viktor Zamaraev (University of Liverpool, UK)
* Partially supported by the EPSRC grants EP/P020372/1 and EP/P02002X/1, and by the EEE/CS University of Liverpool Initiative NeST.