Twin-width

Last updated July 30, 2024

The twin-width of an undirected graph is a natural number associated with the graph, used to study the parameterized complexity of graph algorithms. Intuitively, it measures how similar the graph is to a cograph, a type of graph that can be reduced to a single vertex by repeatedly merging together twins, vertices that have the same neighbors. The twin-width is defined from a sequence of repeated mergers where the vertices are not required to be twins, but have nearly equal sets of neighbors.

Definition

Twin-width is defined for finite simple undirected graphs. These have a finite set of vertices, and a set of edges that are unordered pairs of vertices. The open neighborhood of any vertex is the set of other vertices that it is paired with in edges of the graph; the closed neighborhood is formed from the open neighborhood by including the vertex itself. Two vertices are true twins when they have the same closed neighborhood, and false twins when they have the same open neighborhood; more generally, both true twins and false twins can be called twins, without qualification.^[1]

The cographs have many equivalent definitions,^[2] but one of them is that these are the graphs that can be reduced to a single vertex by a process of repeatedly finding any two twin vertices and merging them into a single vertex. For a cograph, this reduction process will always succeed, no matter which choice of twins to merge is made at each step. For a graph that is not a cograph, it will always get stuck in a subgraph with more than two vertices that has no twins.^[1]

The definition of twin-width mimics this reduction process. A contraction sequence, in this context, is a sequence of steps, beginning with the given graph, in which each step replaces a pair of vertices by a single vertex. This produces a sequence of graphs, with edges colored red and black; in the given graph, all edges are assumed to be black. When two vertices are replaced by a single vertex, the neighborhood of the new vertex is the union of the neighborhoods of the replaced vertices. In this new neighborhood, an edge that comes from black edges in the neighborhoods of both vertices remains black; all other edges are colored red.^[1]

A contraction sequence is called a $d$ -sequence if, throughout the sequence, every vertex touches at most $d$ red edges. The twin-width of a graph is the smallest value of $d$ for which it has a $d$ -sequence.^[1]

A dense graph may still have bounded twin-width; for instance, the cographs include all complete graphs. A variation of twin-width, sparse twin-width, applies to families of graphs rather than to individual graphs. For a family of graphs that is closed under taking induced subgraphs and has bounded twin-width, the following properties are equivalent:^[3]

The graphs in the family are sparse, meaning that they have a number of edges bounded by a linear function of their number of vertices.
The graphs in the family exclude some fixed complete bipartite graph as a subgraph.
The family of all subgraphs of graphs in the given family has bounded twin-width.
The family has bounded expansion, meaning that all its shallow minors are sparse.

Such a family is said to have bounded sparse twin-width.^[3]

The concept of twin-width can be generalized from graphs to various totally ordered structures (including graphs equipped with a total ordering on their vertices), and is in many ways simpler for ordered structures than for unordered graphs.^[4] It is also possible to formulate equivalent definitions for other notions of graph width using contraction sequences with different requirements than having bounded degree.^[5]

Graphs of bounded twin-width

Cographs have twin-width zero. In the reduction process for cographs, there will be no red edges: when two vertices are merged, their neighborhoods are equal, so there are no edges coming from only one of the two neighborhoods to be colored red. In any other graph, any contraction sequence will produce some red edges, and the twin-width will be greater than zero.^[1]

The path graphs with at most three vertices are cographs, but every larger path graph has twin-width one. For a contraction sequence that repeatedly merges the last two edges of the path, only the edge incident to the single merged vertex will be red, so this is a 1-sequence. Trees have twin-width at most two, and for some trees this is tight. A 2-contraction sequence for any tree may be found by choosing a root, and then repeatedly merging two leaves that have the same parent or, if this is not possible, merging the deepest leaf into its parent. The only red edges connect leaves to their parents, and when there are two at the same parent they can be merged, keeping the red degree at most two.^[1]

More generally, the following classes of graphs have bounded twin-width, and a contraction sequence of bounded width can be found for them in polynomial time:

