Abstracts

Kernelizing Temporal Exploration Problems

Petra Wolf, University of Bergen, Norway

Abstract: We study the kernelization of exploration problems on temporal graphs. A temporal graph consists of a finite sequence of snapshot graphs G=(G1,G2,…,GL) that share a common vertex set but might have different edge sets. 

The non-strict temporal exploration problem (NS-TEXP for short) introduced by Erlebach and Spooner, asks if a single agent can visit all vertices of a given temporal graph where the edges traversed by the agent are present in non-strict monotonous time steps, i.e., the agent can move along the edges of a snapshot graph with infinite speed. The exploration must at the latest be completed in the last snapshot graph. The optimization variant of this problem is the k-arb NS-TEXP problem, where the agent's task is to visit at least k vertices of the temporal graph. We show that under standard computational complexity assumptions, neither of the problems NS-TEXP nor k-arb NS-TEXP allow for polynomial kernels in the standard parameters: number of vertices n, lifetime L, number of vertices to visit k, and maximal number of connected components per time step γ; as well as in the combined parameters L+k, L+γ, and k+γ. On the way to establishing these lower bounds, we answer a couple of questions left open by Erlebach and Spooner. 

We also initiate the study of structural kernelization by identifying a new parameter of a temporal graph 

p(G)=∑Li=1(|E(Gi)|)−|V(G)|+1. Informally, this parameter measures how dynamic the temporal graph is. Our main algorithmic result is the construction of a polynomial (in p(G)) kernel for the more general Weighted k-arb NS-TEXP problem, where weights are assigned to the vertices and the task is to find a temporal walk of weight at least k.

Joint work with Emmanuel Arrighi, Fedor V. Fomin and Petr Golovach.



Exploring an Infinite Grid using Disoriented Robots

Stéphane Devismes. MIS, Université de Picardie, France. 

Abstract: In this talk, we address the problem of solving an infinite task using a few very weak computing mobile entities, so-called robot. More precisely, we consider the exploration of an infinite grid using a tiny swarm of such very weak luminous robots (no compass, no chirality, …) assuming synchronous settings.  Those robots are mobile and can perceive their surrounding within a fixed visibility range. Moreover, each of them is endowed with a light that can take different colors; the light color can be also perceived by robots in the surrounding. In this context, we look for optimal solutions w.r.t. the number of robots, the visibility range, and the number used colors.


Searching a tree with signals: routing mobile sensors for targets emitting radiation, chemicals or scents

Thomas Lidbetter. Rutgers Business School, UK.

Abstract: Adversarial search of a network for an immobile Hider (or target) was introduced and solved for rooted trees by Shmuel Gal in 1979. In this zero-sum game, a Hider picks a point to hide on the tree and a Searcher picks a unit speed trajectory starting at the root. The payoff (to the Hider) is the search time. In Gal’s model (and many subsequent investigations), the Searcher receives no additional information after the Hider chooses his location. In reality, the Searcher will often receive such locational information. For homeland security, mobile sensors on vehicles have been used to locate radioactive material stashed in an urban environment. In a military setting, mobile sensors can detect chemical signatures from land mines. In predator-prey search, the predator often has specially attuned senses (hearing for wolves, vision for eagles, smell for dogs, sonar for bats, pressure sensors for sharks) that may help it locate the prey. How can such noisy locational information be used by the Searcher to modify her route? We model such information as signals which indicate which of two branches of a binary tree should be searched first, where the signal has a known accuracy p < 1. Our solution calculates which branch (at every branch node) is favored, meaning it should always be searched first when the signal is in that direction. When the signal is in the other direction, we calculate the probability the signal should be followed. Compared to the optimal Hider strategy in the classic search game of Gal, the Hider’s optimal distribution for this model is more skewed towards leaf nodes that are further from the root.


Further results on the Hunters and Rabbit game through monotonicity

Foivos Fioravantes. Dept. Theoretical Computer Science, Fac. Information Tech., Czech Technical University.

Abstract: The Hunters and Rabbit game, introduced in [1] as a generalisation of the game studied in [2], is played on a graph G where the Hunter player shoots at k vertices in every round while the Rabbit player occupies an unknown vertex and, if it is not shot, must move to a neighbouring vertex after each round. The Rabbit player wins if they can ensure that their position is never shot. The Hunter player wins otherwise. The hunter number h(G) of a graph G is the minimum integer k such that the Hunter player has a winning strategy (i.e., allowing them to win whatever be the strategy of the Rabbit player). This game has been studied in several graph classes, in particular in bipartite graphs (grids, trees, hypercubes...), but the computational complexity of computing h(G) remains open in general graphs and even in more restricted graph classes such as trees. To progress further in this study, we propose a notion of monotonicity (a well-studied and useful property in classical pursuit-evasion games such as Graph Searching games) for the \textsc{Hunters and Rabbit} game imposing that, roughly, a vertex that has already been shot ``must not host the rabbit anymore''. This allows us to obtain new results in various graph classes.

