The Complexity of Recognizing Geometric Hypergraphs
Bertschinger, Daniel1; El Maalouly, Nicolas1; Kleist, Linda2; Miltzow, Tillmann3; Weber, Simon1
1 ETH Zürich Department of Computer Science Switzerland
2 Universität Potsdam Institute of Computer Science Germany
3 Utrecht University Department of Information and Computing Sciences the Netherlands
Innovations in Graph Theory, Volume 2 (2025), pp. 157-190.

As set systems, hypergraphs are omnipresent and have various representations ranging from Euler and Venn diagrams to contact representations. In a geometric representation of a hypergraph $H=(V,E)$, each vertex $v\in V$ is associated with a point $p_v\in \mathbb{R}^d$ and each hyperedge $e\in E$ is associated with a connected set $s_e\subset \mathbb{R}^d$ such that $\lbrace p_v\mid v\in V\rbrace \cap s_e=\lbrace p_v\mid v\in e\rbrace $ for all $e\in E$. We say that a given hypergraph $H$ is representable by some (infinite) family $\mathcal{F} $ of sets in ${\mathbb{R}^d}$, if there exist $P\subset \mathbb{R}^d$ and $S \subseteq \mathcal{F} $ such that $(P,S)$ is a geometric representation of $H$. For a family $\mathcal{F}$, we define Recognition ($\mathcal{F}$) as the problem to determine if a given hypergraph is representable by $\mathcal{F}$. It is known that the Recognition problem is $\exists \mathbb{R}$-hard for halfspaces in $\mathbb{R}^d$. We study the families of translates and homothets of balls and ellipsoids in $\mathbb{R}^d$, as well as of other convex sets, and show that their Recognition problems are also $\exists \mathbb{R}$-complete. In particular, for a bi-curved, computable set $C$, the recognition problem of the family of translates (or homothets) of $C$ is $\exists \mathbb{R}$-complete if it is T-difference-separable (H-difference-separable). We show that for bounded sets in the plane, convexity is equivalent to T-difference-separability and H-difference-separability; in higher dimensions, convexity is necessary but not sufficient. Our results imply that these recognition problems are equivalent to deciding whether a multivariate system of polynomial equations with integer coefficients has a real solution.

Received:
Accepted:
Published online:
DOI: 10.5802/igt.9
Classification: 05C62, 68R10, 05C65
Keywords: Hypergraph, geometric hypergraph, recognition, computational complexity, convex, ball, ellipsoid, halfplane, halfspace, translate, homothet, bi-curved, difference-separable.

Bertschinger, Daniel 1; El Maalouly, Nicolas 1; Kleist, Linda 2; Miltzow, Tillmann 3; Weber, Simon 1

1 ETH Zürich Department of Computer Science Switzerland
2 Universität Potsdam Institute of Computer Science Germany
3 Utrecht University Department of Information and Computing Sciences the Netherlands
License: CC-BY 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights 
@article{IGT_2025__2__157_0,
     author = {Bertschinger, Daniel and El~Maalouly, Nicolas and Kleist, Linda and Miltzow, Tillmann and Weber, Simon},
     title = {The {Complexity} of {Recognizing}  {Geometric} {Hypergraphs}},
     journal = {Innovations in Graph Theory},
     pages = {157--190},
     publisher = {Stichting Innovations in Graph Theory},
     volume = {2},
     year = {2025},
     doi = {10.5802/igt.9},
     language = {en},
     url = {https://igt.centre-mersenne.org/articles/10.5802/igt.9/}
}
TY  - JOUR
AU  - Bertschinger, Daniel
AU  - El Maalouly, Nicolas
AU  - Kleist, Linda
AU  - Miltzow, Tillmann
AU  - Weber, Simon
TI  - The Complexity of Recognizing  Geometric Hypergraphs
JO  - Innovations in Graph Theory
PY  - 2025
SP  - 157
EP  - 190
VL  - 2
PB  - Stichting Innovations in Graph Theory
UR  - https://igt.centre-mersenne.org/articles/10.5802/igt.9/
DO  - 10.5802/igt.9
LA  - en
ID  - IGT_2025__2__157_0
ER  - 
%0 Journal Article
%A Bertschinger, Daniel
%A El Maalouly, Nicolas
%A Kleist, Linda
%A Miltzow, Tillmann
%A Weber, Simon
%T The Complexity of Recognizing  Geometric Hypergraphs
%J Innovations in Graph Theory
%D 2025
%P 157-190
%V 2
%I Stichting Innovations in Graph Theory
%U https://igt.centre-mersenne.org/articles/10.5802/igt.9/
%R 10.5802/igt.9
%G en
%F IGT_2025__2__157_0
Bertschinger, Daniel; El Maalouly, Nicolas; Kleist, Linda; Miltzow, Tillmann; Weber, Simon. The Complexity of Recognizing  Geometric Hypergraphs. Innovations in Graph Theory, Volume 2 (2025), pp. 157-190. doi : 10.5802/igt.9. https://igt.centre-mersenne.org/articles/10.5802/igt.9/

[1] Abrahamsen, Mikkel Covering Polygons is Even Harder, IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS 2022) (2022), pp. 375-386 | DOI | MR

