Count on CFI graphs for #P-hardness

Research output: Conference Article in Proceeding or Book/Report chapterArticle in proceedingsResearchpeer-review

Abstract

A homomorphism between graphs H and G, possibly with vertex-colors, is a function f : V(ℋ) → V(G) that preserves colors and edges. Many interesting graph parameters are finite linear combinations p(·) = Ση αH hom(ℋ, ·) of homomorphism counts from fixed pattern graphs H; this includes (induced) subgraph counts for fixed patterns. Interpreting graph parameters as linear combinations of homomorphism counts has proven to be useful in understanding their computational complexity, as it is known that such linear combinations are as hard to evaluate as their hardest terms, whose complexity in turn is governed by the treewidth of the pattern graph. More formally, given oracle access to a linear combination of homomorphism counts p as above and a graph S with coefficient αs ≠ 0, it is possible to compute hom(S, G) for any n-vertex input graph G in 2|E(S)|poly(s, n) time, where s is the maximum size of graphs in the defining linear combination of p. This reduction runs in polynomial time when p and S are fixed or small in comparison to G; this is the relevant setting in several results based on this reduction.
In this paper, we show that a similar reduction can be performed in poly(n, s) time even if S is part of the input, provided that S has constant maximum degree. Our polynomial-time reduction is based on graph products with Cai-Fürer-Immerman graphs, a novel technique that is likely of independent interest in algorithms and complexity. The new reduction yields #P-hardness results for problems that could previously only be studied under parameterized complexity assumptions such as FPT ≠ #W[1], which are a priori stronger than classical assumptions. This includes the problems #Hom(ℋ), #Sub(ℋ) and #Ind(ℋ) for fixed graph classes H satisfying natural polynomial-time enumerability conditions, which ask to count homomorphisms from H to G or (induced) subgraph copies of H in G, given as input a graph H ∈ H and a general graph G.
Original languageEnglish
Title of host publicationProceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024
PublisherSociety for Industrial and Applied Mathematics
Publication date2024
Pages1854 - 1871
ISBN (Electronic)978-1-61197-791-2
DOIs
Publication statusPublished - 2024

Keywords

  • counting complexity
  • Cai-Fürer-Immerman graphs
  • graph homomorphisms

Fingerprint

Dive into the research topics of 'Count on CFI graphs for #P-hardness'. Together they form a unique fingerprint.

Cite this