G²OAT seminar: Reconfiguration Using Generalized Token Jumping


13. 5. 2024
13:00 – 14:00


Room TH:A-1247

Thákurova 7, Prague 6



Jan Matyáš Křišťan (FIT CTU) will speak at the regular Monday seminar of the G²OAT group. In his talk, he will discuss reconfiguration in graphical problems, where he will focus on the possibilities of transition between two solutions using small steps, both by moving one token to any vertex of the graph (Token Jumping) and by moving a token to an adjacent vertex (Token Sliding).

Event website


The functionality of a graph defined by [Alecu et al.: Graph functionality, JCTB2021] is a parameter that generalizes graph degeneracy. Informally, the functionality of a graph G is minimal k such that in any induced subgraph H of G there is a vertex v in H and a set S of k vertices that the adjacency of v and any vertex u in H is determined by the adjacency of u to S. I will present (almost) matching lower and upper bounds for the functionality of random graphs G(n,p) for all possible values of p. For a large range of p, the bounds differ in a constant factor. For values of p that are near to 0 or 1, the bounds differ in log n factor.

This is joint work with L. Folwarczný, M. Opler, P. Pudlák, R. Šámal, T. Vu.

The person responsible for the content of this page: Bc. Veronika Dvořáková