Subgraph Isomorphism on Graph Classes that Exclude a Substructure

Abstract

We study Subgraph Isomorphism on graph classes defined by a fixed forbidden graph. Although there are several ways for forbidding a graph, we observe that it is reasonable to focus on the minor relation since other well-known relations lead to either trivial or equivalent problems. When the forbidden minor is connected, we present a near dichotomy of the complexity of Subgraph Isomorphism with respect to the forbidden minor, where the only unsettled case is the path of five vertices. We then also consider the general case of possibly disconnected forbidden minors. We show in particular that: the problem is fixed-parameter tractable parameterized by the size of the forbidden minor H when H is a linear forest such that at most one component has four vertices and all other components have three or less vertices; and it is NP-complete if H contains four or more components with at least five vertices each. As a byproduct, we show that Subgraph Isomorphism is fixed-parameter tractable parameterized by vertex integrity. Using similar techniques, we also observe that Subgraph Isomorphism is fixed-parameter tractable parameterized by neighborhood diversity.

Partially supported by NETWORKS (the Networks project, funded by the Netherlands Organization for Scientific Research NWO), the ELC project (the project Exploring the Limits of Computation, funded by MEXT), JSPS/MEXT KAKENHI grant numbers JP24106004, JP18K11168, JP18K11169, JP18H04091, JP18H06469, JP15K00009, JST CREST Grant Number JPMJCR1402, and Kayamori Foundation of Informational Science Advancement. The authors thank Momoko Hayamizu, Kenji Kashiwabara, Hirotaka Ono, Ryuhei Uehara, and Koichi Yamazaki for helpful discussions. The authors are grateful to the anonymous reviewer of an earlier version of this paper who pointed out a gap in a proof.

1 Introduction

Let Q and G be graphs. A subgraph isomorphism $\eta$ is an injection from V(Q) to V(G) that preserves the adjacency in Q; that is, if $\{u,v\} \in E(Q)$, then $\{\eta (u),\eta (v)\} \in E(G)$. We say that Q is subgraph-isomorphic to G if there is a subgraph isomorphism from Q to G, and write $Q \preceq G$. In this paper, we study the following problem of deciding the existence of a subgraph isomorphism.

The problem Subgraph Isomorphism is one of the most general and fundamental graph problems and generalizes many other graph problems such as Graph Isomorphism, Clique, Hamiltonian Path/Cycle, and Bandwidth. Obviously, Subgraph Isomorphism is NP-complete in general. When both host and pattern graphs are restricted to be in a graph class $\mathcal {C}$, we call the problem Subgraph Isomorphism on $\mathcal {C}$. By slightly modifying known reductions in [7, 14], one can easily show that the problem is hard even for very restricted graph classes. Recall that a linear forest is the disjoint union of paths and a cluster graph is the disjoint union of complete graphs. We can show the following hardness of Subgraph Isomorphism by a simple reduction from 3-Partition [14].

Proposition 1.1

($\bigstar$¹). Subgraph Isomorphism on linear forests and cluster graphs is NP-complete even if both graphs have the same number of vertices.

Since most of the well-studied graph classes contain all linear forests or all cluster graphs, it is often hopeless to have a polynomial-time algorithm for an interesting graph class. This is sometimes true even if we further assume that the graphs are connected [19, 21]. On the other hand, it is polynomial-time solvable for trees [27]. This result was first generalized for 2-connected outerplanar graphs [24], and finally for k-connected partial k-trees [15, 26] (where the running time is XP parameterized by k). In [26], a polynomial-time algorithm for partial k-trees of bounded maximum degree is presented as well, which is later generalized to partial k-trees of log-bounded fragmentation [16]. It is also known that for chain graphs, co-chain graphs, and threshold graphs, Subgraph Isomorphism is polynomial-time solvable [19,20,21]. In the case where only the pattern graph has to be in a restricted graph class that is closed under vertex deletions, a complexity dichotomy with respect to the graph class is known [17].

