# Algorithm for detecting if H is a induced subgraph of G in O(n)

Say that I am given a graph $$H$$ and a graph $$G$$ where the maximum degree of $$G$$ is known. How can I use BFS to find out if $$H$$ is an induced subgraph of $$G$$ in $$O(n)$$ time?

My current take is the following:

• Run BFS on $$H$$ and take note of the layer depth.
• Assume I have a function $$g(x)$$: $$H_{nodes}$$ -> $$G_{nodes}$$, which maps each node to in $$H$$ to its correspondent node in $$G$$ if it exists. With this, I do a BFS on each node in $$g(i)$$ where $$i$$ is in the set of $$H_{nodes}$$.
• If each BFS tree on $$G$$ produced by the above results in a BFS tree with the same amount of layers and every node in $$H$$ is contained within these layers, the algorithm return true, if not, return false.

Since we know the maximum depth of the BFS tree on $$H$$ given that we know how many nodes it has, and we know the maximum degree of $$G$$, the algorithm can be viewed as performing a constant operation (albeit possibly large such) $$h$$ times, where $$h$$ is the amount of nodes in $$H$$. $$O(h)$$?

• The Induced subgraph isomorphism problem is $\mathsf{NP}$-complete, I am note sure bounding the degree makes it solvable in polynomial time. Also, what is $n$? Commented Mar 9, 2023 at 10:10
• Sorry, n is the number of nodes in h. Has been edited! Commented Mar 9, 2023 at 11:45
• Is $H$ connected? Also, the running time of an algorithm for this problem will have to include the size of $G$: if e.g. $G$ has $k$ connected components, at least $\Omega(k)$ time is required to test if any of the components contain the induced subgraph, in the worst case. This means you cannot obtain an algorithm in $O(n)$ time, where $n$ is the number of nodes in $H$. Finally, could you clarify how your function $g$ is constructed? Commented Mar 10, 2023 at 10:22
• AFAICT, you don't have the critical piece, namely the function $g(x)$ -- and trying all possible functions will explode the running time. If you are instead assuming that you do have that function, then you already have the answer -- it is necessarily "yes". Commented Mar 11, 2023 at 6:15