Source-linked AI summary
Upper and Lower Bounds on the Complexity of Unit-Distance Graph Realization in $\mathbb{Z}^d$
Eric Binnendyk
TL;DR
The paper asks whether exhaustive search for unit-distance graph recognition on integer grids can be improved and how far its complexity can be bounded. It uses light balanced cuts in a divide-and-conquer algorithm, giving a subexponential upper bound alongside lower bounds that include the Z^3 case.
Problem
The paper asks whether the exhaustive search for unit-distance graph recognition can be improved, and whether a 2^Ω(|V|) algorithm is optimal under suitable hardness assumptions.
Source: §1 · p. 1Method
The paper uses light balanced cuts to divide the graph and recursively embed induced subgraphs in non-overlapping bounding boxes with cut-adjacent vertices aligned.
Source: §3 · p. 6Results
The algorithm runs in 2^~O(n^((d-1)/d)) time, and the lower bounds include 2^Ω(|V|^(2/3)) for recognition in Z^3.
Source: §3 · p. 6, §4 · p. 10Takeaways & Limitations
The divide-and-conquer approach beats naive exhaustive search by a factor of ~Ω(n^(1/d)) in the exponent.
Source: §3 · p. 6The lower bounds rely on ETH; extending them to a weaker ETH variant with an extra n^ε factor in the exponent remains to be checked.
Source: §4.1 · p. 10
Abstract
from arXiv · showhide
It is known that the problem of recognizing the existence of a unit-distance realization in $\mathbb{Z}^d$ for a graph $G$ is NP-complete. Here, assuming ETH, we give a sub-exponential lower bound of $2^{\Omega(\sqrt{n})}$ for this problem in $\mathbb{Z}^2$ and $2^{\Omega(n^{2/3})}$ in $\mathbb{Z}^3$, and give an upper bound of $2^{O(n^{(d-1)/d} (\log n)^2)}$ for the time complexity with an explicit divide-and-conquer algorithm. This approach beats naive exhaustive search by a factor of $\tilde{\Omega}(n^{1/d})$ in the exponent. For 2 and 3 dimensions, our upper and lower bounds match to within a logarithmic factor.
1 Introduction and related work
The paper studies whether a graph has an injective unit-distance realization in the integer grid Z^d, a problem known to be NP-complete for d ≥ 2. It uses light balanced cuts to obtain a subexponential divide-and-conquer algorithm.
1 Introduction and related work
- Unit-distance graph recognition is NP-complete in Z^2 and in dimensions d > 2.The cited results reduce from NA3SAT in dimension two and use a graph-prism construction in higher dimensions.Source: §1 · p. 1
- The naive search fixes one vertex and tries each of its 2d neighboring locations for each next vertex, taking O((2d)^|V|) time.It checks cross-edges and back-edges at each placement.Source: §1 · p. 1
Our realization algorithm
- The exhaustive divide-and-conquer algorithm runs in 2^~O(n^((d-1)/d)) time, beating naive search by ~Ω(n^(1/d)) in the exponent.The algorithm uses light balanced cuts to split the graph and embed the induced subgraphs in non-overlapping bounding boxes, aligning cut-adjacent vertices.Source: §1 · p. 2
1 Introduction and related work
- In R^2, unit-distance graph detection is ∃R-complete via Stretchability, while the cited work identifies higher-dimensional real-space complexity as open.The paper notes no previous complexity result for R^d when d > 2.Source: §1 · p. 2
- A logic engine converts an n-variable, m-clause NAkSAT formula into a planar realizability graph with O(mn) vertices and edges.Bhatt and Cosmadakis used this construction for unit-distance realizability in Z^2.Source: §1 · p. 2
- Adding the restriction that every length-k path has L1 distance k makes the Z^2 recognition problem polynomial-time solvable.Source: §1 · p. 2
2 Theorems about light balanced cuts
The section proves that grid-embeddable graphs have light balanced cuts: cuts with few crossing edges and substantial vertex sets on both sides. It establishes a two-dimensional result and extends the cut guarantee to d dimensions.
2.1 Two-dimensional case
- In Z^2, every n-vertex grid embedding has a horizontal or vertical cut crossing at most 2√n edges, with at least f(n) vertices on each side.Source: §2.1 · pp. 3–4
- In two dimensions, the cut is formed by edges between a light column and the next column; orthogonal edges ensure at most one crossing edge per vertex in the column.Source: §2.1 · p. 4
2.2 Higher-dimensional case
- For each direction i, the fraction p_i of points in heavy i-layers is defined using layers containing at least c n^(1/d) points; some direction has p_i ≤ p_min.The constant p_min depends on d and c.Source: §2.2 · p. 4
- In the higher-dimensional construction, a layer of fewer than c n^((d-1)/d) points can be chosen so that each side contains at least (1-p_min)n/2 - c n^((d-1)/d) points.The cut edges to the next layer number fewer than 2n^((d-1)/d) when c = 2.Source: §2.2 · p. 6
- Every d-dimensional grid embedding has an axis-perpendicular cut with fewer than 2n^((d-1)/d) crossing edges and at least (1-p_min)n/2 - 2n^((d-1)/d) vertices on each side.Here p_min is a constant in (0, 1) depending only on d; the side-size bound is positive for sufficiently large n.Source: §2.2 · p. 6
3 Our realization algorithm
The algorithm uses light balanced cuts to recursively test whether a graph embeds in a grid, with an upper bound that improves on exhaustive search. It handles base cases, enumerates candidate cuts and edge placements, and combines valid embeddings in separate bounding boxes.
3.6 Time complexity
- The divide-and-conquer algorithm uses light balanced cuts to achieve time 2^O(n^((d−1)/d)(log n)^2), improving on naive search by a factor of Ω̃(n^(1/d)) in the exponent.The cut theorems support the recursive split; the algorithm's bound is stated for constant d.Source: §3 · p. 6, §3.6 · p. 10
3 Our realization algorithm
- GridEmbed returns an injective grid embedding within the bounding box that respects prescribed locations, or reports failure when no such embedding exists.The routine takes the graph, dimension, bounding box, and a partial vertex-to-location map as input.Source: §3 · p. 6, §3.5 · p. 8
3.1 Base cases
- GridEmbed rejects inputs with a vertex degree above 2d, invalid or conflicting prescribed locations, or duplicate prescribed outputs; graphs with fewer than two vertices have a trivial base case.The trivial case returns the prescribed mapping when its locations are unique and inside the bounding box.Source: §3.1 · p. 7
3.2 Main iteration and recursion
- For each candidate planar cut, the algorithm enumerates small edge cuts, vertex-side partitions, and injective placements of cut edges before making two recursive calls.The geometric cut is chosen between consecutive coordinates in one direction of the bounding box.Source: §3.2 · p. 7
- The recursive calls embed the induced subgraphs in the two split bounding boxes, with cut-adjacent vertices constrained to the chosen edge positions; successful embeddings are translated and joined.If no iteration finds valid sub-embeddings, the algorithm returns False.Source: §3.2 · p. 7, §3.3 · p. 8
3.4 The parent function call
- The parent call initializes a connected n-vertex graph with a box of side length n−1 in each dimension; disconnected components are embedded separately and repositioned without overlap.This is the stated initial call to GridEmbed.Source: §3.4 · p. 8
3.5 Proof of correctness
- Correctness follows by induction: an embedding supplies a light balanced cut and compatible sub-embeddings, while every returned pair of sub-embeddings combines into a valid embedding.The recursion terminates because each recursive subgraph has fewer vertices; non-overlapping boxes prevent vertex collisions when combining the two sides.Source: §3.5 · pp. 8–9
4 Lower bounds
Assuming ETH, the paper establishes sub-exponential lower bounds for unit-distance graph recognition on two- and three-dimensional grids. Its reduction also yields a dimension-dependent bound that nearly matches the algorithm's upper bound in two dimensions.
4 Lower bounds
- The Bhatt–Cosmadakis reduction and graph-prism construction give a 2^Ω(√n) lower bound for d-dimensional grid embedding, or 2^Ω(√(n/2d)) when d is not assumed constant.The paper says this nearly matches the upper bound when d = 2.Source: §4 · p. 10
4.1 Exponential Time Hypothesis and Sparsification Lemma
The lower-bound argument relies on ETH and reductions from SAT to NAkSAT. Sparsification supplies linear-clause SAT instances, while the paper notes uncertainty around the ETH assumption and says a weaker version may suffice pending verification.
4.1 Exponential Time Hypothesis and Sparsification Lemma
- The paper says the cited claimed ETH disproof was under review and that the lower bounds may hold under a weaker ETH variant, which still needs checking separately.The proposed weaker assumption rules out 2^O(n^(1−ε)) algorithms for 3-SAT instances with O(n) clauses.Source: §4.1 · p. 10
- The Exponential Time Hypothesis assumes that k-SAT cannot be solved in 2^o(n) time for each k ≥ 3.Here n is the number of variables.Source: §4.1 · p. 10
- Sparsification reduces k-SAT to at most 2^εn instances with O(n) clauses each, in poly(n)2^εn time, while preserving the original solution set as their union.The paper uses this to restrict reductions to instances with linearly many clauses.Source: §4.1 · pp. 10–11
- A reduction transfers a 2^Ω(n) lower bound from k-SAT with n variables and m clauses to NAkSAT with n+m+1 variables and 2m clauses.The construction uses clause splitting after reducing k-SAT to NA(k+1)SAT.Source: §4.1 · p. 11
4.2 A 2Ω(|V |2/3) lower bound for 3 dimensions
A 3D logic engine encodes NA3SAT using a grid base, chains, flags, and variable connections. The resulting graph is realizable in Z^3 exactly when the formula is satisfiable, giving the stated sub-exponential lower bound under ETH.
4.2 A 2Ω(|V |2/3) lower bound for 3 dimensions
- The construction routes O(n) connections between lines perpendicular to the center plane through O(sqrt(n)) layers, using the third dimension to avoid overlaps.A graph-coloring argument establishes the layer bound.Source: §4.2 · p. 11
4.2.1 The base
- Tassel neighbors force the base grid into a planar embedding unique up to rigid transformation and rearrangement of non-grid edges.The proof propagates the fixed embedding of a square across the grid.Source: §4.2.1 · p. 12
4.2.2 Chains
- Each chain’s first h links are forced into consecutive planes parallel to the base, while neighboring chains remain four units apart.The centers of the first h links lie in a line perpendicular to the base.Source: §4.2.2 · p. 13
4.2.4 Encoding NA3SAT constraints
- Literal polarity determines which positive or negative chain link receives two rather than three flags, and a two-flag link can relieve row clashes.If every chain in a row has three flags, the row cannot embed; if at least one link has two, an embedding is possible.Source: §4.2.4 · pp. 14–15
- The clause gadget equates satisfying assignments to embeddings whose chains point up for true variables and down for false variables.This correspondence is stated for each clause’s variables and chains.Source: §4.2.4 · p. 15
4.2.5 Encoding variable connections
- A variable connection extends a valid connection-free embedding exactly when the two chains’ positive sides point in the same direction.Connections at the same height must also avoid overlap; chains pointing in opposite directions cannot be connected.Source: §4.2.5 · p. 17
- For an m by n chain grid with at most d connections per chain, the algorithm schedules all connections without clashes in 2(n + m)d - 2 layers.Connections that share a row or column are assigned different colors, with each color placed on a pair of layers.Source: §4.2.5 · pp. 18–19
4.2.6 Proof of main construction
- An n-variable O(n)-clause NA3SAT instance reduces in polynomial time to a graph of O(n^3/2) vertices realizable in Z^3 iff satisfiable, yielding an ETH lower bound of 2^Omega(|V|^2/3).The main construction has O(n) base vertices, chains, and connections, each chain or connection contributing O(sqrt(n)) vertices.Source: §4.2 · p. 11, §4.2.6 · p. 19
4.3 A 2Ω(|V |2/3) lower bound for 3-dimensional grid embedding
Assuming ETH, the reduction from 3-SAT through bounded-occurrence SAT and NA3SAT yields a 2^Ω(|V|^(2/3)) lower bound for 3-dimensional grid embedding. The bound applies to at least one graph for infinitely many vertex counts.
4.3 A 2Ω(|V |2/3) lower bound for 3-dimensional grid embedding
- Reducing 3-SAT to bounded-occurrence SAT, then to NA3SAT and a graph, transfers the ETH hardness to grid-embedding verification.The resulting graph has O(n^(3/2)) vertices when the SAT instance has n variables.Source: §4.3 · p. 19
- 2^Ω(|V|^(2/3)) is a conditional lower bound for 3-dimensional grid embedding under ETH.The proof establishes the runtime bound for at least one graph at each of infinitely many values of |V|.Source: §4.3 · pp. 19–20
- The reduction also gives a 2^Ω((|V|/2^d)^(2/3)) lower bound for d-dimensional grid embedding.Source: §4.3 · p. 20
4.4 The graph prism construction:
The graph prism construction relates grid embeddings across dimensions: G embeds in Z^d exactly when prism(G) embeds in Z^(d+1). Repeating the construction transfers the conditional lower bound to higher dimensions.
4.4 The graph prism construction:
- For connected G, any grid embedding of prism(G) places its two copies in neighboring parallel planes.The proof uses structural induction over vertices to show the lateral edges share a direction.Source: §4.4 · pp. 20–21
- G has a d-dimensional grid embedding if and only if prism(G) has a (d+1)-dimensional grid embedding.The prism has two copies of G joined by lateral edges, and has twice as many vertices as G.Source: §4.4 · pp. 20–21
- A d-dimensional embedding of G lifts to prism(G) by placing its copies one unit apart in a new coordinate.Conversely, the connected components of G can be realized separately in Z^d from the parallel-plane embedding.Source: §4.4 · p. 21
- Applying the prism construction extends the ETH lower bound to d-dimensional grid embedding: 2^Ω((|V|/2^d)^(2/3)).The reduction uses prism^(d−3)(G), with |V| = O(n^(3/2)2^d).Source: §4.4 · pp. 20–21
5 Future research
The authors propose extending their lower-bound work to higher-dimensional lattices and to real spaces, while identifying a conjectured bound and construction challenges.
5 Future research
- For d > 3, the authors plan to adapt their work and conjecture a reduction yielding a 2^Ω(|V|^((d−1)/d)) lower bound.They state that this would match the algorithm to a logarithmic factor in the exponent.Source: §5 · pp. 21–22
- They conjecture the same lower-bound exponent is tight up to a logarithmic factor for discrete d-dimensional lattices with unit-vector bases.Source: §5 · p. 22
- For higher-dimensional lattices, they expect logic-engine constructions to work but note the challenge of finding a rigid-structure building block.Source: §5 · p. 22
- For R^d, they expect Schaefer’s Peaucellier-linkage construction to extend systematically, but have no specific extension yet.Source: §5 · p. 22