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

Daniel Paul-Pena, C. Seshadhri

TL;DR

This paper introduces a "dichotomy theorem" for counting graph homomorphisms, a fundamental problem in computer science with applications in various fields. It establishes a clear condition based on the structure of a small "pattern graph" that determines whether counting these relationships can be done efficiently (in near-linear time) for large, sparse "input graphs." This work provides a precise characterization for when this computationally challenging task becomes tractable.

What Problem Does This Paper Address?

Counting the number of ways a small graph (the "pattern graph" H) can be mapped onto a larger graph (the "input graph" G) while preserving structure is a core problem in graph theory and computer science. This "homomorphism counting" has applications in areas like bioinformatics, database querying, and network analysis. Beyond just the total count, researchers are increasingly interested in "orbit counting": for each vertex in the large graph G, how many homomorphisms map it to a specific "role" or "orbit" within the pattern graph H. This provides a more granular understanding of graph structure.

The challenge lies in efficiency. For general graphs, these counting problems are computationally very hard. However, many real-world graphs are "sparse" and have "bounded degeneracy," meaning they have a lot of structure that can be exploited. The paper asks: for these sparse graphs, what property of the pattern graph H determines if we can count H-homomorphism orbits efficiently (in near-linear time)?

Methods

The paper's core contribution is a dichotomy theorem. This means they've found a property of the pattern graph H that perfectly divides all possible pattern graphs into two categories: those for which orbit counting is efficient, and those for which it's provably hard (assuming certain widely-held complexity conjectures).

The key property they identify is the Longest Induced Path Connecting Orbits (LIPCO) of H. This measures the longest path within H that connects two vertices within the same orbit (meaning they can be swapped by an automorphism of H) and where no intermediate vertices are connected by edges outside this path.

The proof involves several sophisticated techniques:

  • Acyclic Orientations: They leverage the fact that bounded degeneracy graphs can be efficiently "acyclically oriented," which simplifies the problem.
  • DAG-tree Decompositions: Building on prior work, they use a technique called DAG-tree decomposition to break down the pattern graph into smaller, manageable pieces.
  • Inclusion-Exclusion: A crucial part of their algorithm for the "efficient" case involves an inclusion-exclusion principle to convert vertex-centric counts (counting homomorphisms for specific vertex mappings) into orbit counts.
  • Fine-grained Complexity: For the "hard" case, they rely on established conjectures in fine-grained complexity, particularly the Triangle Detection Conjecture, to prove lower bounds on computation time.

Datasets

Not discussed in the paper. The paper focuses on theoretical characterizations and algorithmic complexity rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • The LIPCO Threshold: The most striking insight is the sharp threshold of 5 for the LIPCO. If LIPCO(H) ≤ 5, efficient orbit counting is possible for bounded degeneracy graphs. If LIPCO(H) > 5, it's provably hard. This is a clean, structural characterization.
  • Dichotomy for Orbit Counting vs. Total Counting: The paper highlights that the condition for efficient orbit counting (LIPCO ≤ 5) is different from the condition for efficient total homomorphism counting (longest induced cycle length ≤ 5). This means that for some pattern graphs, counting orbits is strictly harder than counting the total number of homomorphisms, a surprising separation.
  • Structural Properties Dictate Complexity: The research demonstrates that the complexity of a graph problem can be precisely determined by simple structural properties of the input pattern graph, even for complex counting tasks.

Key Results

  • Dichotomy Theorem: The paper presents a dichotomy theorem:
  • If LIPCO(H) ≤ 5, then H-homomorphism orbit counting can be computed in near-linear time for bounded degeneracy graphs.
  • If LIPCO(H) > 5, then (assuming fine-grained complexity conjectures) no near-linear time algorithm exists for this problem.
  • Algorithm for Efficient Case: They provide a deterministic algorithm that computes orbit counts in O(mlog n) time when LIPCO(H) ≤ 5, where m is the number of edges and n is the number of vertices in the input graph G.
  • Lower Bound for Hard Case: They establish a lower bound showing that for LIPCO(H) > 5, the problem is computationally hard, requiring at least Ω(m¹⁺γ) time for some constant γ > 0, assuming the Triangle Detection Conjecture.

Limitations and Future Work

  • Bounded Degeneracy Assumption: The results are specifically for graphs with bounded degeneracy. Extending these findings to general graphs would be a significant challenge.
  • Fine-grained Complexity Dependence: The lower bound relies on the Triangle Detection Conjecture. While widely believed, it's still a conjecture.
  • Constant Factors: The paper focuses on asymptotic near-linear time complexity. The exact constant factors in the algorithms and lower bounds, especially those dependent on the pattern graph's size, are not the primary focus but could be important for practical performance.
  • Future Work: The authors suggest exploring similar dichotomy theorems for other graph counting problems and investigating the precise role of LIPCO in other graph-related computational tasks. They also hint at the possibility of extending these results to slightly more general graph classes beyond 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