ABSTRACT. Research on Temporal Graphs has greatly  expanded in the last few years.

The majority of the results

till now , address problems related to the notion of Temporal Paths.

In this talk, we focus , instead , on some selected problems whose main topic is not on Temporal Paths.

In particular, we will discuss Temporal Vertex Covers , the notion of Temporal Transitivity , and also

issues and models of stochastic temporal graphs. We discuss the concept of a sliding time window in temporal graphs.

The talk  aims to motivate new research towards lifting more topics of algorithmic

graph theory to the temporal case.

ABSTRACT. We prove that functions over the reals computable in polynomial time can be characterized using discrete ordinary differential equations (ODE), also known as finite differences. We also provide a characterization of functions computable in polynomial space over the reals.

In particular, this covers space complexity, while existing characterizations were only able to cover time complexity, and were restricted to functions over the integers, and we prove that no artificial sign or test function is needed even for time complexity.

At a technical level, this is obtained by proving that Turing machines can be simulated with analytic discrete ordinary differential equations. We believe this result opens the way to many applications, as it opens the possibility of programming with ODEs, with an underlying well-understood time and space complexity.

ABSTRACT. We establish that constructive continued fraction dimension originally defined using s-gales is robust, but surprisingly, that the effective continued fraction dimension and effective (base-b) Hausdorff dimension of the same real can be unequal in general.

We initially provide an equivalent characterization of continued fraction dimension using Kolmogorov complexity. In the process, we provide the construction of an optimal lower semicomputable s-gale for continued fractions. We also prove new bounds on the Lebesgue measure of continued fraction cylinders, which may be of independent interest.

We apply these bounds to reveal an unexpected behavior of continued fraction dimension. It is known that feasible dimension is invariant with respect to base conversion. We also know that Martin-Lof randomness and computable randomness are invariant not only with respect to base conversion, but also with respect to the continued fraction representation. In contrast, for any 0 < epsilon < 0.5, we prove the existence of a real whose effective Hausdorff dimension is less than epsilon, but whose effective continued fraction dimension is greater than or equal to 0.5. This phenomenon is related to the "non-faithfulness" of certain families of covers, investigated by Peres and Torbin and by Albeverio, Ivanenko, Lebid and Torbin .

We also establish that for any real, the constructive Hausdorff dimension is at most its effective continued fraction dimension.

ABSTRACT. We study the existence of optimal and p-optimal proof systems for classes in the Boolean hierarchy over NP. Our main results concern DP, i.e., the second level of this hierarchy:

If all sets in DP have p-optimal proof systems, then all sets in coDP have p-optimal proof systems. The analogous implication for optimal proof systems fails relative to an oracle.

As a consequence, we clarify such implications for all classes C and D in the Boolean hierarchy over NP: either we can prove the implication or show that it fails relative to an oracle.

Furthermore, we show that the sets SAT and TAUT have p-optimal proof systems, if and only if all sets in the Boolean hierarchy over NP have p-optimal proof systems which is a new characterization of a conjecture studied by Pudlák.

ABSTRACT. Previous work on Dynamic Complexity has established that there exist dynamic constant-time parallel algorithms for regular tree languages and context-free languages under label or symbol changes. However, these algorithms were not developed with the goal to minimise work (or equivantly, the number of processors). In fact, their inspection yields the work bounds O(n^2) and O(n^7) per change operation, respectively. In this paper, dynamic algorithms for regular tree languages are proposed that generalise the previous algorithms in that they allow unbounded node rank and leaf insertions, while improving the work bound from O(n^2) to O(n^ϵ), for arbitrary ϵ > 0. For context-free languages algorithms with better work bounds (compared with O(n^7)) for restricted classes are proposed: for every ϵ > 0 there are such algorithms for deterministic context-free languages with work bound O(n^(3+ϵ)) and for visibly pushdown languages with work bound O(n^(2+ϵ)).

ABSTRACT. We study a natural problem about rational behaviors in multiplayer non-zero-sum sequential infinite duration games played on graphs: rational verification, that consists in deciding whether all the rational answers to a given strategy satisfy some specification.