[2] Abrahamsen, Mikkel; Adamaszek, Anna; Miltzow, Tillmann The Art Gallery Problem is ∃ℝ-complete, Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2018) (2018), pp. 65-73 | DOI | MR | Zbl

[3] Abrahamsen, Mikkel; Kleist, Linda; Miltzow, Tillmann Training Neural Networks is ∃ℝ-complete, Advances in Neural Information Processing Systems (NeurIPS 2021) (2021), pp. 18293-18306 https://proceedings.neurips.cc/paper_files/paper/2021/file/9813b270ed0288e7c0388f0fd4ec68f5-paper.pdf

[4] Abrahamsen, Mikkel; Kleist, Linda; Miltzow, Tillmann Geometric Embeddability of Complexes is ∃ℝ-complete (2023) To appear in: Symposium on Computational Geometry (SOCG 2023) | arXiv | DOI

[5] Abrahamsen, Mikkel; Miltzow, Tillmann; Seiferth, Nadja Framework for ∃ℝ-Completeness of Two-Dimensional Packing Problems, IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS 2020) (2020), pp. 1014-1021 | DOI | MR

[6] Aronov, Boris; Ezra, Esther; Sharir, Micha Small-Size ϵ-Nets for Axis-Parallel Rectangles and Boxes, SIAM Journal on Computing (SiComp), Volume 39 (2010) no. 7, pp. 3248-3282 | DOI | MR | Zbl

[7] Axenovich, Maria; Ueckerdt, Torsten Density of range capturing hypergraphs, Journal of Computational Geometry (JoCG), Volume 7 (2016) no. 1 | DOI | MR

[8] Berthelsen, Marie L. T.; Hansen, Kristoffer A. On the Computational Complexity of Problems About Multi-player Nash Equilibria, International Symposium on Algorithmic Game Theory (LNCS), Volume 11801 (2019), pp. 153-167 | DOI | Zbl

[9] Bertschinger, Daniel; El Maalouly, Nicolas; Kleist, Linda; Miltzow, Tillmann; Weber, Simon The Complexity of Recognizing Geometric Hypergraphs, Graph Drawing and Network Visualization (GD’23) (2023), pp. 163-179 | DOI | Zbl

[10] Bertschinger, Daniel; Hertrich, Christoph; Jungeblut, Paul; Miltzow, Tillmann; Weber, Simon Training Fully Connected Neural Networks is ∃ℝ-Complete (2022) | arXiv | DOI

[11] Bilò, Vittorio; Mavronicolas, Marios A Catalog of ∃ℝ-Complete Problems About Nash Equilibria in Multi-Player Games, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016) ((LIPIcs)) (2016), p. 17:1-17:13 | DOI | MR | Zbl

[12] Bilò, Vittorio; Mavronicolas, Marios ∃ℝ-Complete Decision Problems about Symmetric Nash Equilibria in Symmetric Multi-Player Games, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017) ((LIPIcs)), Volume 66 (2017), p. 13:1-13:14 | DOI | MR | Zbl

