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

  • $\begingroup$ What do you think? Have you tried to find such a proof? $\endgroup$ – Yuval Filmus Nov 29 '15 at 13:41
  • $\begingroup$ @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. $\endgroup$ – opsorst Nov 29 '15 at 13:46
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Nov 29 '15 at 14:09
  • $\begingroup$ @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. $\endgroup$ – opsorst Nov 29 '15 at 15:32
  • $\begingroup$ 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. $\endgroup$ – Juho Nov 29 '15 at 16:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.