GRASTA 2022
10th Workshop on GRAph Searching, Theory and Applications

May 16th-20th, 2022, Porquerolles, France

Merci (de nouveau) à Christelle pour les photos

This edition of GRASTA was initially planned for May 2020. It will hold on May 16th-20th, 2022 :)

• Home
• Venue
• Registration
• List of Participants
  
• List of talks
  
• Program
  
• About Graph Searching
• Previous GRASTA
• Contact

ED STIC

List of presentations

• Spyros Angelopoulos, LIP6, CNRS, Paris, France
  Online search with hints.
  The linear search problem, informally known as the cow path problem, is one of the fundamental problems in search theory. In this problem, an immobile target is hidden at some unknown position on an unbounded line, and a mobile searcher, initially positioned at some specific point of the line called the root, must traverse the line so as to locate the target. The objective is to minimize the worst-case ratio of the distance traversed by the searcher to the distance of the target from the root, which is known as the competitive ratio of the search.
  In this work we study this problem in a setting in which the searcher has a hint concerning the target. We consider three settings in regards to the nature of the hint: i) the hint suggests the exact position of the target on the line; ii) the hint suggests the direction of the optimal search (i.e., to the left or the right of the root); and iii) the hint is a general k-bit string that encodes some information concerning the target. Our objective is to study the Pareto-efficiency of strategies in this model. Namely, we seek optimal, or near-optimal tradeoffs between the searcher's performance if the hint is correct (i.e., provided by a trusted source) and if the hint is incorrect (i.e., provided by an adversary).


• Stéphane Devismes, Univ. Picardie Jules Verne, France
  Optimal Exclusive Perpetual Grid Exploration by Luminous Myopic Opaque Robots with Common Chirality.
  We consider swarms of luminous myopic opaque robots that run in synchronous Look-Compute-Move cycles. These robots have no global compass, but agree on a common chirality. In this context, we propose optimal solutions to the perpetual exploration of a finite grid. Precisely, we investigate optimality in terms of the visibility range, number of robots, and number of colors. In more detail, under the optimal visibility range one, we give an algorithm which is optimal w.r.t. both the number of robots and colors: it uses two robots and three colors. Under visibility two, we design two algorithms: the first one uses three robots with an optimal number of colors (i.e., one), the second one achieves the best trade-off between the number of robots and colors, i.e., it uses two robots and two colors.


• Thomas Dissaux, Univ. Cote d'Azur, Inria, CNRS, I3S, France
  Treelength and pathlength of subclasses of planar graphs
  A Path-decomposition of a graph G=(V,E) is a sequence of subsets of V, called bags that satisfy some connectivity properties. A tree-decomposition of a graph G=(V,E) is a set of subsets of its vertices, called bags, that are organized in a tree-like fashion. The length of a path-decomposition (resp. tree-decomposition) of a graph G is the greatest distance between two vertices that belong to a same bag and the pathlength (resp. treelength), denoted by pl(G) (resp. tl(G)) of G is the smallest length of its path-decompositions.
  These parameters have been studied for their algorithmic applications for several classical metric problems. Deciding if the pathlength (resp. treelength) of a graph G is at most 2 is NP-complete, however no result (resp. few results) about planar graphs is known. In this talk, we will first define these two problems, and make an overview of the known results about them. Then, we will present you a (+1)-approximation of 2-connected Outerplanar graphs, based on a characterization of almost optimal (of length at most pl(G)+1) path-decompositions of such graphs. By the way, since this characterization is based on the one of trees, we will also show you a linear time algorithm to compute the pathlength of trees.


• Harmender Gahlawat‬, Ben-Gurion University of the Negev, Israel
  The game of Cops and Robber on string graphs
  Cops and Robber is a well-studied two player pursuit-evasion game where a team of cops tries to capture the position of the robber. The game is well-studied for graphs having some geometric representation. We continue this study and show that 13 cops are always sufficient to capture the robber on a connected string graph, improving upon a result of Gavenciak et al. We also use similar techniques to give a winning strategy using four cops for the game of Fully Active Cops and Robber on planar graphs.


