[Mittagsseminar TI] Mittagsseminar Di 19.11.2024
Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU
Berlin spricht am
Dienstag, 19.11.2024, 12:00 Uhr, SR 055, Takustraße 9
Matthew Maat
zum Thema: Running in circles: Cycle patterns and how algorithms use them for games
Abstract: Parity games, mean payoff games
and energy games are examples of games that are played on the vertices
of a directed graph. The problem of finding optimal strategies or values
for these games is a well-studied topic, with
countless algorithms being proposed. It is interesting from a
complexity-theoretic viewpoint, as it is one of the few problems in both
NP and coNP for which no polynomial-time algorithm is known.
We introduce the notion of 'cycle pattern'
to shed some light on the underlying structure of these games. We
characterize which cycle patterns can be realized in a weighted graph.
We show some hardness results related to cycle patterns
and to computing the winner of a game using only cycle patterns. We
also show some bounds on the maximum required size of weights in the
graph, and what this implies for algorithms that solve mean payoff
games.