Because of its unavoidable hardness in the general case, it is often assumed that the pattern graph is small. In such a setting, we can study the parameterized complexity² of Subgraph Isomorphism parameterized by the size of the pattern graph. Unfortunately, the W[1]-completeness of Clique [9] implies that this parameterization does not help in general. Indeed, the existence of a $2^{o(n \log n)}$-time algorithm for Subgraph Isomorphism is ruled out assuming the Exponential Time Hypothesis, where n is the total number of vertices [5]. So we need further restrictions on the considered graph classes even in the parameterized setting. For planar graphs, it is known to be fixed-parameter tractable [8, 11]. This result is later generalized to graphs of bounded genus [4]. For several graph parameters, the parameterized complexity of Subgraph Isomorphism parameterized by combinations of them is determined in [25]. In [3], it is shown that when the pattern graph excludes a fixed graph as a minor, the problem is fixed-parameter tractable parameterized by treewidth and the size of the pattern graph. The result in [3] implies also that Subgraph Isomorphism can be solved in subexponential time when the host graph also excludes a fixed graph as a minor.

1.1 Our Results

As mentioned above, the research on Subgraph Isomorphism has been done mostly when the size of the pattern graph is considered as a parameter. However, in this paper, we are going to study the general case where the pattern graph can be as large as the host graph.

We first observe that forbidding a graph as an induced substructure (an induced subgraph, an induced topological minor, or an induced minor) does not help for making Subgraph Isomorphism tractable unless we make the graph class trivial by forbidding either adjacent vertices or nonadjacent vertices. This can be done just by combining some easy observations and known results.

Observation 1.2

($\bigstar$). Let $\mathcal {C}$ be the graph class that forbids a fixed graph H as either an induced subgraph, an induced topological minor, or an induced minor. Then, Subgraph Isomorphism on $\mathcal {C}$ is polynomial-time solvable if H has at most two vertices; otherwise, it is NP-complete.

Our main contribution in this paper is the following pair of results on Subgraph Isomorphism on graph classes forbidding a fixed graph as a substructure. (We prove Theorem 1.3 in Sect. 3 and Theorem 1.4 in Sect. 4.)

Theorem 1.3

Let $\mathcal {C}$ be the graph class that forbids a fixed connected graph $H \ne P_{5}$ as either a subgraph, a topological minor, or a minor. Then, Subgraph Isomorphism on $\mathcal {C}$ is polynomial-time solvable if H is a subgraph of $P_{4}$; otherwise, it is NP-complete.

Theorem 1.4

Let $\mathcal {C}$ be the graph class that forbids a fixed (not necessarily connected) graph H as either a subgraph, a topological minor, or a minor. Then, Subgraph Isomorphism on $\mathcal {C}$ is

• fixed-parameter tractable parameterized by the order of H if H is a linear forest such that at most one component is of order 4 and all other components are of order at most 3;

• NP-complete if either H is not a linear forest, H contains a component with six or more vertices, or H contains four components with five vertices.

Note that we have some missing cases. We do not know the complexity of the problem when the forbidden linear forest H contains either

• two or more disjoint $P_{4}$ subgraphs but no $P_{5}$ subgraph, or

• one, two, or three disjoint $P_{5}$ subgraphs but no $P_{6}$ subgraph.

2 Preliminaries and Basic Observations

We denote the path of n vertices by $P_{n}$, the complete graph of n vertices by $K_{n}$, and the star with $\ell$ leaves by $K_{1,\ell }$. For notational convenience, we allow $\ell$ to be 0; that is, $K_{1,0} = P_{1} = K_{1}$. The disjoint union of graphs X and Y is denoted by $X \cup Y$ and the disjoint union of k copies of a graph Z is denoted by kZ.

A graph Q is a minor of G if Q can be obtained from G by removing vertices, removing edges, and contracting edges, where contracting an edge $\{u,v\}$ means adding a new vertex $w_{u,v}$, making the neighbors of u and v adjacent to $w_{u,v}$, and removing u and v. A graph Q is a topological minor of G if Q can be obtained by removing vertices, removing edges, and contracting edges, where contraction of an edge is allowed if one of the endpoints of the edge is of degree 2. A graph Q is a subgraph of G if Q can be obtained by removing vertices and edges. If we cannot remove edges but can do the other modifications as before, then we get the induced variants induced minor, induced topological minor, and induced subgraph.

Recall that a graph is a linear forest if it is the disjoint union of paths. In other words, a graph is a linear forest if and only if it does not contain a cycle nor a vertex of degree at least 3. Observe that in all graph containment relations mentioned above, if we do not forbid any linear forest from a graph class, then the class includes all linear forests. Thus, by Proposition 1.1, we have the following lemma.

Lemma 2.1

If H is not a linear forest, then Subgraph Isomorphism is NP-complete for graphs that do not contain H as a minor, a topological minor, a subgraph, an induced minor, an induced topological minor, or an induced subgraph.

