Recognizing Subgraphs of Regular Tilings

This paper presents algorithms for recognizing subgraphs of regular tilings, proving that the problem is solvable in quasi-polynomial time for hyperbolic tilings, subexponential time for Euclidean tilings, and constant time for spherical tilings, while highlighting that the Euclidean case remains NP-hard even for trees.

The Gist

Imagine you have a giant, infinite floor covered in a perfect, repeating pattern of tiles. This could be a checkerboard (squares), a honeycomb (hexagons), or a more exotic pattern that curves like a saddle. In the world of mathematics, these are called Regular Tilings.

Now, imagine you have a small, specific shape cut out of paper—a "pattern graph." It could be a simple tree, a loop, or a complex web.

The Big Question: Can you place your paper shape onto the infinite tiled floor so that every corner of your paper lands exactly on a tile corner, and every line on your paper matches a line on the floor?

This is the problem the authors, Eliel Ingervo and Sándor Kisfaludi-Bak, are trying to solve. They want to know: How hard is it to find this match?

The answer depends entirely on the shape of the floor. The authors discovered that the difficulty changes drastically depending on whether the floor is flat, round, or curved.

1. The Three Types of Floors

The authors divide the infinite floors into three categories based on how the tiles fit together:

• The Round Floor (Spherical): Think of a soccer ball. The tiles curve inward to close a loop.
  • The Verdict: These floors are tiny (finite). You can check if your shape fits in a blink of an eye. It's trivial.
• The Flat Floor (Euclidean): Think of a standard checkerboard or a honeycomb. The tiles lie flat and go on forever in straight lines.
  • The Verdict: This is hard. Even if your paper shape is just a simple tree (no loops), finding where it fits on a square grid is a nightmare for computers. It's so hard that we believe no super-fast algorithm exists for it. The authors found a "good enough" fast method, but it's still slow for very large shapes.
• The Curved Floor (Hyperbolic): Think of a Pringles chip or a coral reef. The tiles curve outward, and the space expands incredibly fast. As you move away from the center, the number of available spots grows exponentially.
  • The Verdict: Surprisingly, this is the easiest of the three! Even though the floor is infinite and complex, the authors found a clever way to solve the puzzle in "quasi-polynomial" time. This means it's much faster than the flat floor version, almost as if the curvature of the floor helps the computer cheat.

2. The Secret Weapon: The "Convex Hull" and the "Bubble"

Why is the curved floor easier?

Imagine you are trying to fit your paper shape onto the floor.

• On the Flat Floor: If you try to fit a tree, the branches can wiggle around in endless directions. There are too many possibilities.
• On the Curved Floor: The authors realized that if you draw a "bubble" (a convex hull) around your shape, the bubble has a special property. Because the floor curves outward, the bubble doesn't get huge and messy; it stays relatively compact and well-behaved.

They used a technique called Dynamic Programming. Think of this like solving a giant jigsaw puzzle by starting with the smallest pieces and snapping them together.

1. They imagine cutting the floor with a flexible, rubbery loop (a "noose").
2. They check if the paper shape fits inside the loop.
3. They shrink the loop, solve the tiny pieces, and then build back up to the full shape.

Because the "bubble" on the curved floor is so well-behaved, the computer doesn't get lost in a sea of possibilities. It can systematically check every valid way to fit the shape without getting overwhelmed.

3. The "Tree" Surprise

There is a fascinating twist. Usually, if a problem is hard for a complex shape, it's also hard for a simple shape like a tree.

• On the Flat Floor: Even a simple tree is a nightmare to fit. It's like trying to find a specific tree in a dense, flat forest where every tree looks the same and branches go in every direction.
• On the Curved Floor: Even though the floor is infinite, the "tree-likeness" of the hyperbolic geometry actually helps. The branches of the floor spread out so quickly that your paper tree has a unique "home" that is easier to find.

The Takeaway

The paper is a victory lap for Hyperbolic Geometry.

• Flat World (Euclidean): Finding patterns is hard. It's like looking for a needle in a haystack where the haystack is infinite and flat.
• Curved World (Hyperbolic): Finding patterns is surprisingly easy. The curvature acts like a guide, funneling the possibilities into a manageable path.

The authors didn't just say "it's hard" or "it's easy." They built the actual instruction manual (algorithms) for computers to solve these puzzles efficiently on curved floors, and they proved that for flat floors, we are likely stuck with the slow methods we have now.

In short: If you want to fit a shape onto an infinite floor, you're better off on a curved, saddle-shaped world than on a flat one. The curvature, which seems more complex, actually makes the math simpler!

Technical Summary

Here is a detailed technical summary of the paper "Recognizing Subgraphs of Regular Tilings" by Eliel Ingervo and Sándor Kisfaludi-Bak.

1. Problem Definition

The paper addresses the Subgraph Isomorphism and Induced Subgraph Isomorphism problems where the host graph $G$ is a fixed, infinite, highly regular planar graph known as a $\{p, q\}$-tiling graph ($T_{p,q}$).

• Structure of $T_{p,q}$: A planar graph where every face is a cycle of length $p$ and every vertex has degree $q$.
• Geometric Classification: The complexity of the tiling depends on the curvature determined by $1/p + 1/q$:
  • Spherical ($1/p + 1/q > 1/2$): Finite graphs. Recognition is trivial (constant time).
  • **Euclidean ($1/p + 1/q = 1/2$):** Infinite planar grids (e.g., square$T_{4,4}$, triangular$T_{3,6}$, hexagonal$T_{6,3}$).
  • Hyperbolic ($1/p + 1/q < 1/2$): Infinite tilings of the hyperbolic plane with exponential growth.

The input is a pattern graph $H$ with $n$ vertices. The goal is to determine if $H$ is isomorphic to a subgraph (or induced subgraph) of $T_{p,q}$.

