Counting and Finding Homomorphisms is Universal for Parameterized Complexity Theory

Counting homomorphisms from a graph H into another graph G is a fundamental problem of (parameterized) counting complexity theory. In this work, we study the case where both graphs H and G stem from given classes of graphs: H ∈ H and G ∈ G. By this, we combine the structurally restricted version of this problem (where the class G = is the set of all graphs), with the languagerestricted version (where the class H = is the set of all graphs). The structurally restricted version allows an exhaustive complexity classification for classes H: Either we can count all homomorphisms in polynomial time (if the treewidth of H is bounded), or the problem becomes #W[1]-hard [Dalmau, Jonsson, Th.Comp.Sci'04]. In contrast, in this work, we show that the combined view most likely does not admit such a complexity dichotomy.

Our main result is a construction based on Kneser graphs that associates every problem P in #W[1] with two classes of graphs H and G such that the problem P is equivalent to the problem #Hom(H → G) of counting homomorphisms from a graph in H to a graph in G. In view of Ladner's seminal work on the existence of NP-intermediate problems [J.ACM'75] and its adaptations to the parameterized setting, a classification of the class #W[1] in fixed-parameter tractable and #W[1]complete cases is unlikely. Hence, obtaining a complete classification for the problem #Hom(H → G) seems unlikely. Further, our proofs easily adapt to W[1] and the problem of deciding whether a homomorphism between graphs exists.

In search of complexity dichotomies, we hence turn to special graph classes. Those classes include line graphs, claw-free graphs, perfect graphs, and combinations thereof, and F -colorable graphs for fixed graphs F : If the class G is one of those classes and the class H is closed under taking minors, then we establish explicit criteria for the class H that partition the family of problems #Hom(H → G) into polynomial-time solvable and #W[1]-hard cases. In particular, we can drop the condition of H being minor-closed for F -colorable graphs. As a consequence, we are able to lift the framework of graph motif parameters due to Curticapean, Dell and Marx [STOC'17] to F -colorable graphs and provide an exhaustive classification for the parameterized subgraph counting problem on F -colorable graphs. As a special case, we obtain an easy proof of the parameterized intractability result of the problem of counting k-matchings in bipartite graphs.