More precisely, let the monotone hunter number mh(G) of a graph G be the minimum integer k such that the Hunter player has a monotone winning strategy. We show that pw(G) <= mh(G) <= pw(G)+1 for any graph G with pathwidth pw(G), which implies that computing mh(G), or even approximating mh(G) up to an additive constant, is NP-hard. Then, we show that mh(G) can be computed in polynomial time in split graphs, interval graphs, cographs and trees. These results go through structural characterisations which allow us to relate the monotone hunter number with the pathwidth in some of these graph classes. In all cases, this allows us to specify the hunter number or to show that there may be an arbitrary gap between h and mh, i.e., that monotonicity does not help. In particular, we show that, for every k>= 3, there exists a tree T with h(T)=2 and mh(T)=k. We conclude by proving that computing h (resp., mh) is FPT~parameterised by the minimum size of a vertex cover.

Joint work with Thomas Dissaux, Harmender Gahlawat and Nicolas Nisse

[1] T. V. Abramovskaya, F. V. Fomin, P. A. Golovach, and M. Pilipczuk. How to hunt an invisible rabbit on a graph. European Journal of Combinatorics, 52:12–26, 2016.

[2] J. R. Britnell and M. Wildon. Finding a princess in a palace: a pursuit-evasion problem. The Electronic Journal of Combinatorics, 20(1):25, 2013.


A graph searching game for block tree-depth 

Archontia Giannopoulou, National and Kapodistrian University of Athens

Greece 

Abstract: Block elimination distance is a parameter on graphs that measures the distance of the biconnected components of a graph from a given class of graphs.  When the indicated graph class is the class of edgeless graphs, we call the parameter  block treedepth. We show that block treedepth is equivalent to the minimum number of colors needed to color a graph such that every biconnected subgraph has a vertex of unique color. Additionally, we introduce a special kind of non-proper edge coloring that can serve as an alternative for block treedepth, called cycle edge ranking. Moreover, we make a connection between block treedepth and graph searching games by introducing two versions of the cops and robbers game that can be used to calculate the block treedepth of a graph. Finally, we argue that block treedepth has a polynomial kernel when parameterized by the vertex cover number.


Parameterized analysis of the Cops and Robber game 

Harmender Gahlawat. Ben-Gurion University of Negev, Israel

Abstract: Pursuit-evasion games have been intensively studied for several decades due to their numerous applications in artificial intelligence, robot motion planning, database theory, distributed computing, and algorithmic theory. Cops and Robber (CnR) is one of the most well-studied pursuit-evasion games played on graphs, where multiple cops pursue a single  robber. The aim is to compute the cop number of a graph, k, which is the minimum number of cops that ensures the capture of the robber. 

In this talk, we will consider the parameterized complexity of CnR wrt structural parameters of the input graph since CnR is W[2]-hard parameterized by k [Fomin et al., TCS, 2010].  We begin with the vertex cover number (vcn). We prove that CnR parameterized by vcn is FPT by designing an exponential kernel. We complement this result by showing that it is unlikely for CnR parameterized by vcn to admit a polynomial compression. We extend our exponential kernels to the parameters cluster vertex deletion number and deletion to stars number, and design a linear vertex kernel for neighborhood diversity.  We also prove that the cop number of a graph is not bounded by any computable function of twin-width of the input graph and CnR is paraNP-hard parameterized by twin-width. Additionally, we extend all of our results to several well-studied variations of CnR. These results are based on a joint work with Meirav Zehavi.


Tight (Double) Exponential Bounds for NP-Complete Problems: Treewidth and Vertex Cover Parameterizations

Fionn Mc Inerney, TU Wien, Austria

Abstract: Treewidth serves as an important parameter that yields tractability for a wide class of problems. For example, graph problems expressible in Monadic Second Order (MSO) logic and \textsc{Quantified SAT} or, more generally, \textsc{Quantified CSP}, are fixed-parameter tractable parameterized by the treewidth of the input's (primal) graph plus the length of the MSO-formula [Courcelle, Information & Computation 1990]  and the quantifier rank [Chen, ECAI 2004], respectively.  The algorithms generated by these (meta-)results have running times whose dependence on treewidth is  a tower of exponents. A conditional lower bound by Fichte, Hecher, and Pfandler [LICS 2020] shows that, for \textsc{Quantified SAT}, the height of this tower is equal to the number of quantifier alternations. That is, the height of the tower must increase with every extra quantifier alternation. These types of lower bounds, which show that at least double-exponential factors in the running time are necessary, exhibit the extraordinary level of computational hardness for such problems and are rare in the current literature: there are only a handful of such lower bounds (for treewidth and vertex cover parameterizations) and all of them are for problems that are either $\Sigma_2^p$-, $\Sigma_3^p$- or #NP-complete.

