Abstracts

Tentative list of talks (to be updated)

Speaker: Anthony Bonato
Title: Graph Searching Games and Probabilistic Methods
Abstract: The intersection of graph searching and probabilistic methods is a new topic within graph theory, with applications to graph searching problems such as the game of Cops and Robbers and its many variants, Firefighting, graph
burning, and acquaintance time. Graph searching games may be played on random structures such as binomial random graphs, random regular graphs or random geometric graphs. Probabilistic methods may also be used to understand the properties of games played on deterministic structures. A third and new approach is where randomness figures into the rules of the game, such as in the game of Zombies and Survivors. We give a broad survey of graph searching and probabilistic methods, highlighting the themes and trends in this emerging area. The talk is based on my upcoming book (with the same title) co-authored with Pawel Pralat (to be published by CRC Press in late 2017).

Speaker: Nancy Clarke
Title: Cops and Robbers with Gangs
Abstract: A variation of the Cops and Robber game is considered in which the robber side consists of  “gangs” of robbers that can win by attacking a cop. We present results for gangs of two robbers on graphs of small girth. This is joint work with A. Sanaei.

Speaker: Dariusz Dereniowski
Title: Graph Exploration Algorithms
Abstract: The aim of this talk is to survey some recent results and models of graph exploration. The problem is usually formulated in such a way that a single or multiple mobile agents are placed in a graph and their task is to visit all of its vertices. The goal is to design an algorithm that dictates movements of agents. Typical optimization criteria involve the number of agents or exploration time.

Speaker: Michael Fellows
Title: Searching for a Hidden Flaw: Some Results on Minesweeper of 3-Coloring
Abstract: In the folklore of puzzle-type computer game design there is a fruitful approach based on handles(H) + NP-hard problems(X). A handle is the interaction dynamic or basic interaction script. Examples include the on-line-with-a-wave handle ("Tetris") and the  hidden-solution-with-a-flaw handle ("Minesweeper"). This approach poses many interesting and unexplored algorithms and complexity challenges. The talk will briefly survey the approach and report on some preliminary results concerning the H+X: Minesweeper of 3-Coloring. The talk is based on unpublished work with Vladimir Estivill-Castro and Frances Rosamond.

Speaker: Petr Golovach
Title: How to hunt an invisible rabbit on a graph
Abstract:  We investigate Hunters & Rabbit game, where a set of hunters tries to catch an invisible rabbit that slides along the edges of a graph. We show that the minimum number of hunters required to win on an (n\times m)-grid is \lfloor min{n,m}/2 \rfloor+1. We also show that the extremal value of this number on n-vertex trees is between Omega(log n/loglog n) and O(log n).
The talk is based on the paper: Tatjana V. Abramovskaya, Fedor V. Fomin, Petr A. Golovach, Michal Pilipczuk. How to hunt an invisible rabbit on a graph. Eur. J. Comb. 52: 12-26 (2016)

Speaker: Przemysław Gordinowicz
Title: Those Magnificent Blind Cops in Their Flying Machines with Sonars
Abstract: Inspired by the localisation problems in wireless networks we study the variation of Cops and Robber model, in which helicopter cops plays against a slow, but invisible robber. Instead, cops receive the information of a distance from robber's current position to vertices occupied by the cops. The goal for cops is to localise the robber. This model, restricted to one cop, was introduced by Seager (with slightly different rules) and then by Carraher, Choi, Delcourt, Erickson and West. Here we investigate the cop number in this model providing some bounds of it, developed from other graph parameters and giving examples of graph classes on which it is, surprisingly, unbounded (incl. planar graphs).
The talk is based on still being developed work with B. Bosek, J. Grytczuk, P. Naroski, J. Sokół and M. Śleszyńska-Nowak.

Speaker: Akitoshi Kawamura
Title: Open problems on optimal patrolling
Abstract:  Ιn patrolling problems, several mobile agents move on a graph (with edge lengths) and try to cooperate so that every specified point on the graph is (perpetually) visited sufficiently often (that is, no point should be left unattended for a long time).  Problems of this kind are studied with various motivations and in various forms: the agents may have the same or different speeds; the underlying graph may be a path, a cycle, a tree, or more general graphs; the points to be visited may be just the vertices or all points on the edges. Finding an optimal patrolling schedule is not straightforward, even in the simplest settings.  I will introduce some results and open questions about properties of and algorithms for optimal patrolling.