Every graph of bounded clique-width, or of bounded rank-width, also has bounded twin-width. The twin-width is at most exponential in the clique-width, and at most doubly exponential in the rank-width.^[1] These graphs include, for instance, the distance-hereditary graphs, the $k$ -leaf powers for bounded values of $k$ , and the graphs of bounded treewidth.
Indifference graphs (equivalently, unit interval graphs or proper interval graphs) have twin-width at most two.^[6]
Unit disk graphs defined from sets of unit disks that cover each point of the plane a bounded number of times have bounded twin-width. The same is true for unit ball graphs in higher dimensions.^[1]
The permutation graphs coming from permutations with a forbidden permutation pattern have bounded twin-width. This allows twin-width to be applied to algorithmic problems on permutations with forbidden patterns.^[1]
Every family of graphs defined by forbidden minors has bounded twin-width. For instance, by Wagner's theorem, the forbidden minors for planar graphs are the two graphs $K_{5}$ and $K_{3,3}$ , so the planar graphs have bounded twin-width.^[1]
Every graph of bounded stack number or bounded queue number also has bounded twin-width.^[3] There exist families of graphs of bounded sparse twin-width that do not have bounded stack number, but the corresponding question for queue number remains open.^[7]
The strong product of any two graphs of bounded twin-width, one of which has bounded degree, again has bounded twin-width. This can be used to prove the bounded twin-width of classes of graphs that have decompositions into strong products of paths and bounded-treewidth graphs, such as the $k$ -planar graphs.^[3] For the lexicographic product of graphs, the twin-width is exactly the maximum of the widths of the two factor graphs.^[8] Twin-width also behaves well under several other standard graph products, but not the modular product of graphs.^[9]

In every hereditary family of graphs of bounded twin-width, it is possible to find a family of total orders for the vertices of its graphs so that the inherited ordering on an induced subgraph is also an ordering in the family, and so that the family is small with respect to these orders. This means that, for a total order on $n$ vertices, the number of graphs in the family consistent with that order is at most singly exponential in $n$ . Conversely, every hereditary family of ordered graphs that is small in this sense has bounded twin-width.^[4] It was originally conjectured that every hereditary family of labeled graphs that is small, in the sense that the number of graphs is at most a singly exponential factor times $n!$ , has bounded twin-width.^[3] However, this conjecture was disproved using a family of induced subgraphs of an infinite Cayley graph that are small as labeled graphs but do not have bounded twin-width.^[10]

There exist graphs of unbounded twin-width within the following families of graphs:

In each of these cases, the result follows by a counting argument: there are more graphs of the given type than there can be graphs of bounded twin-width.^[1]

Properties

If a graph has bounded twin-width, then it is possible to find a versatile tree of contractions. This is a large family of contraction sequences, all of some (larger) bounded width, so that at each step in each sequence there are linearly many disjoint pairs of vertices each of which could be contracted at the next step in the sequence. It follows from this that the number of graphs of bounded twin-width on any set of $n$ given vertices is larger than $n!$ by only a singly exponential factor, that the graphs of bounded twin-width have an adjacency labelling scheme with only a logarithmic number of bits per vertex, and that they have universal graphs of polynomial size in which each $n$ -vertex graph of bounded twin-width can be found as an induced subgraph.^[3]

Algorithms

The graphs of twin-width at most one can be recognized in polynomial time.^[8] However, it is NP-complete to determine whether a given graph has twin-width at most four, and NP-hard to approximate the twin-width with an approximation ratio better than 5/4. Under the exponential time hypothesis, computing the twin-width requires time at least exponential in $n/\log n$ , on $n$ -vertex graphs.^[11] In practice, it is possible to compute the twin-width of graphs of moderate size using SAT solvers.^[12] For most of the known families of graphs of bounded twin-width, it is possible to construct a contraction sequence of bounded width in polynomial time.^[1]

Once a contraction sequence has been given or constructed, many different algorithmic problems can be solved using it, in many cases more efficiently than is possible for graphs that do not have bounded twin-width. As detailed below, these include exact parameterized algorithms and approximation algorithms for NP-hard problems, as well as some problems that have classical polynomial time algorithms but can nevertheless be sped up using the assumption of bounded twin-width.

Parameterized algorithms

