Recognition of Unit Segment and Polyline Graphs is $\exists \mathbb {R} $-Complete

Michael Hoffmann, Tillmann Miltzow, Simon Weber, Lasse WulfWG 2024 · DOI

TL;DR

This paper tackles the problem of recognizing intersection graphs formed by unit segments and polylines with a fixed number of bends. The authors prove that for both these geometric object families, the recognition problem is $\exists \mathbb{R}$-complete, a complexity class related to the solvability of real polynomial systems. This result fills a gap in the understanding of geometric graph recognition complexity.

What Problem Does This Paper Address?

In computational geometry, a fundamental question is whether a given graph can be represented as the intersection graph of a specific set of geometric objects. For example, can a graph be formed by the intersections of unit disks or line segments? The complexity of these "recognition problems" varies greatly depending on the geometric objects. While many such problems are well-understood, the recognition of graphs formed by unit segments and polylines with a fixed number of bends remained open. These objects are considered "natural" and have been studied extensively. This paper aims to resolve the complexity of these two specific recognition problems, placing them within the hierarchy of known geometric graph recognition complexities.

Methods

The paper establishes $\exists \mathbb{R}$-completeness for both unit segment and k-polyline recognition. This involves two main parts: $\exists \mathbb{R}$-membership and $\exists \mathbb{R}$-hardness.

  • $\exists \mathbb{R}$-Membership: This is shown by constructing explicit formulas in the existential theory of the reals (ETR) that capture the problem. Alternatively, they describe a "real witness and verification algorithm" approach. The witness is the geometric realization (coordinates of segments/polylines), and the verifier checks unit lengths, intersections, and connectivity.
  • $\exists \mathbb{R}$-Hardness: This is proven via reductions from the STRETCHABILITY problem. The core idea is to take a pseudoline arrangement (a set of curves that behave like lines but can be "bent" to achieve a specific combinatorial structure) and construct a graph whose intersection graph can be represented by unit segments (or k-polylines) if and only if the original pseudoline arrangement is stretchable. This construction involves adding "probes," "connectors," and a "cycle" to the pseudoline arrangement to create a graph with specific structural properties. Key lemmas are used to relate the combinatorial structure of the pseudoline arrangement to the geometric realization of the constructed graph. For polylines, the construction is extended to handle bends, ensuring that the critical part of the arrangement remains "straight" to leverage the unit segment proof.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Bridging the Gap: The paper places polylines with a fixed number of bends as an intermediate class between segments (0 bends) and strings (unbounded bends) in terms of recognition complexity. This refines the understanding of how geometric complexity influences algorithmic complexity.
  • The "Sweet Spot": The authors suggest that $\exists \mathbb{R}$-completeness arises for geometric objects that are neither too simple (allowing polynomial-time recognition) nor too flexible (leading to NP-completeness). Unit segments and k-polylines fall into this "sweet spot."
  • Cycle Representations: The use of induced cycles in the constructed graphs is crucial. These cycles enforce specific ordering constraints on the geometric objects in any realization, which is key to proving the reduction's correctness.
  • Probes and Connectors: The clever use of "probes" and "connectors" in the reduction construction allows for the translation of combinatorial properties of pseudoline arrangements into geometric intersection properties of segments and polylines.

Key Results

  • Theorem 1: Recognition of unit segment intersection graphs is $\exists \mathbb{R}$-complete.
  • Theorem 2: Recognition of k-polyline intersection graphs (for any fixed $k \ge 0$) is $\exists \mathbb{R}$-complete.

Limitations and Future Work

  • Bounded Degree Conjecture: The authors conjecture that unit segment recognition remains $\exists \mathbb{R}$-complete even for graphs of bounded degree. This would be a significant refinement, but their current reduction creates graphs of unbounded degree.
  • Curvature and Rotation: They speculate that $\exists \mathbb{R}$-completeness might be related to the "curvature" or "rotation" of geometric objects, suggesting that objects allowing for these properties tend to lead to $\exists \mathbb{R}$-complete recognition problems.
  • Exact Degree Threshold: For bounded degree graphs, finding the exact degree threshold where recognition becomes easy is an open question.

Summary updated

BibTeX
@inproceedings{hoffmann2024recognition,
  author = {Michael Hoffmann and Tillmann Miltzow and Simon Weber and Lasse Wulf},
  title = {{Recognition of Unit Segment and Polyline Graphs is $\textbackslash\{\}exists \textbackslash\{\}mathbb \{R\} $-Complete}},
  booktitle = {WG},
  year = {2024},
  doi = {10.1007/978-3-031-75409-8\_19},
}
Figure