Speaker: Athanasios Kehagias
Title: Games of selfish cops and robbers
Abstract: I examine variants of the cops and robber game in which is two cops are independently trying to catch a robber. I first consider the  variant in which the robber is mobile but does not actively attempt to  evade capture. This results in a two-player, zero-sum game between the two cops. I consider two versions of the game: in the first, "sequential" version the players move one after the other and in the second, "concurrent" version they move simultaneously. For both versions I prove that the game possesses a minimax value and optimal strategies which attain the value. I also provide algorithms for the computation of these quantities. I then consider the variant in which the robber actively attempts to evade capture. This results in a three-player, non-zero-sum game. I only consider the "sequential" version of the game, I prove that the game possesses a Nash equilibrium and optimal strategies and provide an algorithm for the computation of these quantities.

Speaker: David Kirkpatrick
Title: Minimizing uncertainty in the proximity of moving agents
Abstract: Search problems are conventionally understood in terms of minimizing uncertainty in the location of one or more agents (perhaps moving in an adversarial fashion), using some form of spatial queries. We consider, and encourage further consideration of, a natural  modification in which the goal is to reduce uncertainty, attributable to unmonitored motion,  concerning the proximity, rather than absolute location, of a collection of moving agents. For example, imagine a collection of point agents moving in a graph (or some subset of one-, or higher, dimensional Euclidean space) each with some (known, but possibly different) upper bound on their speed.  If we know, by means of an individual location query, the precise location of an individual agent at a particular time, then its location, until the time that it is next queried, lies in  a steadily-expanding region of uncertainty. Motivated by the fact that resource demands are often commensurate with congestion (e.g. bandwidth allocation), we consider the problem of minimizing measures of potential congestion—maximum local congestion, over all agent configurations consistent with the current uncertainty of the collection—using individual queries that are restricted to one query per unit of time. Our focus to date has been on the degree of the uncertainty regions (defined as the maximum, over all agents a, of the number of uncertainty regions that intersect the uncertainty region of a), a natural measure of worst-case congestion, for point agents moving continuously in one-, or higher, dimensional Euclidean space. The goal is to minimize this degree continuously. Competitive query strategies are described in terms of a notion of intrinsic degree (the minimum degree achievable by any query strategy, even one that knows the trajectories of all agents). Only partially studied to date are analogous questions for agents moving in a graph. (Based on joint work with Daniel Busto, and Will Evans)

Speaker: Amos Korman
Title: From Ants to Query Complexity
Abstract: I will talk about my recent adventures with ants. Together with biologists we study P. longicornis ants as they collaboratively transport a large food item to their nest. This collective navigation process is guided by pheromones which are laid by individual ants. Using a new methodology to detect scent marks, we identify a new kind of ant trail characterized by very short and dynamic pheromone markings and highly stochastic navigation response to them. We argue that such a trail can be highly beneficial in conditions in which knowledge of individual ants regarding the underlying topological structure is unreliable. This gives rise to a new theoretical search model under unreliable guiding instructions, which is of independent computational interest. To illustrate the model, imagine driving a car in an unknown country that is in the aftermath of a major hurricane which has randomly flipped a certain small fraction of the road-signs. Under such conditions of unreliability, how can you still reach your destination fast? I will discuss the limits of unreliability that allow for efficient navigation. In trees, for example, there is a phase transition phenomenon that occurs roughly around 1/sqrt{D}. That is, if noise is above this threshold then any algorithm cannot avoid finding the target in exponential time (in the original distance), while below the threshold we identify an optimal, almost linear, walking algorithm. Finally, I will discuss algorithms that under such a noisy model aim to minimize the number of queries to find a target (rather than the number of moves).

Speaker: Tomáš Gavenčiak
Title: Cop number of string graphs
Abstract: We show that for intersection graphs of curves on a surface, a finite number of cops can always catch the robber (in the Nowakowski-Quilliot Cops and Robber pursuit game). The talk is based on Gavenčiak, Gordinowicz, Jelinek, Klavik, Kratochvil: Cops and Robbers on String Graphs, ISAAC 2015.

Speaker: Thomas Lidbetter
Title: Using a best response oracle to solve search games on graphs
Abstract: We consider zero-sum search games between a Searcher and Hider.  Such games are often played on a graph, where the Hider’s strategy set is the set of vertices of the graph but the Searcher’s strategy set is much larger and may correspond to the order in which she visits the vertices.  In this case, conventional linear programming methods are not efficient for solving the game (that is, finding optimal mixed strategies and the value of the game).  We assume there is an oracle that, for any fixed mixed (randomized) strategy of the Hider, outputs a best response strategy for the Searcher (or an “approximate” best response). Under this assumption, we give efficient algorithms for solving or “approximately” solving the game, and we give many examples of games for which this approach is useful. This is joint work with Lisa Hellerstein

