We give faster exponential-time randomised approximation algorithms for counting problems where polynomial-time approximation is unavailable and exact exponential-time counting remains expensive. For general n-vertex graphs, our independent-set counter runs in O^{∗}(1.1869ⁿ) time, improving the previous O^*(1.2041ⁿ) general-graph bound. For n-variable #2-SAT, we obtain an O^*(1.2373ⁿ)-time approximation algorithm, narrowly below Wahlström’s currently cited O^*(1.2377ⁿ) variable-parameter exact bound. The new algorithmic point is to take the square root after decomposition. For a single bounded unweighted self-reduction with f(x) positive leaves and recursion-compatible upper bound b(x), an enumerate-or-sample estimator gives an (ε,δ)-approximation in O^*(√{b(x)} ε^{-2}log(1/δ)) time. After preprocessing decomposes an input into many bounded cores, the combined estimator pays O^*(√{∑_i b_i(x_i)} ε^{-2} log (1/δ)) , rather than estimating the cores separately at cost ∑_i √{b_i(x_i)}. The same conversion improves the bases for counting maximal cliques, minimal separators, and perfect matchings in subcubic graphs. Bounded unweighted self-reductions provide the formal language; at the level of counting classes, the resulting unweighted formulation has the same Karp closure as TotP. With explicit recursion-tree access, the framework yields black-box quantum speed-ups.

Analyzing the worst-case running time of branching algorithms has traditionally focused more on designing complicated branching rules rather than developing better analysis methods for simple algorithms. In the mid-2000s, Fomin et al. (ACM 2009) introduced measure & conquer, an advanced general analysis method, sparking widespread adoption for obtaining tighter worst-case running time upper bound s for many fundamental NP-complete problems. Despite its significance, most subsequent work largely applied it without further methodological advancements and hence much potential in this direction remains untapped. Motivated by this, we present piecewise analysis , a new general method that analyzes the running time of branching algorithms. To showcase its potential, we reanalyze two almost 20-year-old algorithms by Fomin et al. (COCOON 2007), solving 4-Coloring and #3-Coloring , respectively. Our new analysis method improves the original running time upper bounds from O ( 1 . 7272 n ) and O ( 1 . 6262 n ) to O ( 1 . 7207 n ) and O ( 1 . 6225 n ) , respectively.

The peaceable queens problem asks to determine the maximum number such that there is a placement of white queens and black queens on an chessboard so that no queen can capture any queen of the opposite color. In this paper, we consider the peaceable queens problem and its variant on the toroidal board. For the regular board, we show that , for all sufficiently large . This improves on the bound of van Bommel and MacEachern [16]. For the toroidal board, we provide new upper and lower bounds. Somewhat surprisingly, our bounds show that there is a sharp contrast in behaviour between the odd torus and the even torus. Our lower bounds are given by explicit constructions. For the upper bounds, we formulate the problem as a non-linear optimization problem with at most 100 variables, regardless of the size of the board. We solve our non-linear program exactly using modern optimization software. We also provide a local search algorithm and a software implementation which converges very rapidly to solutions which appear optimal. Our algorithm is sufficiently robust that it works on both the regular and toroidal boards. For example, for the regular board, the algorithm quickly finds the so-called Ainley construction. Thus, our work provides some further evidence that the Ainley construction is indeed optimal. *Matthew Drescher was supported by the National Science Foundation under Grant #2127309 to the Computing Research Association for the CIFellows 2021 Project. This paper has been awarded the “Code and Data Available” and “Results Reproduced” badges as recognition that the author(s) have followed reproducibility principles. Code and data that allow readers to reproduce the results in this paper are available at https://doi.org/10.5281/zenodo.13787471. Participation in the ALENEX artifact evaluation phase was optional and performed at the request of the author(s).

The Euclidean Traveling Salesman Problem with Neighborhoods (ETSPN) is a well-studied problem in computational geometry and has a wealth of results. In this problem, given a set of geometric neighborhoods (or regions), the goal is to compute a shortest route that visits at least one point of each neighborhood. The problem is a generalization of the standard Euclidean TSP and hence is also NP-hard, even when the neighborhoods are disjoint unit disks or unit squares in the plane. A longstanding open problem on this topic is the existence of PTASes for ETSPN with unit disk (and unit square) neighborhoods. Prior to this work, the best-known approximation factor for unit disks is 6.75, and PTASes are only known for the special case where the unit disks/squares are of bounded depth, i.e., each point lies in at most a constant number of disks.

A 2-dimensional direction-length framework (G,p) consists of a multigraph G=(V;D,L) with realisation p:V→R2. The edges of G represent geometric constraints: edges in L have fixed length, and edges in D have fixed gradient. A direction-length framework (G,p) is globally rigid if every (G,q) which satisfies the same geometric constraints as (G,p) can be obtained from (G,p) by an isometry of the plane. We characterise global rigidity for the class of 2-dimensional direction-length frameworks (G,p) for which p is generic and the rigidity matroid of G is connected. Specifically, we show that such frameworks are globally rigid if and only if both D and L are non-empty, and every 2-separation of G is direction-balanced. This extends previous work by Jackson and Jordán (2010).

Abstract We consider the effect of symmetry on the rigidity of bar-joint frameworks, spherical frameworks and point-hyperplane frameworks in $${\mathbb {R}}^d$$ R d . In particular, for a graph $$G=(V,E)$$ G = ( V , E ) and a framework (G, p), we show that, under forced or incidental symmetry, infinitesimal rigidity for spherical frameworks with vertices in some subset $$X\subset V$$ X ⊂ V realised on the equator and point-hyperplane frameworks with the vertices in X representing hyperplanes are equivalent. We then show, again under forced or incidental symmetry, that infinitesimal rigidity properties under certain symmetry groups can be paired, or clustered, under inversion on the sphere so that infinitesimal rigidity with a given group is equivalent to infinitesimal rigidity under a paired group. The fundamental basic example is that mirror symmetric rigidity is equivalent to half-turn symmetric rigidity on the 2-sphere. With these results in hand we also deduce some combinatorial consequences for the rigidity of symmetric bar-joint and point-line frameworks.