Projects per year
Abstract
A homomorphism between graphs H and G, possibly with vertexcolors, 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 nvertex input graph G in 2E(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 polynomialtime reduction is based on graph products with CaiFürerImmerman graphs, a novel technique that is likely of independent interest in algorithms and complexity. The new reduction yields #Phardness 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 polynomialtime 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.
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 polynomialtime reduction is based on graph products with CaiFürerImmerman graphs, a novel technique that is likely of independent interest in algorithms and complexity. The new reduction yields #Phardness 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 polynomialtime 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 language  English 

Title of host publication  Proceedings of the 2024 ACMSIAM Symposium on Discrete Algorithms, SODA 2024 
Publisher  Society for Industrial and Applied Mathematics 
Publication date  2024 
Pages  1854  1871 
ISBN (Electronic)  9781611977912 
DOIs  
Publication status  Published  2024 
Keywords
 counting complexity
 CaiFürerImmerman graphs
 graph homomorphisms
Fingerprint
Dive into the research topics of 'Count on CFI graphs for #Phardness'. Together they form a unique fingerprint.
CountBeyond: Beyond Exact Counting: Approximation and Symmetry
Curticapean, R.C. (PI)
01/06/2023 → 30/09/2023
Project: Research

CountHom: Counting (with) homomorphisms
Curticapean, R.C. (PI)
01/04/2023 → 31/03/2028
Project: Research