Speaker: Minko Markov
Title: The sweeping of planar shapes: a geometric analogue of graph searching
Abstract:  The presentation is based on the paper "Decontaminating Planar Regions by Sweeping with Barrier Curves" by Karaivanov, Markov, Snoeyink, and Vassilev.  A novel concept of sweeping a planar shape by the coordinated movement of barriers is introduced.  The corresponding measure, the sweepwidth, is proven to be NP-hard even for orthogonal polygons.  It is still an open question how to prove there always exists a sweep that both avoids recontamination and is optimal.  We present a technique for proving lower bounds on the sweepwidth of planar shapes that is a weighted analogue of a technique for proving lower bounds on the vertex separation of graphs.

Speaker: Katerina Papadaki
Title:  Patrolling continuous networks
Abstract: We define a zero sum game between a patroller who wants to protect a continuous network and an attacker who wants to disrupt the network. The patroller picks a walk on a network that she periodically repeats and the attacker picks a point on the network and a time to attack. The attack is successful if the attacker spends time r at the attack point uninterrupted by the patroller, otherwise the attack is intercepted. We present the value and optimal mixed strategies for various types of networks.

Speaker: Konstantinos Panagiotou
Title: Optimal Strategies for Weighted Search Problems
Abstract: Searching for a hidden target is an important algorithmic problem. We study the general setting in which a number of targets, each with a certain weight, are hidden in a star-like environment that consists of m infinite, concurrent rays, with a common origin. A mobile searcher, initially located at the origin, explores this environment in order to locate a set of targets
whose aggregate weight is at least a given value W. The cost of the search strategy is defined as the total distance traversed by the searcher, and its performance is evaluated by the worst-case
ratio of the cost incurred by the searcher over the cost of an on optimal, offline strategy with access to the whole instance. This setting is a broad generalization of well-studied problems in search theory; namely, it generalizes the setting in which either a single target is sought, and the case in which all targets have unit weights.
We consider two models depending on the amount of information allowed to the offline algorithm. In the first model, which is the canonical model in search theory, the offline algorithm
has complete information. Here, we propose and analyze a strategy that attains optimal performance. In the second model, the offline algorithm has only partial information of the problem instance (i.e., the target locations). Here, we present a strategy of asymptotically optimal performance that is logarithmically related to m. This is in stark contrast to the full information model in which a linear dependency is unavoidable.

Speaker: Christophe Paul
Title: Connected search against a lazy robber
Abstract: The node search game against a lazy/agile (invisible) robber has been introduced as a search-game analogue of the graph parameters of treewidth/pathwidth. In the “connected” variants of the above two games, we additionally demand that, at each moment of the search, the “clean” territories are connected. The connected search game against an agile and invisible robber has been extensively examined. The monotone variant (where we also demand that the clean territories are progressively increasing) of this game, corresponds to the graph parameter of connected pathwidth and has been shown that its value cannot be more than the double (asymptotically) of its non-connected counterpart. This implied that the “price of connectivity” is bounded by 2 for the case of an agile robber. In this paper we initiate the study of the connected variant of this search game where the robber is lazy, in the sense that he/she moves only when the searchers strategy threatens the location that he/she currently occupies. We introduce two alternative graph-theoretical formulations of its monotone variant, one in terms of (connected) layouts and one on terms of (connected) tree decompositions, leading to the graph parameter of connected treewidth. For this “lazy-robber” variant we prove that there is no bound in the price of connectivity, which comes in contrast to the case of an agile robber. We also observe that the corresponding parameter, i.e. connected treewidth, is closed under contractions and we study the contraction-obstruction set class of the class of graphs with connected treewidth at most k. It follows that this set is infinite for every k ≥ 2. We also provide a complete characterisation for the case where k = 2. This is joint work with Isolde Adler and Dimitrios M. Thilikos.

Speaker: Pascal Schweitzer
Title: Online graph exploration
Abstract: We study the problem of exploring an unknown undirected connected graph. Beginning in some start vertex, a searcher must visit each node of the graph by traversing edges. Upon visiting a vertex for the first time, the searcher learns all incident edges and their respective traversal costs. The goal is to find a tour of minimum total cost. Kalyanasundaram and Pruhs proposed a sophisticated generalization of a Depth First Search that is 16-competitive on planar graphs. The description of the algorithm is not particular to planar graphs. I will explain some results for general graphs from joint work with Nicole Megow and Kurt Mehlhorn and highlight, however, that the main problem is unresolved to-date.

Speaker: Konstantinos Stavropoulos
Title: Cops, Robber and Medianwidth Parameters
Abstract:  We present a generalisation of the classical Cops and Robber game where the robber plays not against one, but many teams of cops simultaneously. This is motivated as a game characterisation for medianwidth parameters, which correspond to high-dimensional generalisations of treewidth and pathwidth.