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 give asymptotically exact values for the treewidth tw(G) of a random geometric graph G ∈ G(n, r) in [0, √n]². More precisely, let rc denote the threshold radius for the appearance of the giant component in G(n, r). We then show that for any constant 0 < r < rc, tw(G) = Θ(log n/log log n), and for c being sufficiently large, and r = r(n) ≥ c, tw(G) = Θ(r√n). Our proofs show that for the corresponding values of r the same asymptotic bounds also hold for the pathwidth and the treedepth of a random geometric graph. [ABSTRACT FROM AUTHOR]

After the number of vertices, Vertex Cover Number is the largest of the classical graph parameters and has more and more frequently been used as a separate parameter in parameterized problems, including problems that are not directly related to the Vertex Cover Number . Here we consider the treewidth and pathwidth problems parameterized by k , the size of a minimum vertex cover of the input graph. We show that the pathwidth and treewidth can be computed in O ∗ ( 3 k ) time. This complements recent polynomial kernel results for treewidth and pathwidth parameterized by the Vertex Cover Number . [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]

Research on the similarity of a graph to being a tree—called the treewidth of the graph—has seen an enormous rise within the last decade, but a practically fast algorithm for this task has been discovered only recently by Tamaki (ESA 2017). It is based on dynamic programming and makes use of the fact that the number of positive subinstances is typically substantially smaller than the number of all subinstances. Algorithms producing only such subinstances are called positive-instance driven (PID). The parameter treedepth has a similar story. It was popularized through the graph sparsity project and is theoretically well understood—but the first practical algorithm was discovered only recently by Trimble (IPEC 2020) and is based on the same paradigm. We give an alternative and unifying view on such algorithms from the perspective of the corresponding configuration graphs in certain two-player games. This results in a single algorithm that can compute a wide range of important graph parameters such as treewidth, pathwidth, and treedepth. We complement this algorithm with a novel randomized data structure that accelerates the enumeration of subproblems in positive-instance driven algorithms. [ABSTRACT FROM AUTHOR]