2. Methodology and Key Technical Insights

The authors approach the problem differently for Euclidean and Hyperbolic cases, leveraging the distinct geometric properties of each.

A. Hyperbolic Tilings ($1/p + 1/q < 1/2$)

The main contribution is a quasi-polynomial time algorithm ($n^{O(\log n)}$) for fixed $q$.

• Challenge: Standard dynamic programming (DP) on tree decompositions fails because the pattern graph $H$ might have low treewidth, but the embedding into the host graph creates complex geometric overlaps. Furthermore, known treewidth bounds for subgraphs of hyperbolic tilings are $O(\log n)$, which usually suggests efficient algorithms, but the specific structure of the embedding problem prevents a direct application.
• Key Insight: Convex Hulls and Sphere Cut Decompositions.
  • Instead of using separators on $H$ directly, the authors utilize the convex hull of the embedded graph within the tiling.
  • They rely on the property that the convex hull of an $n$-vertex connected subgraph in a hyperbolic tiling has size $O(n)$ and treewidth $O(\log n)$.
  • Normalized Nooses: The algorithm uses a sphere cut decomposition (a hierarchy of "nooses" or closed curves intersecting the graph). In hyperbolic geometry, these nooses can be "normalized" to have complexity $O(\log n)$.
  • Dynamic Programming: The algorithm builds a solution by embedding subgraphs of $H$ into regions defined by these normalized nooses.
  • State Definition: The DP state is a triplet $(\nu, \phi, \bar{B})$, where:
    • $\nu$: A candidate normalized noose.
    • $\phi$: A boundary assignment mapping boundary vertices of $H$ to vertices on $\nu$.
    • $\bar{B}$: A boundary neighborhood constraint (specifying which neighbors of the boundary map to the interior).
  • Recursion: The algorithm checks if a triplet can be formed by merging two "potential children" triplets (left and right sub-regions) that are compatible under orientation-preserving isometries of the hyperbolic plane.

B. Euclidean Tilings ($1/p + 1/q = 1/2$)

The authors provide a subexponential deterministic algorithm with running time $n^{O(\sqrt{n})}$.

• Methodology: A simple Divide-and-Conquer approach.
• Separator Theorem: They utilize the fact that subgraphs of Euclidean grids (like $T_{4,4}$) admit a grid-aligned line separator of size $O(\sqrt{n})$ that splits the graph into two parts of size at most $4/5 n$.
• Algorithm:
  • The problem is restricted to a bounded square region of size $2n \times 2n$.
  • The algorithm recursively splits the region using grid-aligned lines.
  • Unlike the hyperbolic case, they do not need complex nooses; simple rectangular regions suffice.
  • The running time is derived from the recurrence $T(n) = N^{O(\sqrt{n})} \cdot T(4n/5)$, yielding $n^{O(\sqrt{n})}$.

C. Lower Bounds

• Euclidean Hardness: The paper establishes that for the square grid $T_{4,4}$, the problem is nearly optimal under the Exponential Time Hypothesis (ETH).
  • By reducing from $(3,3)$-SAT (a variant of 3-SAT) to the subgraph recognition problem, they show that an algorithm running in $2^{o(\sqrt{n})}$ would violate ETH.
  • This confirms that the problem remains hard even when the pattern graph $H$ is a tree.

3. Key Results

Tiling Type	Condition	Algorithm Complexity	Lower Bound / Hardness
Spherical	$1/p + 1/q > 1/2$| Constant Time ($O(1)$)	Trivial (Finite graphs)
Euclidean	$1/p + 1/q = 1/2$|$n^{O(\sqrt{n})}$| No$2^{o(\sqrt{n})}$ algorithm (under ETH)
Hyperbolic	$1/p + 1/q < 1/2$|$2^{O(q + q \frac{\log n}{p+q})} \cdot n^{O(1 + \frac{\log n}{p+q})}$	Open (Is it polynomial? Current best is quasi-polynomial)

• Hyperbolic Specifics: For any fixed $q$, the time is $n^{O(\log n)}$. If $q$ is constant and $p = \Omega(n^\epsilon)$, the time becomes polynomial.
• Induced Subgraphs: The results hold for both standard subgraph isomorphism and induced subgraph isomorphism.

4. Significance and Contributions

1. Complexity Separation: The paper demonstrates a surprising complexity gap between Euclidean and Hyperbolic regular tilings. While Euclidean grid subgraph recognition is likely hard (requiring $n^{\Omega(\sqrt{n})}$), Hyperbolic tiling recognition is significantly easier (quasi-polynomial), despite the infinite nature and exponential growth of the host graph.
2. Novel Algorithmic Technique: The introduction of convex hulls within tiling graphs as a mechanism to define separators for dynamic programming is a major technical breakthrough. It bypasses the limitations of standard treewidth-based approaches by exploiting the specific geometric properties of hyperbolic tilings (specifically, that convex hulls of subgraphs remain small and have low treewidth).
3. Refutation of Intuition: It challenges the intuition that "low treewidth of the pattern graph" implies easy subgraph isomorphism. In Euclidean grids, even tree patterns are hard. In Hyperbolic tilings, the geometric structure of the host graph (exponential expansion) allows for efficient decomposition, making the problem tractable.
4. Practical Implications: The results are relevant for graph drawing, visualization in hyperbolic space (common in network analysis and machine learning), and understanding the computational limits of pattern matching in regular structures.

5. Open Questions

The authors conclude by highlighting several open problems:

• Can the hyperbolic algorithm be improved to polynomial time ($n^{O(1)}$)?
• Can these techniques be extended to general Gromov-hyperbolic planar graphs?
• Are there subexponential algorithms for higher-dimensional regular tilings?