← 研踪 PaperTrailarXiv:2610.36516 · v1
Upper and Lower Bounds on the Complexity of Unit-Distance Graph Realization in $\mathbb{Z}^d$
首次提交 2026-10-27 10:19
版本更新 2026-10-27 10:19
雷达观测 2026-10-29 00:35
摘要
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^{Ω(\sqrt{n})}$ for this problem in $\mathbb{Z}^2$ and $2^{Ω(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Ω(n^{1/d})$ in the exponent. For 2 and 3 dimensions, our upper and lower bounds match to within a logarithmic factor.
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v1 · 2026-10-27 10:19 · 最新观测版本
Upper and Lower Bounds on the Complexity of Unit-Distance Graph Realization in $\mathbb{Z}^d$
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^{Ω(\sqrt{n})}$ for this problem in $\mathbb{Z}^2$ and $2^{Ω(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Ω(n^{1/d})$ in the exponent. For 2 and 3 dimensions, our upper and lower bounds match to within a logarithmic factor.
查看此版本解读 →查看此版本原文 ↗