• Robert Ganian, Technische Universität Wien, Institute of Logic and Computation, Austria
  A Unifying Framework for Characterizing and Computing Width Measures
  Algorithms for computing or approximating optimal decompositions for parameters such as treewidth (which, famously, also admits a graph-searching based characterization) or clique-width have so far traditionally been tailored to specific width parameters. Moreover, for mim-width, no efficient algorithms for computing good decompositions were known, even under highly restrictive parameterizations. In this work we identify F-branchwidth as a class of generic decompositional parameters that can capture mim-width, treewidth, clique-width as well as other measures. We show that while there is an infinite number of F-branchwidth parameters, only a handful of these are asymptotically distinct. We then develop fixed-parameter and kernelization algorithms (under several structural parameterizations) that can approximate every possible F-branchwidth, providing a unifying parameterized framework that can efficiently obtain near-optimal tree-decompositions, k-expressions, as well as optimal mim-width decompositions.


• Petr Golovach, Univ. Bergen, Norway
  Can Romeo and Juliet Meet? Or Rendezvous Games with Adversaries on Graphs:
  We introduce the rendezvous game with adversaries. In this game, two players, Facilitator and Divider, play against each other on a graph. Facilitator has two agents, and Divider has a team of k agents located in some vertices of the graph. They take turns in moving their agents to adjacent vertices (or staying put). Facilitator wins if his agents meet in some vertex of the graph. The goal of Divider is to prevent the rendezvous of Facilitator's agents. Our interest is to decide whether Facilitator can win. It appears that, in general, the problem is PSPACE-hard and, when parameterized by k, co-W[2]-hard. Moreover, even the game's variant where we ask whether Facilitator can ensure the meeting of his agents within t steps is co-NP-complete already for t=2. On the other hand, for chordal and P_5-free graphs, we prove that the problem is solvable in polynomial time. These algorithms exploit an interesting relation of the game and minimum vertex cuts in certain graph classes. Finally, we show that the problem is fixed-parameter tractable parameterized by both the graph's neighborhood diversity and t.
  Joint work with Fedor V. Fomin and Dimitrios M. Thilikos.


• David Ilcinkas, CNRS, LaBRI, Bordeaux, France
  Certifying in Coq results on mobile agents: a user perspective
  Results in distributed computing by mobile entities tend to become more and more complex, relying on tedious case-by-case analyses and/or subtle arguments. On the other hand, model checking tools and proof assistants gain maturity, and there now exist frameworks which are specialized for distributed computing by mobile entities. In this talk, I will present my personal experience with the Pactole framework of the Coq proof assistant, that Sébastien Bouchard and I used to prove a result on graph exploration by mobile robots.


• Shahin Kamali, University of Manitoba, Canada
  A Review of the Graph Burning Problem
  Graph burning is a simple model for the spread of social influence in networks. The objective is to measure how quickly a "fire," e.g., a piece of fake news, can be spread in a network. The burning process takes place in discrete rounds. In each round, a new fire breaks out at a selected vertex, while the old fires extend to their neighbours and burn them. A burning schedule sets where the new fire breaks out in each round, and the burning problem asks for a schedule that burns all vertices in a minimum number of rounds. The burning conjecture states that any connected graph of n vertices can be burned via sqrt(n) rounds. We survey some recent algorithmic results for the graph burning problem in this talk. In particular, we review an algorithm for burning any graph in sqrt(4n/3) + O(1) rounds and approximation algorithms for burning general graphs and a few graph families.


• Arnaud Labourel, LIS, Univ. Aix Marseille, CNRS, France
  Almost-Optimal Deterministic Treasure Hunt in Arbitrary Graphs:
  A mobile agent navigating along edges of a simple connected graph, either finite or countably infinite, has to find an inert target (treasure) hidden in one of the nodes. This task is known as treasure hunt. The agent has no a priori knowledge of the graph, of the location of the treasure or of the initial distance to it. The cost of a treasure hunt algorithm is the worst-case number of edge traversals performed by the agent until finding the treasure. Let e(d) be the number of edges whose at least one extremity is at distance less than d from the starting position of the mobile agent. Awerbuch, Betke, Rivest and Singh conjectured in 1999 that it is impossible to find a treasure hidden in a node at distance at most d at cost nearly linear in e(d). We first design a deterministic treasure hunt algorithm working in the model without any restrictions on the moves of the agent at cost 𝒪(e(d) log d). Thus we refute the above twenty-year-old conjecture. We observe that no treasure hunt algorithm can beat cost Θ(e(d)) for all graphs and thus our algorithms are also almost optimal.
  This is a joint work with Sébastien Bouchard, Yoann Dieudonné and Andrzej Pelc that has been published at ICALP 2021.