[13] Booth, Kellogg S.; Lueker, George S. Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms, Journal of Computer and System Sciences, Volume 13 (1976) no. 3, pp. 335-379 | DOI | MR | Zbl

[14] Booth, Kellogg S.; Lueker, George S. Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms, Journal of computer and system sciences, Volume 13 (1976) no. 3, pp. 335-379 | DOI | MR | Zbl

[15] Čadek, Martin; Krčál, Marek; Matoušek, Jiří; Sergeraert, Francis; Vokřínek, Lukáš; Wagner, Uli Computing all maps into a sphere, Journal of the ACM, Volume 61 (2014) no. 3, pp. 1-44 | DOI | MR | Zbl

[16] Čadek, Martin; Krčál, Marek; Matoušek, Jiří; Vokřínek, Lukáš; Wagner, Uli Time computation of homotopy groups and Postnikov systems in fixed dimension, SIAM Journal on Computing, Volume 43 (2014) no. 5, pp. 1728-1780 | DOI | MR | Zbl

[17] Čadek, Martin; Krčál, Marek; Vokřínek, Lukáš Algorithmic solvability of the lifting-extension problem, Discrete & Computational Geometry (DCG), Volume 57 (2017) no. 4, pp. 915-965 | DOI | MR | Zbl

[18] Cardinal, Jean; Felsner, Stefan; Miltzow, Tillmann; Tompkins, Casey; Vogtenhuber, Birgit Intersection Graphs of Rays and Grounded Segments, Journal of Graph Algorithms and Applications, Volume 22 (2018) no. 2, pp. 273-294 | DOI | MR | Zbl

[19] Chistikov, Dmitry; Kiefer, Stefan; Marusic, Ines; Shirmohammadi, Mahsa; Worrell, James On Restricted Nonnegative Matrix Factorization, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) (LIPIcs), Volume 55 (2016), p. 103:1-103:14 | DOI | MR | Zbl

[20] Dey, T. K.; Pach, János Extremal Problems for Geometric Hypergraphs, Discrete & Computational Geometry, Volume 19 (1998) no. 4, pp. 473-484 | DOI | MR | Zbl

[21] Dobbins, Michael G.; Holmsen, Andreas; Miltzow, Tillmann A Universality Theorem for Nested Polytopes (2019) | arXiv | DOI

[22] Dobbins, Michael G.; Kleist, Linda; Miltzow, Tillmann; Rzążewski, Paweł Completeness for the Complexity Class ∀∃ℝ and Area-Universality, Discrete & Computational Geometry (DCG), Volume 70 (2022) no. 1, pp. 154-188 | DOI | MR | Zbl

[23] Erickson, Jeff Optimal Curve Straightening is ∃ℝ-Complete (2019) | arXiv | DOI

[24] Erickson, Jeff; van der Hoog, Ivor; Miltzow, Tillmann Smoothing the gap between NP and ∃ℝ, IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS 2020) (2020), pp. 1022-1033 | DOI | MR

[25] Evans, William; Rzążewski, Paweł; Saeedi, Noushin; Shin, Chan-Su; Wolff, Alexander Representing Graphs and Hypergraphs by Touching Polygons in 3D,, Graph Drawing and Network Visualization (GD 2019) (2019), pp. 18-32 | DOI | Zbl

[26] Gardi, Frédéric The Roberts characterization of proper and unit interval graphs, Discrete Mathematics, Volume 307 (2007) no. 22, pp. 2906-2908 | DOI | MR | Zbl

[27] Garg, Jugal; Mehta, Ruta; Vazirani, Vijay V.; Yazdanbod, Sadra ∃ℝ-Completeness for Decision Versions of Multi-Player (Symmetric) Nash Equilibria, ACM Transactions on Economics and Computation, Volume 6 (2018) no. 1, Paper no. 1, 23 pages | DOI | MR

[28] Habib, Michel; McConnell, Ross; Paul, Christophe; Viennot, Laurent Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing, Theoretical Computer Science, Volume 234 (2000) no. 1, pp. 59-84 | DOI | MR | Zbl

[29] Haussler, David; Welzl, Emo ε-nets and simplex range queries, Discrete & Computational Geometry (1987), pp. 127-151 | DOI | MR | Zbl

