Jean Cardinal

Jean Cardinal, Micha Sharir

Semialgebraic graphs are graphs whose vertices are points in $\mathbb{R}^d$, and adjacency between two vertices is determined by the truth value of a semialgebraic predicate of constant complexity. We show how to harness polynomial partitioning methods to construct compact adjacency labeling schemes for families of semialgebraic graphs. That is, we show that for any family of semialgebraic graphs, given a graph on $n$ vertices in this family, we can assign a label consisting of $O(n^{1-2/(d+1) + \varepsilon})$ bits to each vertex (where $\varepsilon > 0$ can be made arbitrarily small and the constant of proportionality depends on $\varepsilon$ and on the complexity of the adjacency-defining predicate), such that adjacency between two vertices can be determined solely from their two labels, without any additional information. We obtain for instance that unit disk graphs and segment intersection graphs have such labelings with labels of $O(n^{1/3 + \varepsilon})$ bits. This is in contrast to their natural implicit representation consisting of the coordinates of the disk centers or segment endpoints, which sometimes require exponentially many bits. It also improves on the best known bound of $O(n^{1-1/d}\log n)$ for $d$-dimensional semialgebraic families due to Alon (Discrete Comput. Geom., 2024), a bound that holds more generally for graphs with shattering functions bounded by a degree-$d$ polynomial. We also give new bounds on the size of adjacency labels for other families of graphs. In particular, we consider semilinear graphs, which are semialgebraic graphs in which the predicate only involves linear polynomials. We show that semilinear graphs have adjacency labels of size $O(\log n)$. We also prove that polygon visibility graphs, which are not semialgebraic in the above sense, have adjacency labels of size $O(\log^3 n)$.

Boris Aronov, Jean Cardinal, Justin Dallant et al.

In recent years, the Fiat-Naor function inversion scheme has been used to disprove conjectures in fine-grained complexity theory and design state of the art data structures for a number of combinatorial problems. We pursue this line of research by considering its application to data structures for searching in implicit sets, defined as the image of a function. We show that, if $f$ is of the form $[N]\to [2^{w}]^d$ for some $w=polylog(N)$ and is computable in constant time, then, for any $0<α<1$, we can obtain a data structure using $Õ(N^{1-α/3})$ space such that, for a given $d$-dimensional axis-aligned box $B$, we can search for some $x\in [N]$ such that $f(x) \in B$ in time $Õ(N^α)$. (Here the $Õ(.)$ notation omits polylogarithmic factors.) Using similar techniques, we further obtain - data structures for range counting and reporting, predecessor, selection, ranking queries, and combinations thereof, on the set $f([N])$, - data structures for preimage size and preimage selection queries for a given value of $f$, and - data structures for selection and ranking queries on geometric quantities computed from tuples of points in $d$-space. These results unify and generalize previously known results on 3SUM-indexing and string searching, and are widely applicable as a black box to a variety of problems. In particular, we give a data structure for a generalized version of gapped string indexing, and show how to preprocess a set of points on an integer grid in order to efficiently compute (in sublinear time), for points contained in a given axis-aligned box, their Theil-Sen estimator, the $k$th largest area triangle, or the induced hyperplane that is the $k$th furthest from the origin.

Jean Cardinal, Kevin Mann, Akira Suzuki et al.

We initiate the study of the shortest reconfiguration problem for independent sets under the adjacency relation derived from the independent set polytope. Given a graph and two independent sets, the problem asks for a shortest sequence transforming one into the other such that the subgraph induced by the symmetric difference of any two consecutive sets is connected. This is equivalent to finding a shortest path on the $1$-skeleton of the independent set polytope. We prove that the problem is NP-hard even on planar graphs of bounded degree, as well as on split graphs. Notably, the hardness for planar graphs of bounded degree still holds even when deciding whether the target can be reached in at most two steps. For split graphs, we further show the W[2]-hardness when parameterized by the number of steps, as well as the inapproximability of the optimal length. As a consequence, we prove that the length of a shortest path between two vertices of a 0/1 polytope in $\mathbb{R}^n$ described by $O(n)$ linear inequalities is hard to approximate within a factor of $(1-\varepsilon)\ln n$ for any constant $ε>0$, unless $P=NP$. On the positive side, we provide polynomial-time algorithms for block graphs, cographs, and bipartite chain graphs. Moreover, for paths and cycles, we show that the optimal length of the shortest reconfiguration sequence exactly matches a trivial upper bound.