2.1 Graphs Forbidding a Short Path as a Minor

By the discussion above, we can focus on a graph class forbidding a linear forest as a minor (or equivalently as a topological minor or a subgraph). We here characterize graph classes forbidding a short path as a minor.

Lemma 2.2

($\bigstar$). A connected $P_{3}$-minor free graph is isomorphic to $K_{1}$ or $K_{2}$.

Lemma 2.3

($\bigstar$). A connected $P_{4}$-minor free graph is isomorphic to either $K_{3}$ or $K_{1,s}$ for some $s \ge 0$.

3 Forbidding a Connected Graph as a Minor

Here we first show that Subgraph Isomorphism on $P_{k}$-minor free graphs is linear-time solvable if $k \le 4$. Note that $P_{k}$-minor free graphs include all $P_{k'}$-minor free graphs if $k' \le k$.

The following result can be easily obtained from Lemma 2.3.

Lemma 3.1

($\bigstar$). Subgraph Isomorphism on $P_{4}$-minor free graphs is linear-time solvable.

The following theorem implies that Subgraph Isomorphism on $P_{k}$-minor free graphs is NP-complete for every $k \ge 6$.

Theorem 3.2

Subgraph Isomorphism is NP-complete when the host graph is a forest without paths of length 6 and the pattern is a collection of stars.

Proof

The problem clearly is in NP. To show hardness, we reduce from Exact 3-Cover [14]:

Suppose we have an instance $(\mathcal {C}, U)$ of Exact 3-Cover given, where $U = \{u_0, \ldots , u_{n-1}\}$. From $(\mathcal {C}, U)$, we construct the host graph G and the pattern Q.

The host G consists of the disjoint union of $|\mathcal {C}|$ trees as follows (see Fig. 1). For each set $C \in \mathcal {C}$, we take a tree in G as follows. Take a star $K_{1, 4n+6}$. For each $u_{i} \in C$, do the following: take one of the leaves of the star, and add $n+i$ pendant vertices to it. Take another leaf of the star, and add $3n-i$ pendant vertices to it. I.e., if $C = \{u_{i},u_{j},u_{k}\}$, then the corresponding tree has seven vertices of degree more than 1: one vertex with degree $4n+6$, which is also adjacent to each of the other six non-leaf vertices; the non-leaf vertices have degree $n+i+1$, $3n-i+1$, $n+j+1$, $3n-j+1$, $n+k+1$, and $3n-k+1$. Call the vertex of degree $4n+6$ the central vertex of the component of C.

Fig. 1.

The tree in G corresponding to $\{u_{i},u_{j},u_{k}\} \in \mathcal {C}$.

The pattern graph Q consists of a number of stars (see Fig. 2):

• We have n/3 stars $K_{1,4n}$.

• We have $|\mathcal{C}| - n/3$ stars $K_{1,4n+6}$.

• For each $i \in \{0,\dots ,n-1\}$, we have stars $K_{1,n+i}$ and $K_{1,3n-i}$. Call these the element stars.

Fig. 2.

The pattern graph Q.

From $(\mathcal {C}, U)$, G and Q can be constructed in polynomial time. Now we show that $Q \preceq G$ if and only if $(\mathcal {C}, U)$ is a yes-instance of Exact 3-Cover. We assume that $n > 6$ in the following.

The if direction: Suppose that the Exact 3-Cover instance $(\mathcal {C}, U)$ has a solution $\mathcal {C}' \subseteq \mathcal {C}$.

We map each $K_{1,4n+6}$ of Q into a component M of G corresponding to a set $D \notin \mathcal {C}'$. The center of $K_{1,4n+6}$ is mapped to the central vertex of M and all leaves to its neighbors. The other vertices T are isolated and not used.

Embed each $K_{1,4n}$ of Q into a component L of G corresponding to a set $C \in \mathcal {C}'$, mapping the center of $K_{1,4n}$ to the central vertex of L, and the leaves of $K_{1,4n}$ to leaves neighboring the central vertex of L. After we have done so, we left in this component six stars: if $C = \{u_{i}, u_{j}, u_{k}\}$, then the vertices in L that we did not yet use form stars $K_{1,n+i}$, $K_{1,3n-i}$, $K_{1,n+j}$, $K_{1,3n-j}$, $K_{1,n+k}$, $K_{1,3n-k}$. We thus can embed the element stars corresponding to $u_{i}$, $u_{j}$, and $u_{k}$ in these stars, and have embedded the entire pattern in the host graph since $\mathcal {C}'$ is a cover of U.

The only if direction: Suppose that $Q \preceq G$. Note that both Q and G have exactly $|\mathcal {C}|$ vertices of degree at least 4n. Thus it follows that each vertex of degree at least 4n in Q must be mapped to a central vertex of a component in G. We can see that one of the following two cases must hold for the components in the host graph G.

Case 1: A star $K_{1,4n+6}$ is embedded in the component. This “uses up” the central vertex and all its neighbors. The only vertices in the component that are not in the image of the star $K_{1,4n+6}$ are leaves with its neighbor being used: these isolated vertices thus cannot be used for embedding any other stars. So all element stars must be embedded in components for which Case 2 holds.

Case 2: A star $K_{1,4n}$ is embedded in the component. At this point, note that the total number of vertices of element stars in Q equals $4 n^{2} + 2n$: each of the n elements has in total 4n leaves and two high degree vertices in its element stars. Also, the total number of vertices not used by the stars $K_{1,4n}$ in the Case 2-components equals $4n^{2}+2n$: we have n/3 components of Case 2 in G and each has $16n+7$ vertices of which $4n+1$ are used for embedding the star $K_{1,4n}$. Thus, each vertex in a Case 2-component M must be used for embedding a vertex. This is only possible if we embed in M the element stars of the elements in the set corresponding to M.

So, let $\mathcal C'$ be the sets whose component is of Case 2, i.e., where we embedded a $K_{1,4n}$ in its component. This subcollection $\mathcal C'$ is a solution for Exact 3-Cover: for each element $u_i$, its element stars are embedded in a component that corresponds to a set C that contains $u_i$, and by the argument above $C \in \mathcal{C}'$.   $\square$

By Lemma 2.1, if a connected graph H is not a path, then Subgraph Isomorphism on H-minor free graphs is NP-complete. Assume that H is a path $P_{k}$. If $k \ge 6$, then by Theorem 3.2 the problem is NP-complete. If $k \le 4$, then by Lemma 3.1 the problem can be solved in polynomial time. This completes the proof of Theorem 1.3.

4 Forbidding a Disconnected Graph as a Minor

In this section, we study the more general cases where the forbidden minor H is not necessarily connected. By Lemma 2.1, we can focus on linear forests H. We already know, by Theorem 3.2, if H contains a component with six or more vertices the problem becomes NP-complete. Thus in the following we consider the case where the components of H have five or less vertices.

Using the results in this section, we can prove Theorem 1.4. Corollary 4.2 implies the positive case of Theorem 1.4. Theorems 3.2 and 4.4 together with Lemma 2.1 imply the negative cases.

4.1 Subgraph Isomorphism on $(P_{4} \cup k P_{3})$-Minor Free Graphs

We show that Subgraph Isomorphism on $(P_{4} \cup k P_{3})$-minor free graphs is fixed-parameter tractable when parameterized by k. To this end, we present an algorithm that is parameterized by the vertex integrity, which we think is of independent interest. The vertex integrity [1] of a graph is the minimum integer k such that there is a vertex set $S \subseteq V$ such that $|S| \le k$ and the maximum order of the components of $G - S$ is at most $k - |S|$. We call such S a $\mathsf {vi}(k)$ set of G. Note that the property of having vertex integrity at most k is closed under the subgraph relation.

This subsection is devoted to the proof of the following theorem.

Theorem 4.1

Subgraph Isomorphism on graphs of vertex integrity at most k is fixed-parameter tractable when parameterized by k.

By combining Theorem 4.1, Lemma 3.1, and the fact that $k P_{3}$-minor free graphs have vertex integrity at most $3k-1$, we can prove the following.

Corollary 4.2

($\bigstar$). Subgraph Isomorphism on $(P_{4} \cup k P_{3})$-minor free graphs is fixed-parameter tractable when parameterized by k.

To prove Theorem 4.1, we start with the following simple fact.

Lemma 4.3

($\bigstar$). Let $\eta$ be a subgraph isomorphism from Q to G. For every $\mathsf {vi}(k)$ set T of G, there exists a minimal $\mathsf {vi}(k)$ set S of Q such that $\eta (S) \subseteq T$.

Our algorithm assumes that there is a subgraph isomorphism $\eta$ from Q to G and proceeds as follows:

• 1. find a $\mathsf {vi}(k)$ set T of G;

• 2. guess a minimal $\mathsf {vi}(k)$ set S of Q such that $\eta (S) \subseteq T$;

• 3. guess the bijection between S and $R := \eta (S)$;

• 4. guess a subset $F \subseteq E(G - R)$ of the edges “unused” by $\eta$ such that R is a $\mathsf {vi}(k)$ set of $G - F$;

• 5. solve the problem of deciding the extendability of the guessed parts as the feasibility problem of an integer linear program with a bounded number of variables.

Proof

(Proof of Theorem 4.1). Let G and Q be graphs of vertex integrity at most k. Our task is to find a subgraph isomorphism $\eta$ from Q to G in FPT time parameterized by k.

We first find a $\mathsf {vi}(k)$ set T of G and then guess a minimal $\mathsf {vi}(k)$ set S of Q such that $\eta (S) \subseteq T$ for some subgraph isomorphism $\eta$ from Q to G. By Lemma 4.3, such a set S exists if $\eta$ exists. Finding T can be done in $O(k^{k+1} n)$ time [10], where $n = |V(G)|$. To guess S, it suffices to list all minimal $\mathsf {vi}(k)$ set S of Q. The same algorithm in [10] can be used again: it lists all $O(k^{k})$ candidates by branching on $k+1$ vertices that induce a connected subgraph.

We then guess the subset R of T such that $\eta (S) = R$. We also guess for each $s \in S$, the image $\eta (s) \in R$. That is, we guess an injection from S to T. The number of such injections is $\left( {\begin{array}{c}|T|\\ |S|\end{array}}\right) \cdot |S|! \le k!$. If there is an edge $\{u,v\} \in E(Q[S])$ such that $\{\eta (u),\eta (v)\} \notin E(G[R])$, then we reject this guess. Otherwise, we try to further extend $\eta$.

Observe that R is not necessarily a $\mathsf {vi}(k)$ set of G. In the following, we guess “unnecessary” edges in $G-R$. That is, we guess a subset F of the edges that are not used by $\eta$ as images of any edges in Q. Furthermore, we select F so that R is a $\mathsf {vi}(k)$ set of $G - F$. Such F exists because $\eta$ embeds $Q-S$ (and no other things) into $G-R$.

Guessing F: We now show that the number of candidates of F that we need to consider is bounded by some function in k. We partition F into three sets $F_{1} = F \cap E(G[T-R])$, $F_{2} = F \cap E(V(G)-T, T-R)$, and $F_{3} = F \cap E(G-T)$ and then count the numbers of candidates separately.

Guessing $F_{1}$: For $F_{1}$, we just use all $2^{|E(G[T-R])|} < 2^{k^{2}}$ subsets of $E(G[T-R])$ as candidates. If R is not a $\mathsf {vi}(k)$ set of $G[T] - F_{1}$, we reject this $F_{1}$.

Guessing $F_{2}$: Since we are finding F such that R is a $\mathsf {vi}(k)$ set of $G - F$, each vertex in $T-R$ has less than k edges to $V(G) - T$ in $G - F$. Thus fewer than $k^{2}$ components of $V(G)-T$ have edges to $T-R$ in $G - F$. We guess such components $\mathcal {C}$.

Observe that each component in $V(G) - T$ is of order at most k and that each vertex of $V(G) - T$ can be partitioned into at most $2^{k}$ types with respect to the adjacency to T. This implies that the components of $V(G) - T$ can be classified into at most $4^{k^{2}}$ types ($2^{k^{2}}$ for the isomorphism type and $(2^{k})^{k}$ for the adjacency to T) in such a way that if two components $C_{1}$ and $C_{2}$ of $G-T$ are of the same type, then there is an automorphism of G that fixes T and maps $C_{1}$ to $C_{2}$. Given this classification of the components in $V(G) - T$, we only need to guess how many components of each type are included in $\mathcal {C}$. For this guess, we have at most $\left( {\begin{array}{c}4^{k^{2}} + k^{2} - 1\\ k^{2}\end{array}}\right) < 4^{k^{4} + k^{2}}$ options.

For each guess $\mathcal {C}$, we guess the edges connecting the components in $\mathcal {C}$ to $T-R$ in $G-F$. Since $|\mathcal {C}| < k^{2}$ and $|C| \le k$ for each $C \in \mathcal {C}$, there are at most $k^{3} \cdot |T-R| \le k^{4}$ candidate edges. We just try all $O(2^{k^{4}})$ subsets $F_{2}'$ of such edges, and set $F_{2} = E(V(G)-T, T-R) - F_{2}'$. In total, we have $O(2^{k^{4} + k^{2}} \cdot 2^{k^{4}})$ options for $F_{2}$.

Guessing $F_{3}$: Recall that $G - T$ does not contain any component of order more than k. Hence, if $G - R - (F_{1} \cup F_{2})$ has a component of order more than k, then it consists of some vertices in $T-R$ and some components in $\mathcal {C}$. Thus, we only need to pick some edges of the components in $\mathcal {C}$ for $F_{3}$ to make R a $\mathsf {vi}(k)$ set of $G-F$. We use all $2^{k^{4}}$ subsets of the edges of the components in $\mathcal {C}$ as a candidate of $F_{3}$.

In total, $F = F_{1} \cup F_{2} \cup F_{3}$ has at most $2^{k^{2}} \cdot 4^{k^{4} + k^{2}} \cdot 2^{k^{4}} \cdot 2^{k^{4}}$ candidates, and each candidate can be found in FPT time. We reject this guess F if R is not a $\mathsf {vi}(k)$ set of $G-F$. In the following, we assume that F is guessed correctly and denote $G - F$ by $G'$.

Extending $\eta$: Recall that we already know how $\eta$ maps S to R and that each component in $Q - S$ and $G'-R$ is of order at most k. We now extend $\eta$ by determining how $\eta$ maps $Q - S$ to $G'-R$. By renaming vertices, we can assume that $S = \{s_{1}, \dots , s_{q}\}$, $R = \{r_{1}, \dots , r_{q}\}$, and $\eta (s_{i}) = r_{i}$ for $1 \le i \le q$.

We say that a vertex u in $Q-S$ matches a vertex v in $G' - R$ if $\{i \mid s_{i} \in N_{Q}(u) \cap S\} \subseteq \{i \mid r_{i} \in N_{G'}(v) \cap R\}$. A set of components $\{C_{1}, \dots , C_{h}\}$ of $Q - S$ fits a component D of $G' - R$ if there is an isomorphism $\phi$ from the disjoint union of $C_{1}, \dots , C_{h}$ to D such that for all $u \in \bigcup _{i} V(C_{i})$ and $v \in V(D)$, $\phi (u) = v$ holds only if u matches v. Note that if $h > k$, then $\{C_{1}, \dots , C_{h}\}$ can fit no component of $G'-R$.

