Bart M. P. Jansen

Bart M. P. Jansen, Ruben F. A. Verhaegh

For a fixed set $\mathcal{F}$ of Boolean constraint types, a MinCSP$(\mathcal{F})$-instance consists of a formula $F$ that applies $m$ constraints from $\mathcal{F}$ to a set of $n$ Boolean variables. The goal is to remove a minimum subset of constraint applications from $F$ to make the remaining formula satisfiable. Previous work characterized how the choice of $\mathcal{F}$ affects its polynomial-time solvability and approximability. We extend a recently introduced preprocessing framework for graph problems to the problem above. Rephrased in the context of CSPs, this framework defines a constraint application from a given formula $F$ as $c$-essential if it is contained in all $c$-approximate solutions to $F$. Being able to efficiently detect these essential parts of a solution reduces the search space of any follow-up FPT algorithms parameterized by the solution size and yields an immediate asymptotic improvement to the runtime of such algorithms. In this work, we present a dichotomy theorem that distinguishes constraint sets $\mathcal{F}$ for which $c_\mathcal{F}$-essential constraint applications can be detected efficiently for some $c_{\mathcal{F}} \in \mathcal{O}(1)$, from those for which this task is intractable under established complexity-theoretic conjectures. Our results show that for any set $\mathcal{F}$ of bijunctive constraints, there is a polynomial-time algorithm that detects $\mathcal{O}(1)$-essential constraint applications. This contrasts the fact that constant-factor approximating a bijunctive MinCSP$(\mathcal{F})$-problem is intractable under the Unique Games Conjecture.

Joshua Brakensiek, Venkatesan Guruswami, Bart M. P. Jansen et al.

The non-redundancy (NRD) of a constraint satisfaction problem (CSP) is a combinatorial quantity closely tied to the behavior of CSPs in various computational models including their sparsification, kernelization, and streaming complexity. A primary open question in the study of non-redundancy is the identification of which CSP predicates have near-linear NRD. Recent works by Carbonnel [CP 2022], Khanna, Putterman and Sudan [STOC 2025], Brakensiek and Guruswami [STOC 2025] and Brakensiek, Guruswami, Jansen, Lagerkvist, and Wahlström [2025] have introduced various forms of gadget reductions between CSPs to relate their non-redundancy. The primary contribution of this work is to recontextualize many of these gadget reductions in a framework which we call hypergraph projections. By studying a quantity we call the shrinking factor of these hypergraph projections, we can more precisely predict when a gadget reduction between predicates can yield a super-linear NRD lower bound, greatly improving on the analysis of previous works. To illustrate the power of our framework, we identify some concrete CSP predicates whose non-redundancy is at the cusp of our understanding and show how our methods give lower bounds that could not have been achieved with these previous methods. We also demonstrate how these gadget reductions can be automatically deduced using SAT solvers, thereby opening up novel computational avenues for discovering further relationships between the non-redundancy of various CSPs.

Mark de Berg, Bart M. P. Jansen, Jeroen S. K. Lamme

We study SINGLE-SOURCE SHORTEST PATH (SSSP) on unweighted intersection graphs whose node set corresponds to a set of $n$ constant-complexity objects in the plane. We prove SSSP can be solved in $O(U(n)\ \mathrm{polylog}\,n)$ expected time for any class of objects whose union complexity is $U(n)$. In particular, we obtain an $O(n 2^{α(n)}\log^2 n)$ algorithm for arbitrary pseudodisks, and an $O(λ_{s+2}(n)2^{O(\log^* n)} \log^2 n)$ algorithm for locally fat objects. This significantly extends the class of objects for which SSSP can be solved in $O(n\ \mathrm{polylog}\, n)$ time: so far, $O(n\ \mathrm{polylog}\, n)$ SSSP algorithms were not even known for pseudodisks that are fat and convex and similarly-sized. Our second result concerns the DIAMETER problem, which asks for the maximum distance between any two nodes in a graph. Even for intersection graphs, near-quadratic algorithms are difficult to obtain, and the $O(n^2\ \mathrm{polylog}\, n)$ running time that follows from our SSSP algorithm is the first near-quadratic running time for such general classes of intersection graphs. Obtaining subquadratic running time is even more challenging. We prove that the diameter of a set of arbitrary pseudodisks can be computed almost exactly, namely up to an additive error of 2, in $\tilde{O}(n^{2-1/14})$ expected time. This generalizes and speeds up a recent algorithm by Chang, Gao, and Le~(SoCG 2024) that works for similarly-sized disks (or similarly-sized pseudodisks that are fat and satisfy a strong monotonicity assumption) and runs in $\tilde{O}(n^{2-1/18})$ time. To this end, we develop a so-called star-based $r$-clustering for intersection graphs of pseudodisks, which is interesting in its own right. Our star-based $r$-clustering can also be used to obtain an almost exact distance oracle for pseudodisks that uses $O(n^{2-1/13})$ storage and has $O(1)$ query time.