An algorithmic problem on graphs having an associated parameter is called fixed-parameter tractable if it has an algorithm that, on graphs with $n$ vertices and parameter value $k$ , runs in time $O(n^{c}\,f(k))$ for some constant $c$ and computable function $f$ . For instance, a running time of $O(n2^{k})$ would be fixed-parameter tractable in this sense. This style of analysis is generally applied to problems that do not have a known polynomial-time algorithm, because otherwise fixed-parameter tractability would be trivial. Many such problems have been shown to be fixed-parameter tractable with twin-width as a parameter, when a contraction sequence of bounded width is given as part of the input. This applies, in particular, to the graph families of bounded twin-width listed above, for which a contraction sequence can be constructed efficiently. However, it is not known how to find a good contraction sequence for an arbitrary graph of low twin-width, when no other structure in the graph is known.

The fixed-parameter tractable problems for graphs of bounded twin-width with given contraction sequences include:

Testing whether the given graph models any given property in the first-order logic of graphs. Here, both the twin-width and the description length of the property are parameters of the analysis. Problems of this type include subgraph isomorphism for subgraphs of bounded size, and the vertex cover and dominating set problems for covers or dominating sets of bounded size.^[1] The dependence of these general methods on the length of the logical formula describing the property is tetrational, but for independent set, dominating set, and related problems it can be reduced to exponential in the size of the independent or dominating set, and for subgraph isomorphism it can be reduced to factorial in the number of vertices of the subgraph. For instance, the time to find a $k$ -vertex independent set, for an $n$ -vertex graph with a given $d$ -sequence, is $O(k^{2}d^{2k}n)$ , by a dynamic programming algorithm that considers small connected subgraphs of the red graphs in the forward direction of the contraction sequence. These time bounds are optimal, up to logarithmic factors in the exponent, under the exponential time hypothesis.^[6] For an extension of the first-order logic of graphs to graphs with totally ordered vertices, and logical predicates that can test this ordering, model checking is still fixed-parameter tractable for hereditary graph families of bounded twin-width, but not (under standard complexity-theoretic assumptions) for hereditary families of unbounded twin-width.^[13]
Coloring graphs of bounded twin-width, using a number of colors that is bounded by a function of their twin-width and of the size of their largest clique. For instance, triangle-free graphs of twin-width $d$ can be $(d+2)$ -colored by a greedy coloring algorithm that colors vertices in the reverse of the order they were contracted away.^[6] This result shows that the graphs of bounded twin-width are χ-bounded.^[6]^[14] For graph families of bounded sparse twin-width, the generalized coloring numbers are bounded. Here, the generalized coloring number $\operatorname {col} _{r}(G)$ is at most $k$ if the vertices can be linearly ordered in such a way that each vertex can reach at most $k-1$ earlier vertices in the ordering, through paths of length $r$ through later vertices in the ordering.^[15]

Speedups of classical algorithms

In graphs of bounded twin-width, it is possible to perform a breadth-first search, on a graph with $n$ vertices, in time $O(n\log n)$ , even when the graph is dense and has more edges than this time bound.^[6]

Approximation algorithms

Twin-width has also been applied in approximation algorithms. In particular, in the graphs of bounded twin-width, it is possible to find an approximation to the minimum dominating set with bounded approximation ratio. This is in contrast to more general graphs, for which it is NP-hard to obtain an approximation ratio that is better than logarithmic.^[6]

The maximum independent set and graph coloring problems can be approximated to within an approximation ratio of $n^{\varepsilon }$ , for every $\varepsilon >0$ , in polynomial time on graphs of bounded twin-width. In contrast, without the assumption of bounded twin-width, it is NP-hard to achieve any approximation ratio of this form with $\varepsilon <1$ .^[16]

Related Research Articles

In graph theory, an interval graph is an undirected graph formed from a set of intervals on the real line, with a vertex for each interval and an edge between vertices whose intervals intersect. It is the intersection graph of the intervals.

In graph theory, a cograph, or complement-reducible graph, or P₄-free graph, is a graph that can be generated from the single-vertex graph K₁ by complementation and disjoint union. That is, the family of cographs is the smallest class of graphs that includes K₁ and is closed under complementation and disjoint union.

The art gallery problem or museum problem is a well-studied visibility problem in computational geometry. It originates from the following real-world problem:

"In an art gallery, what is the minimum number of guards who together can observe the whole gallery?"