[30] Hoffmann, Michael; Miltzow, Tillmann; Weber, Simon; Wulf, Lasse Recognition of Unit Segment Graphs is ∃ℝ-complete (Unpublished, in preparation.)

[31] Jungeblut, Paul; Kleist, Linda; Miltzow, Tillmann The Complexity of the Hausdorff Distance, 38th International Symposium on Computational Geometry (SoCG 2022) (LIPIcs), Volume 224 (2022), p. 48:1-48:17 | DOI | MR | Zbl

[32] Kakeya, Sôichi On some properties of convex curves and surfaces, Tohoku Mathematical Journal, First Series, Volume 8 (1915), pp. 218-221 https://www.jstage.jst.go.jp/article/tmj1911/8/0/8_0_218/_pdf/-char/ja

[33] Kang, Ross J.; Müller, Tobias Sphere and Dot Product Representations of Graphs, Discrete & Computational Geometry, Volume 47 (2012) no. 3, pp. 548-568 | DOI | MR | Zbl

[34] Kratochvíl, Jan; Matoušek, Jiří Intersection Graphs of Segments, Journal of Combinatorial Theory, Series B, Volume 62 (1994) no. 2, pp. 289-315 | DOI | MR | Zbl

[35] Looges, Peter J.; Olariu, Stephan Optimal greedy algorithms for indifference graphs, Computers & Mathematics with Applications, Volume 25 (1993) no. 7, pp. 15-25 | DOI | MR | Zbl

[36] Lubiw, Anna; Miltzow, Tillmann; Mondal, Debajyoti The Complexity of Drawing a Graph in a Polygonal Region, Graph Drawing and Network Visualization (GD 2018) (LNCS), Volume 11282 (2018), pp. 387-401 | DOI | MR | Zbl

[37] Ma, Lihong Bisectors and Voronoi Diagrams for Convex Distance Functions, Ph. D. Thesis, FernUniversität Hagen (2000) https://ub-deposit.fernuni-hagen.de/receive/mir_mods_00000857

[38] Matoušek, Jiří; Sedgwick, Eric; Tancer, Martin; Wagner, Uli Embeddability in the 3-sphere is decidable, Journal of the ACM, Volume 65 (2018) no. 1, pp. 1-49 | DOI | MR

[39] Matoušek, Jiří; Seidel, Raimund; Welzl, Emo How to Net a Lot with Little: Small ϵ-Nets for Disks and Halfspaces, Sixth Annual Symposium on Computational Geometry (SoCG 1990) (1990), pp. 16-22 | DOI

[40] Matoušek, Jiří; Tancer, Martin; Wagner, Uli Hardness of embedding simplicial complexes in ℝ d , JEMS, Volume 13 (2011) no. 2, pp. 259-295 | DOI | Zbl

[41] McDiarmid, Colin; Müller, Tobias Integer realizations of disk and segment graphs, Journal of Combinatorial Theory, Series B, Volume 103 (2013) no. 1, pp. 114-143 | DOI | MR | Zbl

[42] Mesmay, Arnaud de; Rieck, Yo’av; Sedgwick, Eric; Tancer, Martin Embeddability in ℝ 3 is NP-hard, Journal of the ACM, Volume 67 (2020) no. 4, Paper no. 20, 29 pages | DOI | MR | Zbl

[43] Miltzow, Tillmann; Schmiermann, Reinier F. On Classifying Continuous Constraint Satisfaction Problems, IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS 2021) (2022), pp. 781-791 | DOI | MR

[44] Mnëv, Nikolai E. The Universality Theorems on the Classification Problem of Configuration Varieties and Convex Polytopes Varieties, Topology and Geometry — Rohlin Seminar (LNM), Volume 1346, Springer, 1988, pp. 527-543 | DOI | Zbl

[45] Nakagawa, Senkichi On some theorems regarding ellipsoid, Tohoku Mathematical Journal, First Series, Volume 8 (1915), pp. 11-13 https://www.jstage.jst.go.jp/article/tmj1911/8/0/8_0_11/_pdf/-char/ja | Zbl

