2019/07/08 by Marc Roth, Roth, Marc, Philip Wellnitz +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Markov Chains and Monte Carlo Methods #Topological and Geometric Data Analysis
paper · pdf · doi:10.48550/arxiv.1907.03850
openalex publication_date 2019/07/08 · openalex created_date 2022/07/28 · openalex updated_date 2026/07/28
Counting homomorphisms from a graph H into another graph G is a\nfundamental problem of (parameterized) counting complexity theory. In this\nwork, we study the case where \both graphs H and G stem from given\nclasses of graphs: H\∈ \H and G\∈ \G. By this, we\ncombine the structurally restricted version of this problem, with the\nlanguage-restricted version.\n Our main result is a construction based on Kneser graphs that associates\nevery problem tt P in #\W[1] with two classes of graphs\n\H and \G such that the problem tt P is\n\equivalent to the problem # tt HOM(\H\→ \G) of\ncounting homomorphisms from a graph in \H to a graph in\n\G. In view of Ladner's seminal work on the existence of\n\NP-intermediate problems [J.ACM'75] and its adaptations to the\nparameterized setting, a classification of the class #\W[1] in\nfixed-parameter tractable and #\W[1]-complete cases is unlikely.\nHence, obtaining a complete classification for the problem # tt\nHOM(\H\→ \G) seems unlikely. Further, our proofs easily\nadapt to \W[1].\n In search of complexity dichotomies, we hence turn to special graph classes.\nThose classes include line graphs, claw-free graphs, perfect graphs, and\ncombinations thereof, and F-colorable graphs for fixed graphs F: If the\nclass \G is one of those classes and the class \H is\nclosed under taking minors, then we establish explicit criteria for the class\n\H that partition the family of problems # tt\nHOM(\H\→\G) into polynomial-time solvable and\n #\W[1]-hard cases. In particular, we can drop the condition of\n\H being minor-closed for F-colorable graphs.\n