• Arnaud de Mesmay, CNRS, Gipsa-lab, Grenoble, France
  Homotopy height: searching a planar graph with simple closed curves.
  The Homotopy Height problem consists informally in finding the best way to sweep a planar graph using a homotopy (a continuous deformation) of a single connected closed curve, i.e., we want the length of the longest intermediate curve to be minimised. Such optimal homotopies are relevant for a wide range of purposes, from very mathematical questions in Riemannian geometry to more practical applications such as similarity measures for trajectories.
  In this talk, we will survey what is known about this problem: the structure of the optimal solutions (simplicity, monotonicity), the complexity of solving it exactly and approximately, and some connections with grid minors.


• Martin Milanic, FAMNIT and IAM, Univ. of Primorska, Slovenia
  Tree decompositions with bounded independence number and their algorithmic applications.
  The independence number of a tree decomposition of a graph is the smallest integer k such that each bag induces a subgraph with independence number at most k. If a graph G is given together with a tree decomposition with bounded independence number, then the Maximum Weight Independent Set (MWIS) problem can be solved in polynomial time. Motivated by this observation, we consider six graph containment relations — the subgraph, topological minor, and minor relations, as well as their induced variants — and for each of them characterize the graphs H for which any graph excluding H with respect to the relation admits a tree decomposition with bounded independence number. Furthermore, using a variety of tools including SPQR trees and potential maximal cliques, we show how to obtain such tree decompositions efficiently.
  As an immediate consequence, we obtain that the MWIS problem can be solved in polynomial time in an infinite family of graph classes that properly contain the class of chordal graphs. More generally, our approach shows that the Maximum Weight Independent Packing problem, a common generalization of the MWIS and the Maximum Weight Induced Matching problems, can be solved in polynomial time in these graph classes.
  This is joint work with Clément Dallard and Kenny Štorgel.


• Nacim Oijid, LIRIS, Lyon, France
  Incidence, a scoring positional game
  In positional games, two players select turn by turn a vertex of a hypergraph. In the Maker-Breaker version, if Maker manages to take fully a hyperedge, he wins, otherwise, Breaker is the winner. In the Maker-Maker version, the first player to take a hyperedge wins. Therefore, in both cases the game stops as soon as Maker has taken a hyperedge. We here consider a scoring version of positional games where the game ends when all vertices are taken. The score is then defined as the number of hyperedges Maker manages to take. A Maker player will try to maximize this number, while Breaker aims to minimize it.
  In this work, we introduce Incidence, which consists in playing this game on a 2-regular hypergraph, i.e. an undirected graph. Two players, namely Alice and Bob, take turn by turn the vertices of a graph, and score the number of edges whose both end vertices are owned by the same player. In the Maker-Breaker version, Alice aims at maximizing the number of edges she owns, while Breaker aims at minimizing it. In the Maker-Maker version, both players try to maximize the number of edges they own.
  We prove that surprisingly, computing the score in the Maker-Breaker version is Pspace-complete whereas in the Maker-Maker version, the relative score can be solved in polynomial time. In addition, for the Maker-Breaker version, we give some bounds on the score with an Erdös-Selfridge like proof, and we prove that the score on paths and cycles can be computed in polynomial time.


• Christophe Paul, LIRMM, CNRS, Université Montpellier, France
  Mixed search games are monotone
  We consider the mixed search game against an agile and visible fugitive. This is the variant of the classic fugitive search game on graphs where searchers may be placed to (or removed from) the vertices or slide along edges. Moreover, the fugitive resides on the edges of the graph and can move at any time along unguarded paths. The \emph{mixed search number against an agile and visible fugitive} of a graph G, denoted avms(G), is the minimum number of searchers required to capture to fugitive in this graph searching variant. Our main result is that this graph searching variant is monotone in the sense that the number of searchers required for a successful search strategy does not increase if we restrict the search strategies to those that do not permit the fugitive to visit an already ``clean'' edge. This means that mixed search strategies against an agile and visible fugitive can be polynomially certified, and therefore that the problem of deciding for a graph G and an integer k whether avms(G) ≤ k is in NP. Our proof is based on the introduction of the notion of tight bramble, that serves as an obstruction for the corresponding search parameter. Our results imply that for a graph G, avms(G) is equal to the Cartesian tree product number of G, that is the minimum k for which G is a minor of the Cartesian product of a tree and a clique on k vertices.