In graph theory, the metric dimension of a graph G is the minimum cardinality of a subset S of vertices such that all other vertices are uniquely determined by their distances to the vertices in S. Finding the metric dimension of a graph is an NP-hard problem; the decision version, determining whether the metric dimension is less than a given value, is NP-complete.

In geometric graph theory, a unit disk graph is the intersection graph of a family of unit disks in the Euclidean plane. That is, it is a graph with one vertex for each disk in the family, and with an edge between two vertices whenever the corresponding vertices lie within a unit distance of each other.

In graph theory, the Grundy number or Grundy chromatic number of an undirected graph is the maximum number of colors that can be used by a greedy coloring strategy that considers the vertices of the graph in sequence and assigns each vertex its first available color, using a vertex ordering chosen to use as many colors as possible. Grundy numbers are named after P. M. Grundy, who studied an analogous concept for directed graphs in 1939. The undirected version was introduced by Christen & Selkow (1979).

In the mathematical area of graph theory, a triangle-free graph is an undirected graph in which no three vertices form a triangle of edges. Triangle-free graphs may be equivalently defined as graphs with clique number ≤ 2, graphs with girth ≥ 4, graphs with no induced 3-cycle, or locally independent graphs.

In graph theory, a cactus is a connected graph in which any two simple cycles have at most one vertex in common. Equivalently, it is a connected graph in which every edge belongs to at most one simple cycle, or in which every block is an edge or a cycle.

In graph theory, the strong product is a way of combining two graphs to make a larger graph. Two vertices are adjacent in the strong product when they come from pairs of vertices in the factor graphs that are either adjacent or identical. The strong product is one of several different graph product operations that have been studied in graph theory. The strong product of any two graphs can be constructed as the union of two other products of the same two graphs, the Cartesian product of graphs and the tensor product of graphs.

In graph theory, the Laman graphs are a family of sparse graphs describing the minimally rigid systems of rods and joints in the plane. Formally, a Laman graph is a graph on n vertices such that, for all k, every k-vertex subgraph has at most 2k − 3 edges, and such that the whole graph has exactly 2n − 3 edges. Laman graphs are named after Gerard Laman, of the University of Amsterdam, who in 1970 used them to characterize rigid planar structures. However, this characterization, the Geiringer–Laman theorem, had already been discovered in 1927 by Hilda Geiringer.

In graph theory, the clique-width of a graph $G$ is a parameter that describes the structural complexity of the graph; it is closely related to treewidth, but unlike treewidth it can be small for dense graphs. It is defined as the minimum number of labels needed to construct $G$ by means of the following 4 operations :

Creation of a new vertex $v$ with label $i$ (denoted by $i (v)$ )
Disjoint union of two labeled graphs $G$ and $H$ (denoted by $)$
Joining by an edge every vertex labeled $i$ to every vertex labeled $j$ (denoted by $η (i, j)$ ), where $i \neq j$
Renaming label $i$ to label $j$ (denoted by $ρ (i, j)$ )

In graph theory, a branch of discrete mathematics, a distance-hereditary graph is a graph in which the distances in any connected induced subgraph are the same as they are in the original graph. Thus, any induced subgraph inherits the distances of the larger graph.

In computational complexity theory and the analysis of algorithms, an algorithm is said to take quasi-polynomial time if its time complexity is quasi-polynomially bounded. That is, there should exist a constant $such that the worst-case running time of the algorithm, on inputs of size, has an upper bound of the form$

In geometric graph theory, a branch of mathematics, a matchstick graph is a graph that can be drawn in the plane in such a way that its edges are line segments with length one that do not cross each other. That is, it is a graph that has an embedding which is simultaneously a unit distance graph and a plane graph. For this reason, matchstick graphs have also been called planar unit-distance graphs. Informally, matchstick graphs can be made by placing noncrossing matchsticks on a flat surface, hence the name.

