Search for: All records

Given a geometric domain P, visibility-based search problems seek routes for one or more mobile agents ("watchmen") to move within P in order to be able to see a portion (or all) of P, while optimizing objectives, such as the length(s) of the route(s), the size (e.g., area or volume) of the portion seen, the probability of detecting a target distributed within P according to a prior distribution, etc. The classic watchman route problem seeks a shortest route for an observer, with omnidirectional vision, to see all of P. In this paper we study bicriteria optimization problems for a single mobile agent within a polygonal domain P in the plane, with the criteria of route length and area seen. Specifically, we address the problem of computing a minimum length route that sees at least a specified area of P (minimum length, for a given area quota). We also study the problem of computing a length-constrained route that sees as much area as possible. We provide hardness results and approximation algorithms. In particular, for a simple polygon P we provide the first fully polynomial-time approximation scheme for the problem of computing a shortest route seeing an area quota, as well as a (slightly more efficient) polynomial dual approximation. We also consider polygonal domains P (with holes) and the special case of a planar domain consisting of a union of lines. Our results yield the first approximation algorithms for computing a time-optimal search route in P to guarantee some specified probability of detection of a static target within P, randomly distributed in P according to a given prior distribution. 

In this paper, we show that computing canonical labelings of graphs of bounded rank-width is in TC². Our approach builds on the framework of Köbler & Verbitsky (CSR 2008), who established the analogous result for graphs of bounded treewidth. Here, we use the framework of Grohe & Neuen (ACM Trans. Comput. Log., 2023) to enumerate separators via split-pairs and flip functions. In order to control the depth of our circuit, we leverage the fact that any graph of rank-width k admits a rank decomposition of width ≤ 2k and height O(log n) (Courcelle & Kanté, WG 2007). This allows us to utilize an idea from Wagner (CSR 2011) of tracking the depth of the recursion in our computation. Furthermore, after splitting the graph into connected components, it is necessary to decide isomorphism of said components in TC¹. To this end, we extend the work of Grohe & Neuen (ibid.) to show that the (6k+3)-dimensional Weisfeiler-Leman (WL) algorithm can identify graphs of rank-width k using only O(log n) rounds. As a consequence, we obtain that graphs of bounded rank-width are identified by FO + C formulas with 6k+4 variables and quantifier depth O(log n). Prior to this paper, isomorphism testing for graphs of bounded rank-width was not known to be in NC. 

Genome rearrangement is a common model for molecular evolution. In this paper, we consider the Pairwise Rearrangement problem, which takes as input two genomes and asks for the number of minimum-length sequences of permissible operations transforming the first genome into the second. In the Single Cut-and-Join model (Bergeron, Medvedev, & Stoye, J. Comput. Biol. 2010), Pairwise Rearrangement is #P-complete (Bailey, et. al., COCOON 2023), which implies that exact sampling is intractable. In order to cope with this intractability, we investigate the parameterized complexity of this problem. We exhibit a fixed-parameter tractable algorithm with respect to the number of components in the adjacency graph that are not cycles of length 2 or paths of length 1. As a consequence, we obtain that Pairwise Rearrangement in the Single Cut-and-Join model is fixed-parameter tractable by distance. Our results suggest that the number of nontrivial components in the adjacency graph serves as the key obstacle for efficient sampling. 

Given a set P ⊂ ℝ^d of n points, with diameter Δ, and a parameter δ ∈ (0,1), it is known that there is a partition of P into sets P_1, …, P_t, each of size O(1/δ²), such that their convex hulls all intersect a common ball of radius δΔ. We prove that a random partition, with a simple alteration step, yields the desired partition, resulting in a (randomized) linear time algorithm (i.e., O(dn)). We also provide a deterministic algorithm with running time O(dn log n). Previous proofs were either existential (i.e., at least exponential time), or required much bigger sets. In addition, the algorithm and its proof of correctness are significantly simpler than previous work, and the constants are slightly better. We also include a number of applications and extensions using the same central ideas. For example, we provide a linear time algorithm for computing a "fuzzy" centerpoint, and prove a no-dimensional weak ε-net theorem with an improved constant.