[46] Pach, János; Tardos, Gábor TIGHT LOWER BOUNDS FOR THE SIZE OF EPSILON-NETS, Journal of the American Mathematical Society, Volume 26 (2013) no. 3, pp. 645-658 | DOI | MR | Zbl

[47] Pach, János; Woeginger, Gerhard Some New Bounds for Epsilon-Nets, Sixth Annual Symposium on Computational Geometry (SoCG 1990) (1990), pp. 10-15 | DOI

[48] Rautenbach, Dieter; Szwarcfiter, Jayme L. Unit and single point interval graphs, Discrete Applied Mathematics, Volume 160 (2012) no. 10-11, pp. 1601-1609 | DOI | MR | Zbl

[49] Richter-Gebert, Jürgen; Ziegler, Günter M. Realization Spaces of 4-Polytopes are Universal, Bulletin of the American Mathematical Society, Volume 32 (1995) no. 4, pp. 403-412 | DOI | MR | Zbl

[50] Schaefer, Marcus Complexity of Some Geometric and Topological Problems, Graph Drawing, Springer (2010), pp. 334-344 | DOI | Zbl

[51] Schaefer, Marcus Realizability of Graphs and Linkages, Thirty Essays on Geometric Graph Theory, Springer (2013), pp. 461-482 | DOI

[52] Schaefer, Marcus Complexity of Geometric k-Planarity for Fixed k, Journal of Graph Algorithms and Applications, Volume 25 (2021) no. 1, pp. 29-41 | DOI | MR | Zbl

[53] Schaefer, Marcus; Cardinal, Jean; Miltzow, Tillmann The existential theory of the reals as a complexity class: A compendium (2024) | arXiv | DOI

[54] Schaefer, Marcus; Sedgwick, Eric; Štefankovič, Daniel Recognizing string graphs in NP, Journal of Computer and System Sciences, Volume 67 (2003) no. 2, pp. 365-380 | DOI | MR | Zbl

[55] Schaefer, Marcus; Štefankovič, Daniel Fixed Points, Nash Equilibria, and the Existential Theory of the Reals, Theory of Computing Systems, Volume 60 (2017), pp. 172-193 | DOI | MR | Zbl

[56] Schaefer, Marcus; Štefankovič, Daniel The Complexity of Tensor Rank, Theory of Computing Systems, Volume 62 (2018) no. 5, pp. 1161-1174 | DOI | MR | Zbl

[57] Shitov, Yaroslav A Universality Theorem for Nonnegative Matrix Factorizations (2016) | arXiv | DOI

[58] Shitov, Yaroslav The Complexity of Positive Semidefinite Matrix Factorization, SIAM Journal on Optimization, Volume 27 (2017) no. 3, pp. 1898-1909 | DOI | MR | Zbl

[59] Shor, Peter W. Stretchability of Pseudolines is NP-Hard., Applied Geometry And Discrete Mathematics (Gritzmann, Peter; Sturmfels, Bernd, eds.) (DIMACS Series in Discrete Mathematics and Theoretical Computer Science), Volume 4 (1991), pp. 531-554 | DOI | Zbl

[60] Skopenkov, Arkadiy Extendability of simplicial maps is undecidable (2020) | arXiv | DOI

[61] Smorodinsky, Shakhar On the chromatic number of geometric hypergraphs, SIAM Journal of Discrete Mathematics, Volume 21 (2007) no. 3, pp. 676-687 | DOI | MR | Zbl

[62] Spinrad, Jeremy Recognition of circle graphs, Journal of Algorithms, Volume 16 (1994) no. 2, pp. 264-282 | DOI | MR | Zbl

[63] Stade, Jack Complexity of the boundary-guarding art gallery problem (2022) | arXiv | DOI

[64] Tanenbaum, Paul J.; Goodrich, Michael T.; Scheinerman, Edward R. Characterization and recognition of point-halfspace and related orders, Graph Drawing, Springer (1995), pp. 234-245 | DOI

[65] Tuncel, Levent; Vavasis, Stephen; Xu, Jingye Computational complexity of decomposing a symmetric matrix as a sum of positive semidefinite and diagonal matrices (2022) | arXiv | DOI

Cited by Sources: