Parameterized Algorithms for the Subgraph Isomorphism Problem
Zachary Frenette · 2014
Given two undirected graphs F and G, the subgraph isomorphism problem asks whether there exists a subgraph of G that is isomorphic to F . Although NP-complete [7], this problem has been very well studied in a variety of settings, particularly in the context of parameterized complexity. In 1978, Matula showed that the subgraph isomorphism problem is solvable in polynomial time when both F and G are trees [13]. Moreover, it was later shown by Matousek and Thomas that the problem remains NP-complete, even when F and G have treewidth at most two [12]. Despite this result, many other papers have tackled the subgraph isomorphism problem when parameterized by treewidth. For example, by introducing the notion of color coding, Alon, Yuster, and Zwick gave an algorithm requiring exponential time and space to solve the subgraph isomorphism problem when F has bounded treewidth [1]. Amini, Fomin, and Saurabh improved upon this result and presented an algorithm requiring a polynomial amount of space by combining the ideas of color coding and counting graph homomorphisms [2]. Furthermore, many of these techniques and ideas have since been adapted to create parameterized algorithms for the counting version of the subgraph isomorphism problem. In particular, by taking ideas from algebraic combinatorics and combining them with the notion of graph homomorphisms and dynamic programming, new algorithms have been developed for both the decision and counting version of the problem when parameterized by treewidth or pathwidth [2, 8, 9]. Although none of these results are fixed parameter tractable with respect to treewidth, there has been a substantial amount of work done in finding sets of parameters for which the problem does become fixed parameter tractable. In particular, Marx and Pilipczuk presented a series of results in which they provide reductions between different sets of parameters. Using these reductions, they then characterize under which parameterizations the subgraph isomorphism problem becomes fixed parameter tractable [11].