[Mittagsseminar TI] Mittagsseminar Di 19.11.2024

[Michaela Borzechowski/Krüger <michaela.borzechowski@fu-berlin.de>]

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.