As we did before for guessing $F_{2}$, we classify the components of $Q-S$ and $G' - R$ into at most $4^{k^{2}}$ types. Two components $C_{1}$ and $C_{2}$ of $Q-S$ (or of $G'-R$) are of the same type if and only if there is an isomorphism $\phi$ from $C_{1}$ to $C_{2}$ such that $\phi (v_{1}) = v_{2}$ implies that $N_{Q}(v_{1}) \cap S = N_{Q}(v_{2}) \cap S$ (or $N_{G'}(v_{1}) \cap R = N_{G'}(v_{2}) \cap R$, respectively). We denote by t(C) the type of a component C and by $t(\{C_{1}, \dots , C_{h}\})$ the multi-set $\{t(C_{1}), \dots , t(C_{h}) \}$. Observe that $\{C_{1}, \dots , C_{h}\}$ fits D if and only if all sets $\{C_{1}', \dots , C_{h}'\}$ with $t(\{C_{1}', \dots , C_{h}'\}) = t(\{C_{1}, \dots , C_{h}\})$ fits $D'$ with $t(D') = t(D)$.

Observe that the guessed part $\eta |_{S}$ can be extended to a subgraph isomorphism $\eta$ from Q to $G'$ if and only if there is a partition of the components of $Q - S$ such that each part $\{C_{1}, \dots , C_{h}\}$ in the partition can be injectively mapped to a component D of $G'-R$ where $\{C_{1}, \dots , C_{h}\}$ fits D. To check the existence of such a partition, we only need to find for each pair of a multi-set $\mathcal {T}$ of types of a set of components in $Q-S$ and a type $\tau$ of a component in $G' - R$, how many sets of components of type $\mathcal {T}$ the map $\eta$ embeds to components of type $\tau$. We use the following ILP formulation to solve this problem.

