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)$?

  • $\begingroup$ 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$? $\endgroup$
    – Nathaniel
    Commented Mar 9, 2023 at 10:10
  • $\begingroup$ Sorry, n is the number of nodes in h. Has been edited! $\endgroup$ Commented Mar 9, 2023 at 11:45
  • $\begingroup$ 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? $\endgroup$
    – Discrete lizard
    Commented Mar 10, 2023 at 10:22
  • $\begingroup$ 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". $\endgroup$ Commented Mar 11, 2023 at 6:15


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.