# Isomorphic induced subgraph problem using Courcelle's theorem

The isomorphic induced subgraph problem, is the problem of deciding whether, given two graphs $G$ and $H$, $G$ contains an induced subgraph isomorphic to $H$. Is there a proof using Courcelle's theorem, that this problem is fixed-parameter tractable when parameterized by $|H|$ and $\mathrm{tw}(G)$ (treewidth)?

• What do you think? Have you tried to find such a proof? – Yuval Filmus Nov 29 '15 at 13:41
• @YuvalFilmus I already checked online, there are plenty of material, but I couldn't find anywhere a proof of it using Courcelle's theorem. This presentation talks about induced isomorphic subgraphs and Courcelle's theorem, but there isn't anything definitive. – opsorst Nov 29 '15 at 13:46
• Have you tried proving it yourself? Sometimes we want to prove something that nobody has proved before, and we are still able to do it. – Yuval Filmus Nov 29 '15 at 14:09
• @YuvalFilmus No, I never tried to prove it. And I have no idea how to do it. This seems complicated to me. I mean basic things like clique, can easily be proved as $\mathbf{clique}(S) := \forall u \in S \space \forall v \in S \neg u = v \rightarrow \mathbf{adj}(u,v)$, but for this one I have no idea. – opsorst Nov 29 '15 at 15:32
• This is not too difficult to define in MSO$_2$. You know that $H$ has $k$ vertices, so then you want to say something about a subset of $k$ vertices from $G$ with some additional properties. – Juho Nov 29 '15 at 16:00