Search

The localization game is a pursuit-evasion game analogous to Cops and Robbers, where the robber is invisible and the cops send distance probes in an attempt to identify the location of the robber. We present a novel graph parameter called the localization capture time, which measures how long the localization game lasts assuming optimal play. We conjecture that the localization capture time is linear in the order of the graph, and show that the conjecture holds for graph families such as trees and interval graphs. We study bounds on the localization capture time for trees and its monotone property on induced subgraphs of trees and more general graphs. We give upper bounds for the localization capture time on the incidence graphs of projective planes. We finish with new bounds on the localization number and localization capture time using treewidth. [ABSTRACT FROM AUTHOR]

We study the combinatorial FIFO Stack-Up problem. In the delivery industry, bins have to be moved from conveyor belts onto pallets. Given is a list Q of k sequences of labeled bins and a positive integer p. The goal is to palletize the bins by iteratively removing the first bin of one of the k sequences and putting it onto a pallet located at one of p stack-up places. Each of these pallets has to contain bins of only one label, bins of different labels have to be placed on different pallets. After all bins of one label have been removed from the given sequences, the corresponding stack-up place becomes available for a pallet of bins of another label. The FIFO Stack-Up problem asks whether such a processing is possible. The FIFO Stack-Up problem is known to be NP-complete even if the sequences of Q contain together at most c Q = 6 bins per pallet. This implies that the problem is also hard if all bins of every pallet are distributed to at most d Q = 6 sequences. In this paper we strengthen the hardness to the cases c Q = 5 and d Q = 3. We also show the hardness for the practical case where the number of sequences is smaller than the number of pallets, and we point out differences to related problems like 3D Bin Packing and Train Marshalling. [ABSTRACT FROM AUTHOR]

A connected path decomposition of a simple graph G is a path decomposition (X 1 , ... , X l) such that the subgraph of G induced by X 1 ∪ ⋯ ∪ X i is connected for each i ∈ { 1 , ... , l }. The connected pathwidth of G is then the minimum width over all connected path decompositions of G. We prove that for each fixed k , the connected pathwidth of any input graph can be computed in polynomial-time. This answers an open question raised by Fedor V. Fomin during the GRASTA 2017 workshop, since connected pathwidth is equivalent to the connected (monotone) node search game. [ABSTRACT FROM AUTHOR]

We consider the complexity of the firefighter problem where a budget of b ≥ 1 firefighters are available at each time step. This problem is known to be NP-complete even on trees of degree at most three and b = 1 [14] and on trees of bounded degree ( b + 3 ) for any fixed b ≥ 2 [4] . In this paper we provide further insight into the complexity landscape of the problem by showing a complexity dichotomy result with respect to the parameters pathwidth and maximum degree of the input graph. More precisely, first, we prove that the problem is NP-complete even on trees of pathwidth at most three for any b ≥ 1 . Then we show that the problem turns out to be fixed parameter-tractable with respect to the combined parameter “pathwidth” and “maximum degree” of the input graph. Finally, we show that the problem remains NP-complete on very dense graphs, namely co-bipartite graphs, but is fixed-parameter tractable with respect to the parameter “cluster vertex deletion”. [ABSTRACT FROM AUTHOR]

Non-deterministic graph searching was introduced by Fomin et al. to provide a unified approach for pathwidth, treewidth, and their interpretations in terms of graph searching games. Given q ≥ 0 , the q -limited search number, s q ( G ) , of a graph G is the smallest number of searchers required to capture an invisible fugitive in G , when the searchers are allowed to know the position of the fugitive at most q times. The search parameter s 0 ( G ) corresponds to the pathwidth of a graph G , and s ∞ ( G ) to its treewidth. Determining s q ( G ) is NP-complete for any fixed q ≥ 0 in general graphs and s 0 ( T ) can be computed in linear time in trees, however the complexity of the problem on trees has been unknown for any q > 0 . We introduce a new variant of graph searching called restricted non-deterministic. The corresponding parameter is denoted by rs q and is shown to be equal to the non-deterministic graph searching parameter s q for q = 0 , 1 , and at most twice s q for any q ≥ 2 (for any graph G ). Our main result is a polynomial time algorithm that computes rs q ( T ) for any tree T and any q ≥ 0 . This provides a 2-approximation of s q ( T ) for any tree T , and shows that the decision problem associated to s 1 is polynomial in the class of trees. Our proofs are based on a new decomposition technique for trees which might be of independent interest. [ABSTRACT FROM AUTHOR]

Given a connected outerplanar graph G of pathwidth p , we give an algorithm to add edges to G to get a supergraph of G , which is 2-vertex-connected, outerplanar and of pathwidth O ( p ) . This settles an open problem raised by Biedl [1] , in the context of computing minimum height planar straight line drawings of outerplanar graphs, with their vertices placed on a two-dimensional grid. In conjunction with the result of this paper, the constant factor approximation algorithm for this problem obtained by Biedl [1] for 2-vertex-connected outerplanar graphs will work for all outer planar graphs. [ABSTRACT FROM AUTHOR]

Abstract: The problems of (classical) searching and connected searching of weighted trees are known to be computationally hard. In this work we give a polynomial-time 3-approximation algorithm that finds a connected search strategy of a given weighted tree. This in particular yields constant factor approximation algorithms for the (non-connected) classical searching problems and for the weighted pathwidth problem for this class of graphs. [Copyright &y& Elsevier]