We give the complexities of that problem for two major concepts of rationality: Nash equilibria and subgame-perfect equilibria, and for three major classes of payoff functions: energy, discounted-sum, and mean-payoff.

ABSTRACT. We analyse an algorithm solving stochastic mean-payoff games, combining the ideas of relative value iteration and of Krasnoselskii-Mann damping. We derive parameterized complexity bounds for several classes of games satisfying irreducibility conditions. We show in particular that an $\epsilon$-approximation of the value of an irreducible concurrent stochastic game can be computed in a number of iterations in $O(|\log\epsilon|)$ where the constant in the $O(\cdot)$ is explicit, depending on the smallest non-zero transition probabilities. This should be compared with a bound in $O(|\epsilon|^{-1}|\log(\epsilon)|)$ obtained by Chatterjee and Ibsen-Jensen (ICALP 2014) for the same class of games, and to a $O(|\epsilon|^{-1})$ bound by Allamigeon, Gaubert, Katz and Skomra (ICALP 2022) for turn-based games. We also establish parameterized complexity bounds for entropy games, a class of matrix multiplication games introduced by Asarin, Cervelle, Degorre, Dima, Horn and Kozyakin. We derive these results by methods of variational analysis, establishing contraction properties of the relative Krasnoselskii-Mann iteration with respect to Hilbert's

ABSTRACT. We study relationships between different relaxed notions of core stability in hedonic games. In particular, we study (i) q-size core stable outcomes in which no deviating coalition of size at most $q$ exists and (ii) k-improvement core stable outcomes in which no coalition can improve by a factor of more than k. For a large class of hedonic games, including fractional and additively separable hedonic games, we derive upper bounds on the maximum factor by which a coalition of a certain size can improve in a q-size core stable outcome. We further provide asymptotically tight lower bounds for a large class of hedonic games. Finally, our bounds allow us to confirm two conjectures by Fanelli et al. [IJCAI'21] for symmetric fractional hedonic games (S-FHGs): (i) every q-size core stable outcome in an S-FHG is also (q/(q-1))-improvement core stable and (ii) the price of anarchy of q-size stability in S-FHGs is precisely (2q)/(q-1).

ABSTRACT. The \textsc{Hunters and Rabbit} game is played on a graph $G$ where the Hunter player shoots at $k$ vertices in every round while the Rabbit player occupies an unknown vertex and, if it is not shot, must move to a neighbouring vertex after each round. The Rabbit player wins if it can ensure that its position is never shot. The Hunter player wins otherwise. The hunter number $h(G)$ of a graph $G$ is the minimum integer $k$ such that the Hunter player has a winning strategy (i.e., allowing him to win whatever be the strategy of the Rabbit player). This game has been studied in several graph classes, in particular in bipartite graphs (grids, trees, hypercubes...), but the computational complexity of computing $h(G)$ remains open in general graphs and even in more restricted graph classes such as trees. To progress further in this study, we propose a notion of monotonicity (a well-studied and useful property in classical pursuit-evasion games such as Graph Searching games) for the \textsc{Hunters and Rabbit} game imposing that, roughly, a vertex that has already been shot ``must not host the rabbit anymore''. This allows us to obtain new results in various graph classes.

More precisely, let the monotone hunter number $mh(G)$ of a graph $G$ be the minimum integer $k$ such that the Hunter player has a monotone winning strategy. We show that $pw(G) \leq mh(G) \leq pw(G)+1$ for any graph $G$ with pathwidth $pw(G)$, which implies that computing $mh(G)$, or even approximating $mh(G)$ up to an additive constant, is \textsf{NP}-hard. Then, we show that $mh(G)$ can be computed in polynomial time in split graphs, interval graphs, cographs and trees. These results go through structural characterisations which allow us to relate the monotone hunter number with the pathwidth in some of these graph classes. In all cases, this allows us to specify the hunter number or to show that there may be an arbitrary gap between $h$ and $mh$, i.e., that monotonicity does not help. In particular, we show that, for every $k\geq 3$, there exists a tree $T$ with $h(T)=2$ and $mh(T)=k$. We conclude by proving that computing $h$ (resp., $mh$) is \FPT~parameterised by the minimum size of a vertex cover.