Our results demonstrate, for the first time, that it is not necessary to go higher up in the polynomial hierarchy to achieve double-exponential lower bounds: we derive double-exponential lower bounds in the treewidth (tw) and the vertex cover number (vc), for natural, important, and well-studied metric-based \NP-complete graph problems. More specifically, we study Metric Dimension, Strong Metric Dimension, and Geodetic Set. We prove that these problems do not admit $2^{2^{o(\textsf{tw})}} \cdot n^{\mathcal{O}(1)}$-time algorithms, even on bounded diameter graphs, unless the ETH fails (here, n is the number of vertices in the graph). In fact, for Strong Metric Dimension, the double-exponential lower bound holds even for the vertex cover number. Such a phenomenon is not possible for Metric Dimension and Geodetic Set as they admit simple $2^{\mathcal{O}(\textsf{vc}^2)} \cdot n^{\mathcal{O}(1)}$ algorithms. We show that, unless the ETH fails, they do not admit $2^{o(\textsf{vc}^2)}\cdot n^{\mathcal{O}(1)}$ algorithms, thereby adding to the sparse list of problems that admit such lower bounds. We note that our lower bounds for the vertex cover parameterizations also yield lower bounds on the vertex-kernel sizes of these problems. We further complement all our lower bounds with matching (and sometimes non-trivial) upper bounds. 

On the technical side, our lower bounds use a novel, yet simple, gadget based on Sperner families of sets. We believe that the techniques introduced in this paper could also be applicable to other natural metric-based graph problems that are NP-complete.


Inverting Ramsey: from class properties to graph parameters

Martin Milanic,  University of Primorska in Koper, Slovenia

Abstract: Consider any graph parameter ρ defined as the maximum or the minimum cardinality of a set of vertices of the graph satisfying a certain property associated with the parameter. Replacing in the above definition the cardinality of a set with the independence number of the corresponding induced subgraph, we obtain the independence variant of the parameter, denoted by α-ρ. This framework captures, for example:

Given a parameter ρ, we say that a graph class has clique-bounded ρ if ρ is bounded from above by a function of the clique number, that is, the only reason for large ρ is the presence of a large clique. Ramsey's theorem implies that in any hereditary graph class in which the independence variant of ρ is bounded, the class has clique-bounded ρ. When does this implication reverse? That is, for which graph parameters ρ is bounded α-ρ not only a sufficient but also a necessary condition for clique-bounded ρ? We will present some results regarding the above question. 

Based on joint work in progress with Clément Dallard, Vadim Lozin, Kenny Štorgel, and Viktor Zamaraev.


From binary search  through games to graphs

Przemsyław Gordinowicz, Łódź University of Technology, Poland

Abstract: The talk focuses on some generalisations of binary search in a multidimensional or graph environment. They can be viewed as a game between the Adversary, who hides the target in this environment and responds to the Algorithm, which in turn, tries to find the target minimizing the number of queries.

We will provide some bounds for the number of queries, including bounds for random graphs and discuss the complexity of the optimal strategy for the Algorithm.

The talk is based on joint works with Dariusz Dereniowski (Gdańsk), Paweł Prałat (Toronto) and Karolina Wróbel (Łódź).       

[1] D. Dereniowski, P. Gordinowicz, P. Prałat, Edge and Pair Queries-Random Graphs and Complexity, Electronic Journal of Combinatorics, 30 (2023), P2.34.

[2] D. Dereniowski, P. Gordinowicz, K. Wróbel, Goal seek for a discrete multi-criteria problem, in preparation.  


On Copnumbers of Periodic Temporal Graphs

Frédéric Simard, Univ. of Ottawa, Canada

Abstract: A periodic temporal graph G = (G0,G1, . . . ,Gp−1)∗ is an infinite periodic sequence of graphs Gi = (V,Ei) where G = (V, ∪iEi) is called the footprint. Recently, the arena where the Cops and Robber game is played has been extended from a graph to a periodic graph; in this case, the copnumber is also the minimum number of cops sufficient for capturing the robber. We study the connections and distinctions between the copnumber c(G) of a periodic graph G and the copnumber c(G) of a graph G (e.g. the footprint), and establish several facts. For instance, we show that the smallest periodic graph with c(G) = 3 has at most 8 nodes; in contrast, the smallest graph G with c(G) = 3 has 10 nodes. On the other hand, we provide an example of a periodic graph with c(G) = 3 whose footprint G is outerplanar and thus c(G) = 2. Based on these results, we derive upper bounds on the copnumber of a periodic graph from properties of its footprint, such as its treewidth.

Joint work with Jean-Lou De Carufel, Paola Flocchini, Nicola Santoro

Generalizations of binary search to graphs

Dariusz Dereniowski. Gdansk University of Technology, Poland.

Abstract: There exist several graph searching problems in which a static target needs to be located by asking queries. Some of them generalize binary search and the goal of this talk is to discuss them, outline selected results, connections to other problems and suggest some open questions.


Parameterized Complexity of Broadcasting in Graphs

Petr Golovach. University of Bergen, Norway


Robbers and Cops with Imperfect Information (on Trees)

Dietmar Berwanger, LMF, CNRS, France


Abstract: We consider graph-searching games where the searcher has imperfect information about the position of the fugitive. Our long-term goal is to measure the alignment between the information structure and the move structure. In the talk, we discuss the setup in terms of reachability games and present some preliminary insights for games on trees.

This is joint work with Patricia Bouyer and Fatemeh


Searching and serving complete geometric graphs

Jan Kratochvil, Charles university in Prague, Univerzita Karlova