In computer science, the method of contraction hierarchies is a speed-up technique for finding the shortest-path in a graph. The most intuitive applications are car-navigation systems: a user wants to drive from $to using the quickest possible route. The metric optimized here is the travel time. Intersections are represented by vertices, the road sections connecting them by edges. The edge weights represent the time it takes to drive along this segment of the road. A path from to is a sequence of edges ; the shortest path is the one with the minimal sum of edge weights among all possible paths. The shortest path in a graph can be computed using Dijkstra's algorithm but, given that road networks consist of tens of millions of vertices, this is impractical. Contraction hierarchies is a speed-up method optimized to exploit properties of graphs representing road networks. The speed-up is achieved by creating shortcuts in a preprocessing phase which are then used during a shortest-path query to skip over "unimportant" vertices. This is based on the observation that road networks are highly hierarchical. Some intersections, for example highway junctions, are "more important" and higher up in the hierarchy than for example a junction leading into a dead end. Shortcuts can be used to save the precomputed distance between two important junctions such that the algorithm doesn't have to consider the full path between these junctions at query time. Contraction hierarchies do not know about which roads humans consider "important", but they are provided with the graph as input and are able to assign importance to vertices using heuristics.$

In graph theory, a branch of mathematics, a half graph is a special type of bipartite graph. These graphs are called the half graphs because they have approximately half of the edges of a complete bipartite graph on the same vertices. The name was given to these graphs by Paul Erdős and András Hajnal.

In the mathematics of graph coloring, Cereceda’s conjecture is an unsolved problem on the distance between pairs of colorings of sparse graphs. It states that, for two different colorings of a graph of degeneracy $d$ , both using at most $d + 2$ colors, it should be possible to reconfigure one coloring into the other by changing the color of one vertex at a time, using a number of steps that is quadratic in the size of the graph. The conjecture is named after Luis Cereceda, who formulated it in his 2007 doctoral dissertation.

In computational geometry, a polygonalization of a finite set of points in the Euclidean plane is a simple polygon with the given points as its vertices. A polygonalization may also be called a polygonization, simple polygonalization, Hamiltonian polygon, non-crossing Hamiltonian cycle, or crossing-free straight-edge spanning cycle.

In graph theory, the Graham–Pollak theorem states that the edges of an $-vertex complete graph cannot be partitioned into fewer than complete bipartite graphs. It was first published by Ronald Graham and Henry O. Pollak in two papers in 1971 and 1972, in connection with an application to telephone switching circuitry.$

A parameterized approximation algorithm is a type of algorithm that aims to find approximate solutions to NP-hard optimization problems in polynomial time in the input size and a function of a specific parameter. These algorithms are designed to combine the best aspects of both traditional approximation algorithms and fixed-parameter tractability.

