Seminář G²OAT: Solving Multiagent Path Finding on Highly Centralized Networks

When

28. 4. 2025
13:00 – 14:00

Where

Room TH:A-1247

Thákurova 7, Prague 6

Record

Zoom

In the regular Monday seminar of the G²OAT group, Michal Opler (FIT CTU) will present new results on the complexity and algorithms for Multiagent Path Finding in highly centralized networks. He shows the problem remains hard even on trees or graphs with low vertex cover, and introduces an FPT algorithm for networks with bounded distance to clique.

Event website

Abstract

How large can a set of simple closed curves on a torus be, such that any two curves are non-homotopic and intersect at most k times? It is known since 1996 that for any fixed k, such a set must be finite. The topic has been extensively studied, leading to a recent upper bound of k + O(k^½ log k) on the size of the set, established by Aougab and Gaster.

We resolve the problem by determining the optimal bound and providing a matching construction for every value of k. In particular, we show that the size of such a set never exceeds k + 6, and is at most k + 4 for sufficiently large k.

In this talk, we will present the main ideas behind the proof, which utilizes well-known tools from combinatorics, discrete optimization, and geometry, along with some number-theoretic observations.

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