CoSP final meeting will take place in Lyon, hosted by CNRS-École Normale Supérieure de Lyon (ENS), from 11th June until 13th June 2024.
Workshop Games and Structure of Graphs
Place: ENS de Lyon, "Monod" building
Address: 46 allée d'Italie, Lyon 7e arrondissement
Public transport: tramway stop "ENS de Lyon" or métro station "Debourg"
Room: 4th floor, B1
Tuesday 11th June 2024
Morning: Joint work
10:00 welcome coffee in B1
12:30 lunch in ENS Lyon's cafeteria
14:00 Éric Duchêne (Lyon): An introduction of positional games in graphs
Positional games are class of combinatorial games that have been extensively studied in recent literature. They include popular recreational games like Tic-Tac-Toe, Hex and Sim. They are played on a hypergraph called the board where the hyperedges are called the winning sets. The two players, generally Maker and Breaker, alternately claimed vertices of the board until a winning set is lled. Maker wants to claim all the elements of a winning set wheareas Breaker wants to prevent her to do so. As 2-player nite games with perfect information, one of the players always have a winning strategy and we are interested in computing which player has such a strategy. In this talk we will present some important results and open problems on this topic from its introduction to most recent studies.
15:00 Aline Parreau (Lyon): Partition strategies for the Maker-Breaker domination game
In this talk we will focus on a particular positional game, the Maker-Breaker domination game. In this game, Dominator and Staller alternately claim vertices of a graph. Dominator wants to claim all the vertices of a dominating set whereas Staller wants to prevent her to do so, or equivalently wants to claim a vertex and all its neighbours. Deciding if Staller or Dominator has a winning strategy is in general a PSPACE-complete problem. Using partition strategies for Dominator, we present some positive results: we prove that Dominator always wins in a regular graphs, that deciding the outcome in an outerplanar graph or a block graph is polynomial and we reduce the complexity for interval graphs by proving that the problem is equivalent to a structural problem and thus belongs to NP.
Joint work with Guillaume Bagan, Éric Duchêne, Valentin Gledel, Tuomo Lehtilä.
16:00 Ron Holzman (Technion): Strong equilibrium in network congestion games
A network congestion game is played on a directed, two-terminal network. Every player chooses a route from his origin to his destination. The cost of a route is the sum of the costs of the arcs on it. The arc cost is a function of the number of players who use it. Rosenthal proved that such a game always has a Nash equilibrium in pure strategies. In this lecture we present a systematic study of the classes of networks for which a strong equilibrium is guaranteed to exist, under either of two opposite monotonicity assumptions on the arc cost functions. The main results are:
(a) If costs are increasing, strong equilibrium is guaranteed on extension-parallel networks, regardless of whether the players' origins and destinations are the same or may differ.
(b) If costs are decreasing, and the players have the same origin but possibly different destinations, strong equilibrium is guaranteed on series-parallel networks.
(c) If costs are decreasing, and both origins and destinations may differ, strong equilibrium is guaranteed on multiextension-parallel networks. In each case, the network condition is not only sufficient but also necessary in order to
guarantee strong equilibrium.
The presentation is based on old results by Holzman and Law-Yone in the increasing case, by Epstein, Feldman and Mansour in the decreasing case, and on more recent extensions by Holzman and Monderer of both sets of results.
Wednesday 12th June 2024
Morning: Joint work
10:00 welcome coffee in B1
12:30 lunch in ENS Lyon's cafeteria
14:00 Martin Loebl (CUNI): Fair Claims Resolution
I will speak about some aspects of fair claims resolution, which includes, e.g., resolution by a central authority, by markets (autonomous agents), by a fix-point theorem, and even by elections (autonomous 'goods'). I will explain our recent results on critical goods distribution and on multi-criteria envy-free allocations.
15:00 Mykhaylo Tyomkyn (CUNI): Alternating paths in oriented graphs with large semidegree
In new progress on conjectures of Stein, and Addario-Berry, Havet, Linhares Sales, Reed and Thomassé, we prove that every oriented graph with all in- and out-degrees greater than 5k/8 contains an alternating path of length k. This improves on previous results of Klimošová and Stein, and Chen, Hou and Zhou.
Thursday 13th June 2024
Morning: Joint work
10:00 welcome coffee in B1
12:30 lunch in ENS Lyon's cafeteria
14:00 Kristina Vušković (University of Leeds): Structure and algorithms for even-hole-free graphs
The class of even-hole-free graphs (i.e. graphs that do not contain a chord-less cycle of even length as an induced subgraph) has been studied since the 1990's, initially motivated by their structural similarity to perfect graphs. It is known for example that they can be decomposed by star cutsets and 2-joins into algorithmically well understood subclasses, which has led to, for example, their polynomial time recognition. Nevertheless, the complexity of a number of classical computational problems remains open for this class, such as the coloring and stable set problems.
15:00 Nicolas Trotignon (Lyon): Unavoidable induced subgraphs in graphs with complete bipartite induced minors
We prove that if a graph contains K3,4 as an induced minor, then it contains a triangle or a theta as an induced subgraph. Here, a theta is a graph made of three internally vertex-disjoint chordless paths P = a ... b, P´ = a ... b, P´´ = a ... b, each of length at least two, such that no edges exist between the paths except the three edges incident to a and the three edges incident to b. A consequence is that excluding a grid and a complete bipartite graph as induced minors is not enough to guarantee a bounded tree-independence number, or even that the treewidth is bounded by a function of the size of the maximum clique, because the existence of graphs with large treewidth that contain no triangles or thetas as induced subgraphs is already known (the so-called layered wheels).
This a joint work with Maria Chudnovsky, Meike Hatzel, Tuukka Korhonen and Sebastian Wiederrecht.
Posted on 2024-06-05