A Dichotomy Theorem for Linear Time Homomorphism Orbit Counting in Bounded Degeneracy Graphs

Daniel Paul-Pena, C. Seshadhri

Abstract

Counting the number of homomorphisms of a pattern graph $H$ in a large input graph $G$ is a fundamental problem in computer science. There are myriad applications of this problem in databases, graph algorithms, and network science. Often, we need more than just the total count. Especially in large network analysis, we wish to compute, for each vertex $v$ of $G$, the number of $H$-homomorphisms that $v$ participates in. This problem is referred to as homomorphism orbit counting, as it relates to the orbits of vertices of $H$ under its automorphisms. Given the need for fast algorithms for this problem, we study when near-linear time algorithms are possible. A natural restriction is to assume that the input graph $G$ has bounded degeneracy, a commonly observed property in modern massive networks. Can we characterize the patterns $H$ for which homomorphism orbit counting can be done in linear time? We discover a dichotomy theorem that resolves this problem. For pattern $H$, let $l$ be the length of the longest induced path between any two vertices of the same orbit (under the automorphisms of $H$). If $l \le 5$, then $H$-homomorphism orbit counting can be done in linear time for bounded degeneracy graphs. If $l > 5$, then (assuming fine-grained complexity conjectures) there is no near-linear time algorithm for this problem. We build on existing work on dichotomy theorems for counting the total $H$-homomorphism count. Somewhat surprisingly, there exist (and we characterize) patterns $H$ for which the total homomorphism count can be computed in linear time, but the corresponding orbit counting problem cannot be done in near-linear time.

Introduction

In the study of large-scale networks, such as social graphs or biological interactomes, understanding the local structure around individual vertices is crucial. While counting the total occurrences of a motif (like a triangle or a clique) provides a global signature, "orbit counting" offers a more granular view. It identifies the specific roles—formally known as orbits—that a vertex plays within a pattern. For instance, in a simple path $A-B-C$, the central vertex $B$ plays a different role than the endpoints $A$ and $C$.

This paper addresses the computational complexity of orbit counting in bounded degeneracy graphs. Degeneracy is a measure of sparseness; a graph has bounded degeneracy if every subgraph contains a vertex with a small degree. This property is ubiquitous in real-world networks, making it a natural setting for developing efficient algorithms. The authors establish a sharp dichotomy theorem that separates patterns $H$ that can be counted in near-linear time from those that are likely intractable.

Understanding Orbits and Homomorphisms

A homomorphism from a pattern $H$ to an input graph $G$ is a mapping that preserves adjacency. An orbit of $H$ is a set of vertices that are equivalent under the graph's symmetries (automorphisms).

Orbits of a 7-vertex path graph. Vertices with the same color belong to the same orbit. For the red orbit (endpoints), the longest induced path between them has length 6.

As shown in the figure above, a 7-vertex path has four orbits. The challenge lies in the fact that while counting the total number of such paths might be easy, counting how many times a specific vertex in $G$ acts as an endpoint (the red orbit) can be significantly harder.

The Dichotomy Theorem and the LIPCO Parameter

The core of the paper is the introduction of the Longest Induced Path Connecting Orbits (LIPCO) parameter. For a pattern $H$, $LIPCO(H)$ is defined as the length (number of edges) of the longest induced path between any two vertices belonging to the same orbit.

Comparison of pattern graphs. The top 7-vertex path has a LIPCO of 6 (hard), while the bottom graph has a smaller LIPCO (easy) because its symmetric vertices are closer together.

The authors prove a definitive threshold for complexity:

  • The Easy Case ($LIPCO(H) \le 5$): There exists a deterministic algorithm to compute all orbit counts in $O(m \log n)$ time, where $m$ is the number of edges in $G$.
  • The Hard Case ($LIPCO(H) > 5$): Assuming the Triangle Detection Conjecture, no near-linear time algorithm exists for these patterns.

This result is surprising because it identifies patterns, like the 7-vertex path ($LIPCO=6$), where global counting is linear but orbit counting hits a complexity wall.

Algorithmic Framework

To achieve near-linear time for the "easy" cases, the authors employ several advanced techniques:

  1. Acyclic Orientations: They exploit bounded degeneracy to orient edges into a Directed Acyclic Graph (DAG) with small out-degrees.
  2. DAG-tree Decompositions: They use specialized decompositions to break $H$ into manageable components for dynamic programming.
  3. Inclusion-Exclusion for Orbits: Standard methods provide vertex-centric counts (how many times $v$ maps to a specific $h \in H$). The authors developed a novel inclusion-exclusion formula to "invert" these into exact orbit counts, correctly handling the symmetries of $H$.

Hardness and Future Work

The hardness result for $LIPCO(H) > 5$ is tied to fine-grained complexity. If a near-linear algorithm existed for these cases, it would imply a faster-than-expected solution to the triangle detection problem, a fundamental challenge in computer science.

While the algorithm is theoretically efficient, the constant factors scale exponentially with the size of the pattern $H$ and the degeneracy of $G$. Future research may focus on optimizing these constants for practical use or extending the dichotomy to graph classes beyond those with bounded degeneracy.

Summary updated

Abstract

Counting the number of homomorphisms of a pattern graph H in a large input graph G is a fundamental problem in computer science. There are myriad applications of this problem in databases, graph algorithms, and network science. Often, we need more than just the total count. Especially in large network analysis, we wish to compute, for each vertex v of G, the number of H-homomorphisms that v participates in. This problem is referred to as homomorphism orbit counting, as it relates to the orbits of vertices of H under its automorphisms. Given the need for fast algorithms for this problem, we study when near-linear time algorithms are possible. A natural restriction is to assume that the input graph G has bounded degeneracy, a commonly observed property in modern massive networks. Can we characterize the patterns H for which homomorphism orbit counting can be done in linear time? We discover a dichotomy theorem that resolves this problem. For pattern H, let l be the length of the longest induced path between any two vertices of the same orbit (under the automorphisms of H). If l <= 5, then H-homomorphism orbit counting can be done in linear time for bounded degeneracy graphs. If l > 5, then (assuming fine-grained complexity conjectures) there is no near-linear time algorithm for this problem. We build on existing work on dichotomy theorems for counting the total H-homomorphism count. Somewhat surprisingly, there exist (and we characterize) patterns H for which the total homomorphism count can be computed in linear time, but the corresponding orbit counting problem cannot be done in near-linear time.
BibTeX
@inproceedings{paulpena2024dichotomy,
  author = {Daniel Paul-Pena and C. Seshadhri},
  title = {{A Dichotomy Theorem for Linear Time Homomorphism Orbit Counting in Bounded Degeneracy Graphs}},
  booktitle = {ISAAC},
  year = {2024},
  doi = {10.4230/lipics.isaac.2024.54},
}
Figure