References

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Bonnet, Édouard; Kim, Eun Jung; Thomassé, Stéphan; Watrigant, Rémi (2022), "Twin-width I: Tractable FO model checking", Journal of the ACM , 69 (1): A3:1–A3:46, arXiv: 2004.14789 , doi:10.1145/3486655, MR 4402362
↑ "Cograph graphs", Information System on Graph Class Inclusions
1 2 3 4 5 6 Bonnet, Édouard; Geniet, Colin; Kim, Eun Jung; Thomassé, Stéphan; Watrigant, Rémi (2022), "Twin-width II: small classes", Combinatorial Theory, 2 (2): P10:1–P10:42, arXiv: 2006.09877 , doi:10.5070/C62257876, MR 4449818
1 2 Bonnet, Édouard; Giocanti, Ugo; de Mendez, Patrice Ossona; Simon, Pierre; Thomassé, Stéphan; Torunczyk, Szymon (2022), "Twin-width IV: ordered graphs and matrices", in Leonardi, Stefano; Gupta, Anupam (eds.), STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20–24, 2022, Association for Computing Machinery, pp. 924–937, arXiv: 2102.03117 , doi:10.1145/3519935.3520037, ISBN 978-1-4503-9264-8, S2CID 235743245
↑ Bonnet, Édouard; Kim, Eun Jung; Reinald, Amadeus; Thomassé, Stéphan (2022), "Twin-width VI: the lens of contraction sequences", in Naor, Joseph (Seffi); Buchbinder, Niv (eds.), Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, VA, USA, January 9–12, 2022, Society for Industrial and Applied Mathematics, pp. 1036–1056, arXiv: 2111.00282 , doi:10.1137/1.9781611977073.45, ISBN 978-1-61197-707-3, S2CID 240354166
1 2 3 4 5 6 Bonnet, Édouard; Geniet, Colin; Kim, Eun Jung; Thomassé, Stéphan; Watrigant, Rémi (2021), "Twin-width III: Max independent set, min dominating set, and coloring", in Bansal, Nikhil; Merelli, Emanuela; Worrell, James (eds.), 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, July 12–16, 2021, Glasgow, Scotland (Virtual Conference), LIPIcs, vol. 198, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, pp. 35:1–35:20, arXiv: 2007.14161 , doi: 10.4230/LIPIcs.ICALP.2021.35 , ISBN 9783959771955, S2CID 235736798
↑ Dujmović, Vida; Eppstein, David; Hickingbotham, Robert; Morin, Pat; Wood, David R. (August 2021), "Stack-Number is not bounded by queue-number", Combinatorica , 42 (2): 151–164, arXiv: 2011.04195 , doi:10.1007/s00493-021-4585-7, S2CID 226281691
1 2 Bonnet, Édouard; Kim, Eun Jung; Reinald, Amadeus; Thomassé, Stéphan; Watrigant, Rémi (2022), "Twin-width and polynomial kernels", Algorithmica , 84 (11): 3300–3337, arXiv: 2107.02882 , doi:10.1007/s00453-022-00965-5, MR 4500778
↑ Pettersson, William; Pettersson, John (June 2023), "Bounds on the twin-width of product graphs", Discrete Mathematics & Theoretical Computer Science, 25 (1), arXiv: 2202.11556 , doi:10.46298/dmtcs.10091
↑ Bonnet, Édouard; Geniet, Colin; Tessera, Romain; Thomassé, Stéphan (2022), "Twin-width VII: groups", arXiv: 2204.12330 [math.GR]
↑ Bergé, Pierre; Bonnet, Édouard; Déprés, Hugues (2022), "Deciding twin-width at most 4 Is NP-complete", in Bojanczyk, Mikolaj; Merelli, Emanuela; Woodruff, David P. (eds.), 49th International Colloquium on Automata, Languages, and Programming, ICALP 2022, July 4–8, 2022, Paris, France, LIPIcs, vol. 229, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, pp. 18:1–18:20, arXiv: 2112.08953 , doi: 10.4230/LIPIcs.ICALP.2022.18 , ISBN 9783959772358, S2CID 245218775
↑ Schidler, André; Szeider, Stefan (2022), "A SAT approach to twin-width", in Phillips, Cynthia A.; Speckmann, Bettina (eds.), Proceedings of the Symposium on Algorithm Engineering and Experiments, ALENEX 2022, Alexandria, VA, USA, January 9–10, 2022, Society for Industrial and Applied Mathematics, pp. 67–77, arXiv: 2110.06146 , doi:10.1137/1.9781611977042.6, ISBN 978-1-61197-704-2, S2CID 238634418
↑ Simon, Pierre; Toruńczyk, Szymon (2021), Ordered graphs of bounded twin-width, arXiv: 2102.06881
↑ Pilipczuk, Marek; Sokołowski, Michał (2023), "Graphs of bounded twin-width are quasi-polynomially $\chi$ -bounded", Journal of Combinatorial Theory, Series B , 161: 382–406, arXiv: 2202.07608 , doi:10.1016/j.jctb.2023.02.006, MR 4568111, S2CID 247170805
↑ Dreier, Jan; Gajarský, Jakub; Jiang, Yiting; Ossona de Mendez, Patrice; Raymond, Jean-Florent (2022), "Twin-width and generalized coloring numbers", Discrete Mathematics , 345 (3), Paper 112746, arXiv: 2104.09360 , doi:10.1016/j.disc.2021.112746, MR 4349879, S2CID 233296212
↑ Bergé, Pierre; Bonnet, Édouard; Déprés, Hugues; Watrigant, Rémi (2023), "Approximating highly inapproximable problems on graphs of bounded twin-width", in Berenbrink, Petra; Bouyer, Patricia; Dawar, Anuj; Kanté, Mamadou Moustapha (eds.), 40th International Symposium on Theoretical Aspects of Computer Science, STACS 2023, March 7-9, 2023, Hamburg, Germany, LIPIcs, vol. 254, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 10:1–10:15, arXiv: 2207.07708 , doi: 10.4230/LIPIcs.STACS.2023.10