• with Shiteng Chen, Radu Curticapean, and Prateek Dwivedi
  • MFCS 2025

PDF · arXiv

For every fixed graph , it is known that homomorphism counts from and colorful -subgraph counts can be determined in time on -vertex input graphs , where is the treewidth of . On the other hand, a running time of would refute the exponential-time hypothesis. Komarath, Pandey and Rahul (Algorithmica, 2023) studied algebraic variants of these counting problems, i.e., homomorphism and subgraph polynomials for fixed graphs . These polynomials are weighted sums over the objects counted above, where each object is weighted by the product of variables corresponding to edges contained in the object. As shown by Komarath \emph{et al.}, the monotone circuit complexity of the homomorphism polynomial for is .

In this paper, we characterize the power of monotone bounded-depth circuits for homomorphism and colorful subgraph polynomials. This leads us to discover a natural hierarchy of graph parameters , for fixed , which capture the width of tree-decompositions for when the underlying tree is required to have depth at most . We prove that monotone circuits of product-depth computing the homomorphism polynomial for require size , where is the graph obtained from by removing all degree- vertices. This allows us to derive an optimal depth hierarchy theorem for monotone bounded-depth circuits through graph-theoretic arguments.

Research overview