• Nicola Santoro, Carleton Univ., Canada
  Cop and Robber Games in Temporal Graphs.
  The game of Cop & Robber is the well known two-players pursue-evation game played on a graph G in discrete rounds. In every round, each player, first the cop and then the robber, stays or moves to a neighbouring one; the cop wins iff both players are in the same node in some round. Observe that there is an obvious notion of ``time'' (the rounds) and that both players are fully aware that the graph does not change. What happens if the the topology of the graph changes in time, possibly at every round ?
  Such a situation would occur if the players were playing on a temporal graph. A temporal graph \G can be viewed as (an infinite) sequence of graphs, \G= G(0),G(1) ,..., where G(i) denotes the topology of \G at time i. Hence, in a Cop & Robber game on \G, in round i the players make their decisions and moves on G(i), and find themselves in G(i+1) in the next round. Knowing the changes beforehand, can the cop still find a winning strategy or the robber forever avoid capture ? Under what conditions \G is copwin ? This talk will address some of these questions and the issues that they raise, by examining and discussing the topic of Cop & Robber in temporal graphs, focusing in particular on periodic temporal graphs.
  This is based on joint work with Jean-Lou de Carufel, Paola Flocchini, and Frederic Simard.


• Milos Stojakovic, Univ of Novi Sad, Serbia
  Generalised Turan Game:
  We study a game motivated by the Generalised Turan Problem. Let H and F be graphs, and n an integer. Two players, Constructor and Blocker, alternately claim unclaimed edges of the complete graph on n vertices. Constructor is not allowed to claim a copy of F, and his goal is to maximise the number of claimed copies of H. Blocker plays without restriction, and his goal is to minimise the number of copies of H Constructor claimed. When both players play optimally the score of the game, denoted by gc(n, H, F), is the number of copies of H Constructor claimed. We look for the game score for several natural choices of H and F.
  This is joint work with Mate Vizer and Balazs Patkos.


• Sebastian Wiederrecht, LIRMM, Montpellier, France
  On tangles cops & robber in digraphs.
  In undirected graphs tangles yield an obstructions to small treewidth. This gives a way to decompose graphs into highly connected and structurally rich areas. Though there is much understanding on how such decompositions can be found and deployed in undirected graphs, the picture is more complicated for directed graphs.
  In this paper, we present a generalisation of tangles to directed graphs which we show to be dual to a width-parameter very close to DAG-width. In fact, we show that the width parameter we find through this approach correspondence to strategies in the (non-monotone) cops and robber reachability game. Hence our approach yields, for the first time, a width parameter for digraphs, together with a decomposition, capturing a non-monotone variant of DAG-width.


• Petra Wolf, Trier Univ., Germany
  Edge Periodic Temporal Graphs:
  Temporal graphs or time varying graphs are graphs that change over time, i.e., edges are only present in certain time steps or the time needed to traverse an edge changes. Temporal graphs are of great interest in the area of dynamic networks such as mobile ad hoc networks and vehicular networks modeling traffic load factors on a road network. In those networks, the topology naturally changes over time and temporal graphs are used to reflect this dynamic behavior. There are several settings of temporal graphs known in the literature: with continuous or discrete time steps, and with an explicit or implicit encoding of the sequence of temporal snapshot graphs. We are focusing on edge periodic temporal graphs. Here, the input is an underlying graph G = (V;E) together with a function   : E ! f0; 1g that maps each edge to a binary string indicating in which discrete time step the edge is present, i.e., e exists in a time step t   0 if and only if   (e)[t mod j  (e)j] = 1. As those binary strings can have independent length, the sequence of snapshot graphs of G only repeats after the least common multiple of the individual string lengths which can be exponential in the size of the input. We investigate among others the computational complexity of structural question such as:
  • (1) Does there exists a time step t in which the snapshot graph G(t) is H-minor free?
  • (2) Does there exists a time step t in which the snapshot graph G(t) contains H as a sub-graph?
  • (3) What is the shortest traversal time from a vertex s to a vertex t?
  We further perform a detailed analysis of the parameterized complexity of those problems and obtain some positive results.
  This talk is based on a joined work together with Emmanuel Arrighi, Niels Grüttemeier, Nils Morawietz, and Frank Sommer.