Let $n_{\tau }$ and $n'_{\tau }$ be the numbers of type-$\tau$ components in $Q-S$ and $G'-R$, respectively. These numbers can be computed in FPT time parameterized by k.

For each type $\tau$ and for each multi-set $\mathcal {T}$ of types such that $\mathcal {T}$ fits $\tau$, we use a variable $x_{\mathcal {T}, \tau }$ to represent the number of type-$\mathcal {T}$ multi-sets of components in $Q - S$ that are mapped to type-$\tau$ components in $G' - R$. For each type $\tau$ of components in $G' - R$, we can embed at most $n_{\tau }$ sets of components in $Q - S$. This constraint is expressed as follows:

$$\begin{aligned} n_{\tau } \ge \sum _{\mathcal {T}:\mathcal {T} \text { fits } \tau } x_{\mathcal {T}, \tau } \quad \text {for each type } \tau . \end{aligned}$$

(1)

For each type $\sigma$ of components in $Q - S$, we need to embed all $n_{\sigma }$ components of type $\sigma$ into some components of $G - R'$. We can express this constraint as follows:

$$\begin{aligned} n_{\sigma } = \sum _{\mathcal {T}, \tau :\sigma \in \mathcal {T} \text { and } \mathcal {T} \text { fits } \tau } \mu _{\mathcal {T}, \sigma } \cdot x_{\mathcal {T}, \tau } \quad \text {for each type } \sigma , \end{aligned}$$

(2)

where $\mu _{\mathcal {T}, \sigma }$ is the multiplicity of $\sigma$ in $\mathcal {T}$. This completes the ILP formulation of the problem. We do not have any objective function and just ask for the feasibility. The construction can be done in FPT time parameterized by k.

Observe that there are at most $\left( {\begin{array}{c}4^{k^{2}} + k - 1\\ k\end{array}}\right) < 4^{k^{3}+k}$ multi-sets $\mathcal {T}$ of types of components. Thus the ILP above has at most $4^{k^{2}} \cdot 4^{k^{3}+k}$ variables (the first factor for $\tau$ and the second for $\mathcal {T}$) and at most $4^{k^{2}} \cdot 4^{k^{3}+k} + 4^{k^{2}} \cdot 4^{k^{2}} \cdot 4^{k^{3}+k}$ constraints (the first term for (1) and the second for (2)) of length $O(4^{k^{2}} \cdot 4^{k^{3}+k})$. The coefficients are upper bounded by $|V(G')|$. It is known that the feasibility check of such an ILP can be done in FPT time parameterized by k [12, 18, 23]. Thus, the problem can be solved in FPT time when parameterized by k.   $\square$

4.2 Subgraph Isomorphism on $4 P_{5}$-Minor Free Graphs

For this case, we show the NP-hardness by a reduction from (3, B2)-Sat [2], which is a restricted version of 3-Sat. (The proof is omitted in this version.)

Theorem 4.4

($\bigstar$). Subgraph Isomorphism on $4 P_{5}$-minor free graphs is NP-complete.

5 Concluding Remarks

As we mentioned before, there are some unsettled cases for Subgraph Isomorphism on H-minor free graphs. If H is connected, then $H = P_{5}$ is only the unknown case. When H can be disconnected, we do not know the complexity when H is a linear forest and either H contains $k P_{4}$ as a subgraph for $k \ge 2$ but no $P_{5}$; or H contains $k P_{5}$ as a subgraph for $k \in \{1,2,3\}$ but no $P_{6}$.

Our results imply some parameterized results. See Fig. 3. (We omit the definitions of the parameters.) The proof of Theorem 3.2 implies that Subgraph Isomorphism is NP-complete even for graphs of tree-depth [28] at most 3. This bound is tight by Lemma 3.1 since graphs of tree-depth at most 2 does not contain $P_{4}$ as a subgraph. Proposition 1.1 implies it is NP-complete even for graphs of constant twin-cover number [13] because cluster graphs have twin-cover number 0. For the parameterization by neighborhood diversity [22], we can use techniques similar to the ones we used in this paper.

Fig. 3.

Graph parameters and Subgraph Isomorphism. For each connection of parameters, there is a function in the parameter above that lower bounds the one below.

Theorem 5.1

($\bigstar$). Subgraph Isomorphism on graphs of neighborhood diversity at most k is fixed-parameter tractable parameterized by k.